论文标题
原始换能器的常规可辨认性是不可证明的
Regular resynchronizability of origin transducers is undecidable
论文作者
论文摘要
我们研究了遏制与双向非确定性传感器之间未知的常规重新同步的关系。我们表明，它构成了预订，并且相应的等价关系在原点等效性和经典等价之间正确地介入。我们给出了一种句法表征，用于遏制两个换能器以进行重新同步，并使用它来证明这种封存关系已经无法确定，而对于单向非确定性传感器以及简单的ressynchronizatization类别。这回答了最近的作品中所述的开放问题，询问这种关系对于双向非确定性传感器是否可以决定。
We study the relation of containment up to unknown regular resynchronization between two-way non-deterministic transducers. We show that it constitutes a preorder, and that the corresponding equivalence relation is properly intermediate between origin equivalence and classical equivalence. We give a syntactical characterization for containment of two transducers up to resynchronization, and use it to show that this containment relation is undecidable already for one-way non-deterministic transducers, and for simple classes of resynchronizations. This answers the open problem stated in recent works, asking whether this relation is decidable for two-way non-deterministic transducers.
