The class of known constraint automata for which the constrained synchronization problem is in NP all admit a special form. In this work, we take a closer look at them. We characterize a wider class of constraint automata that give constrained synchronization problems in NP, which encompasses all known problems in NP. We call these automata polycyclic automata. The corresponding language class of polycyclic languages is introduced. We show various characterizations and closure properties for this new language class. We then give a criterion for NP-completeness and a criterion for polynomial time solvability for polycyclic constraint languages.
翻译：限制同步问题在 NP 中的已知限制自动数据类别都承认一种特殊形式。 在此工作中, 我们仔细查看它们。 我们给NP 中造成限制同步问题的更广泛的限制自动数据类别定性, 其中包括NP中所有已知问题。 我们称之为这些自动数据多环自动数据。 引入了多环语言的相应语言类别。 我们为这一新语言类别展示了各种特性和关闭属性。 然后我们给出了 NP 完整性的标准和多环语言多环语言的多元时间可溶性标准 。
相关内容
微信扫码咨询专知VIP会员