2021/01/20 by Sougata Bose, S. N. Krishna, Bose, Sougata +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #68Q45 #DNA and Biological Computing #F.1.1 #F.4.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Modular Robots and Swarm Intelligence #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2101.08011
openalex publication_date 2021/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The origin semantics for transducers was proposed in 2014, and led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer.