2026-07-23T19:56:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12725 2024-03-06T10:50:41Z ddc:004 open_access

Regular Resynchronizability of Origin Transducers Is Undecidable Kuperberg, Denis Martens, Jan transducers origin resynchronisation MSO one-way two-way undecidability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Denis Kuperberg and Jan Martens 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.58 urn:nbn:de:0030-drops-127255 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.58 eng https://creativecommons.org/licenses/by/3.0/legalcode