Document Open Access Logo

Regular Resynchronizability of Origin Transducers Is Undecidable

Authors Denis Kuperberg , Jan Martens

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.58.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Denis Kuperberg
  • CNRS, LIP, ENS Lyon, France
Jan Martens
  • Eindhoven University of Technology, The Netherlands

Cite AsGet BibTex

Denis Kuperberg and Jan Martens. Regular Resynchronizability of Origin Transducers Is Undecidable. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.58

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • transducers
  • origin
  • resynchronisation
  • MSO
  • one-way
  • two-way
  • undecidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Rajeev Alur and Pavol Černý. Expressiveness of streaming string transducers. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume 8 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1-12, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  2. Mikołaj Bojańczyk. Transducers with origin information. In International Colloquium on Automata, Languages, and Programming, pages 26-37. Springer, 2014. Google Scholar
  3. Mikolaj Bojańczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which classes of origin graphs are generated by transducers. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 114:1-114:13, 2017. Google Scholar
  4. Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. On Synthesis of Resynchronizers for Transducers. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1-69:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  5. Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-equivalence of two-way word transducers is in PSPACE. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  6. J Richard Buchi. Weak second-order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, page 6:66–92, 1960. Google Scholar
  7. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001. Google Scholar
  8. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  9. T. V. Griffiths. The unsolvability of the equivalence problem for Λ-free nondeterministic generalized machines. J. ACM, 15(3):409-413, July 1968. Google Scholar
  10. Oscar H Ibarra. The unsolvability of the equivalence problem for ε-free NGSM’s with unary input (output) alphabet and applications. SIAM Journal on Computing, 7(4):524-532, 1978. Google Scholar
  11. Emil L. Post. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc., 52(4):264-268, April 1946. Google Scholar
  12. Michael Sipser. Introduction to the Theory of Computation. International Thomson Publishing, 1st edition, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact