Document Open Access Logo

Origin-Equivalence of Two-Way Word Transducers Is in PSPACE

Authors Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.22.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

Sougata Bose
  • LaBRI, University of Bordeaux, France
Anca Muscholl
  • LaBRI, University of Bordeaux, France
Vincent Penelle
  • LaBRI, University of Bordeaux, France
Gabriele Puppis
  • CNRS and LaBRI, University of Bordeaux, France

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.22

Abstract

We consider equivalence and containment problems for word transductions. These problems are known to be undecidable when the transductions are relations between words realized by non-deterministic transducers, and become decidable when restricting to functions from words to words. Here we prove that decidability can be equally recovered the origin semantics, that was introduced by Bojanczyk in 2014. We prove that the equivalence and containment problems for two-way word transducers in the origin semantics are PSPACE-complete. We also consider a variant of the containment problem where two-way transducers are compared under the origin semantics, but in a more relaxed way, by allowing distortions of the origins. The possible distortions are described by means of a resynchronization relation. We propose MSO-definable resynchronizers and show that they preserve the decidability of the containment problem under resynchronizations. {}

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • Transducers
  • origin semantics
  • equivalence

Metrics

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

Related Versions

References

  1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman. A general theory of translation. Math. Syst. Theory, 3(3):193-221, 1969. Google Scholar
  2. Rajeev Alur and Pavel Cerný. Expressiveness of streaming string transducer. In Proc. of FSTTCS'10, volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. Google Scholar
  3. Rajeev Alur and Jyotirmoy Deshmukh. Nondeterministic streaming string transducers. In Automata, Languages and Programming - 38th International Colloquium (ICALP'11), volume 6756 of LNCS. Springer, 2011. Google Scholar
  4. Jean Berstel. Transductions and context-free languages. Teubner Studienbücher Stuttgart, 1979. Google Scholar
  5. Mikolaj Bojańczyk. Transducers with origin information. In ICALP'14, LNCS, pages 26-37. Springer, 2014. Google Scholar
  6. Mikolaj Bojańczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which Classes of Origin Graphs Are Generated by Transducers? In ICALP'17, volume 80 of LIPIcs, pages 114:1-114:13, 2017. Google Scholar
  7. Bruno Courcelle. The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic. In G. Rozenberg, editor, Handbook of Graph Transformations: Foundations, volume 1, pages 165-254. World Scientific, 1997. Google Scholar
  8. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic. A language-theoretic approach. Encyclopedia of Mathematics and its applications, Vol. 138. Cambridge University Press, 2012. Google Scholar
  9. Karel Culik II and Juhani Karhumäki. The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDT0L Languages) is Decidable. SIAM J. Comput, 16(2):221-230, 1987. Google Scholar
  10. Luc Dartois, Emmanuel Filiot, and Nathan Lhote. Logics for Word Transductions with Synthesis. In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 295-304. ACM, 2018. Google Scholar
  11. Antoine Durand-Gasselin and Peter Habermehl. Regular transformations of data words through origin information. In Proc. of FoSSaCS'15, LNCS, pages 285-300. Springer, 2016. Google Scholar
  12. Samuel Eilenberg. Automata, languages, and machines. Academic press, 1974. Google Scholar
  13. Joost Engelfriet. Context-free graph grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 125-213. Springer, 1997. Google Scholar
  14. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2(2):216-254, 2001. Google Scholar
  15. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On Equivalence and Uniformisation Problems for Finite Transducers. In ICALP'16, volume 55 of LIPIcs, pages 125:1-125:14, 2016. Google Scholar
  16. Emmanuel Filiot, Sebastian Maneth, Pierre-Alain Reynier, and Jean-Marc Talbot. Decision problems of tree transducers with origin. Inf. Comput., 261:311-335, 2018. Google Scholar
  17. Emmanuel Filiot and Pierre-Alain Reynier. Transducers, logic and algebra for functions of finite words. ACM SIGLOG News, pages 4-19, 2016. Google Scholar
  18. T. V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM, 15(3):409-413, 1968. Google Scholar
  19. M.-P. Schützenberger. A Remark on Finite Transducers. Information and Control, 4(2-3):185-196, 1961. Google Scholar
  20. J.C. Shepherdson. The reduction of two-way automata to one-way automata. IBM J. Res. Dev., 3(2):198-200, 1959. Google Scholar
  21. Moshe Y. Vardi. A Note on the Reduction of Two-Way Automata to One-Way Automata. Information Processing Letters, 30(5):261-264, 1989. Google Scholar
  22. Andreas Weber and Helmut Seidl. On the Degree of Ambiguity of Finite Automata. Theor. Comput. Sci., 88(2):325-349, 1991. 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