Document Open Access Logo

Equivalence of Finite-Valued Streaming String Transducers Is Decidable (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Anca Muscholl, Gabriele Puppis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.122.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Anca Muscholl
  • LaBRI, University of Bordeaux, France
Gabriele Puppis
  • CNRS, LaBRI, Bordeaux, France

Funding

DeLTA project (ANR-16-CE40-0007)

Cite AsGet BibTex

Anca Muscholl and Gabriele Puppis. Equivalence of Finite-Valued Streaming String Transducers Is Decidable (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 122:1-122:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.122

Abstract

In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transducers is decidable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • String transducers
  • equivalence
  • Ehrenfeucht conjecture

Metrics

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

Related Versions

References

  1. M.H. Albert and J. Lawrence. A proof of Ehrenfeucht’s conjecture. Theor. Comput. Sci., 41(1):121-123, 1985. Google Scholar
  2. Rajeev Alur and Pavel Cerný. Expressiveness of streaming string transducer. In IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS'10), volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. Google Scholar
  3. Rajeev Alur and Pavol Cerný. Streaming Transducers for Algorithmic Verification of Single-pass List-processing Programs. In POPL'11. ACM, 2011. Google Scholar
  4. Rajeev Alur, Loris D'Antoni, Jyotirmoy Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In Proc. of Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013), pages 13-22. IEEE, 2013. Google Scholar
  5. Rajeev Alur and Jyotirmoy Deshmukh. Nondeterministic streaming string transducers. In International Colloquium on Automata, Languages and Programming (ICALP'11), volume 6756 of LNCS. Springer, 2011. Google Scholar
  6. Michael Benedikt, Timothy Duff, Aditya Sharad, and James Worrell. Polynomial automata: Zeroness and applications. In Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17), pages 1-12. IEEE, 2017. Google Scholar
  7. Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude. Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method". In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), volume 122 of LIPIcs, pages 48:1-48:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  8. Mikolaj Bojańczyk. The Hilbert Method for Transducer Equivalence. ACM SIGLOG News, January 2019. Google Scholar
  9. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. Google Scholar
  10. Karel Culik II and Juhani Karhumäki. The equivalence of finite valued transducers (on HDT0L languages) is decidable. Theor. Comput. Sci., 47:71-84, 1986. Google Scholar
  11. Volker Diekert. Makanin’s Algorithm. In M. Lothaire, editor, Algebraic combinatorics on words, volume 90 of Encyclopedia of mathematics and its applications, chapter 12, pages 387-442. Cambridge University Press, 2002. Google Scholar
  12. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Log., 2(2):216-254, 2001. Google Scholar
  13. Patrick C. Fischer and Arnold L. Rosenberg. Multi-tape one-way nonwriting automata. J. Comput. and System Sci., 2:88-101, 1968. Google Scholar
  14. Paul Gallot, Anca Muscholl, Gabriele Puppis, and Sylvain Salvati. On the Decomposition of Finite-Valued Streaming String Transducers. In Annual Symposium on Theoretical Aspects of Computer Science (STACS'17), volume 66 of LIPIcs, pages 34:1-34:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  15. Victor S. Guba. Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. Mat. Zametki, 40(3):688 - -690, 1986. Google Scholar
  16. Eitan M. Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal of Computing, 448-452, 1982. Google Scholar
  17. Eitan M. Gurari and Oscar H. Ibarra. A note on finite-valued and finitely ambiguous transducers. Math. Syst. Theory, 16(1):61-66, 1983. Google Scholar
  18. Oscar H. Ibarra. The unsolvability of the equivalence problem for e-free NGSM’s with unary input (output) alphabet and applications. SIAM J. of Comput., 7(4):524-532, 1978. Google Scholar
  19. Artur Jez. Word Equations in Nondeterministic Linear Space. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP'17), volume 80 of LIPIcs, pages 95:1-95:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. Google Scholar
  20. Juhani Karhumäki. The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids. Theor. Comput. Sci., 29:285-308, 1984. Google Scholar
  21. Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE. JACM, 51(3):483-496, 2004. Google Scholar
  22. Jacques Sakarovitch and Rodrigo de Souza. On the decomposition of k-valued rational relations. In Annual Symposium on Theoretical Aspects of Computer Science (STACS'08), volume 1 of LIPIcs, pages 621-632. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008. Google Scholar
  23. Jacques Sakarovitch and Rodrigo de Souza. Lexicographic decomposition of K-valued transducers. Theory Comput. Sci., 47:758-785, 2010. Google Scholar
  24. Andreas Weber. Decomposing A k-Valued Transducer into k Unambiguous Ones. RAIRO-ITA, 30(5):379-413, 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