论文标题
在字母模式约束上的置换状态复杂性和相关决策问题
State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints
论文作者
论文摘要
我们研究了对字母模式约束（APC）的置换操作或交换闭合的状态复杂性。该类对应于Straubing-th {é} rien层次结构的$ 3/2 $，包括有限，分段测试或$ \ Mathcal j $ - trivial，以及$ \ Mathcal r $ $ $ $ $ - 琐事和$ \ Mathcal l $ trivicial语言。我们给出了一种尖锐的状态复杂性，它根据相关的有限语言的一单位投影语言中最长的字符串表示，并且对于有限语言的子类已经很敏锐。此外，对于两个子类，我们给出了以识别输入自动机和字母大小的大小表示尖锐的边界。最后，我们研究了APC上的包含和普遍性问题，直到置换等效性，即使对于固定的字母，在APC上已知两个问题是在APC上完全完整的，并且在这种情况下，在多项式时间内可以在多项式时间内确定它们。
We investigate the state complexity of the permutation operation, or the commutative closure, on Alphabetical Pattern Constraints (APC). This class corresponds to level $3/2$ of the Straubing-Th{é}rien Hierarchy and includes the finite, the piecewise-testable, or $\mathcal J$-trivial, and the $\mathcal R$-trivial and $\mathcal L$-trivial languages. We give a sharp state complexity bound expressed in terms of the longest strings in the unary projection languages of an associated finite language and which is already sharp for the subclass of finite languages. Additionally, for two subclasses, we give sharp bounds expressed in terms of the size of a recognizing input automaton and the size of the alphabet. Lastly, we investigate the inclusion and universality problem on APCs up to permutational equivalence, two problems known to be PSPACE-complete on APCs even for fixed alphabets in general, and show them to be decidable in polynomial time for fixed alphabets in this case.
