论文标题
正则表达模式匹配和成员资格的细粒度复杂性
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
论文作者
论文摘要
正则表达模式匹配和成员资格的当前最快算法将经典的O（NM）时间算法提高了大约log^{3/2} n。我们没有专注于一般模式，而是分析了这项工作中有界深度的均匀模式。对于他们来说，已知的分类将类型分类为轻松（强烈的次级）和硬（在塞思下基本上是二次时间）。我们对此分类的硬模式类型进行了非常细粒度的观察，并显示了二分法：很少类型允许超多种物质改进，而其他模式类型的算法只能通过恒定数量的对数因子（假设公式-SAT假设假设）来改进。
The currently fastest algorithm for regular expression pattern matching and membership improves the classical O(nm) time algorithm by a factor of about log^{3/2}n. Instead of focussing on general patterns we analyse homogeneous patterns of bounded depth in this work. For them a classification splitting the types in easy (strongly sub-quadratic) and hard (essentially quadratic time under SETH) is known. We take a very fine-grained look at the hard pattern types from this classification and show a dichotomy: few types allow super-poly-logarithmic improvements while the algorithms for the other pattern types can only be improved by a constant number of log-factors, assuming the Formula-SAT Hypothesis.
