论文标题
理想的分离和一般定理，用于约束同步及其应用于小约束自动机
Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata
论文作者
论文摘要
在受约束的同步问题中，我们询问给定的自动机是否接受来自固定常规约束语言的同步单词。我们表明，将给定的约束语言与理想语言相交会降低计算复杂性。此外，我们陈述了一个定理，给出了Pspace硬度，该定理广泛概括了先前使用的构造，并取决于如何通过串联结合语言以获得多项式时间可溶解的约束同步问题。我们使用这些结果将复杂性景观的分类用于小小的约束自动机，最多为三个状态。
In the constrained synchronization problem we ask if a given automaton admits a synchronizing word coming from a fixed regular constraint language. We show that intersecting a given constraint language with an ideal language decreases the computational complexity. Additionally, we state a theorem giving PSPACE-hardness that broadly generalizes previously used constructions and a result on how to combine languages by concatenation to get polynomial time solvable constrained synchronization problems. We use these results to give a classification of the complexity landscape for small constraint automata of up to three states.
