论文标题
常规交换约束下同步的计算复杂性
Computational Complexity of Synchronization under Regular Commutative Constraints
论文作者
论文摘要
在这里，我们研究了常规交换约束语言类别的约束同步问题的计算复杂性。利用常规交换约束语言的矢量表示，我们对约束同步问题的计算复杂性进行了完整分类。根据约束语言，我们的问题变成了Pspace complete，NP完整或多项式时间。此外，如果某些约束自动机接受了交换性语言作为输入，则我们为约束同步问题的复杂性得出一个多项式时间决策过程。
Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages. Utilizing a vector representation of regular commutative constraint languages, we give a full classification of the computational complexity of the constraint synchronization problem. Depending on the constraint language, our problem becomes PSPACE-complete, NP-complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constraint synchronization problem, given some constraint automaton accepting a commutative language as input.
