The Many Facets of String Transducers (Invited Talk)

Authors Anca Muscholl, Gabriele Puppis



PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.2.pdf
  • Filesize: 0.55 MB
  • 21 pages

Document Identifiers

Author Details

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

Acknowledgements

We would like to thank our colleagues, in particular D. Figueira, O. Gauwin, F. Mazowiecki and I. Walukiewicz, for their comments on a draft version of this paper.

Cite AsGet BibTex

Anca Muscholl and Gabriele Puppis. The Many Facets of String Transducers (Invited Talk). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.2

Abstract

Regular word transductions extend the robust notion of regular languages from a qualitative to a quantitative reasoning. They were already considered in early papers of formal language theory, but turned out to be much more challenging. The last decade brought considerable research around various transducer models, aiming to achieve similar robustness as for automata and languages. In this paper we survey some older and more recent results on string transducers. We present classical connections between automata, logic and algebra extended to transducers, some genuine definability questions, and review approaches to the equivalence problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • String transducers
  • complexity

Metrics

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

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. A general theory of translation. Math. Syst. Theory, 3(3):193-221, 1969. Google Scholar
  2. M.H. Albert and J. Lawrence. A proof of Ehrenfeucht’s conjecture. Theor. Comput. Sci., 41(1):121-123, 1985. Google Scholar
  3. 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
  4. 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
  5. Rajeev Alur, Emmanuel Filiot, and Ashutosh Trivedi. Regular Transformations of Infinite Strings. In Proc. of Annual IEEE Symposium on Logic in Computer Science (LICS'12), pages 65-74. IEEE, 2012. Google Scholar
  6. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Joint meeting of Annual Conference on Computer Science Logic (CSL) and Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), LIPIcs, pages 9:1-9:10. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2014. Google Scholar
  7. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way Definability of Sweeping Transducers. In IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS'15), volume 45 of LIPIcs, pages 178-191. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  8. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing Resources of Sweeping and Streaming String Transducers. In International Colloquium on Automata, Languages, and Programming (ICALP'16), volume 55 of LIPIcs, pages 114:1-114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  9. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Untwisting two-way transducers in elementary time. In ACM/IEEE Symposium on Logic in Computer Science (LICS'17). IEEE Computer Society, 2017. Google Scholar
  10. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way definability of two-way word transducers. Logical Methods in Computer Science, 14(4):1-54, 2018. Google Scholar
  11. Marie-Pierre Béal and Olivier Carton. Determinization of transducers over finite and infinite words. Theor. Comput. Sci., 289(1):225-251, 2002. Google Scholar
  12. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci., 292:45-63, 2003. Google Scholar
  13. 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
  14. Jean Berstel. Transductions and context-free languages. Teubner Studienbücher Stuttgart, 1979. Google Scholar
  15. Meera Blattner and Tom Head. Single-valued a-transducers. J. Comput. and System Sci., 15:310-327, 1977. Google Scholar
  16. Meera Blattner and Tom Head. The decidability of equivalence for deterministic finite transducers. J. Comput. and System Sci., 19:45-49, 1979. Google Scholar
  17. Mikolaj Bojańczyk. Transducers with origin information. In International Colloquium on Automata, Languages and Programming (ICALP'14), number 8572 in LNCS, pages 26-37. Springer, 2014. Google Scholar
  18. Mikolaj Bojańczyk. The Hilbert Method for Transducer Equivalence. ACM SIGLOG News, January 2019. Google Scholar
  19. Mikolaj Bojańczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which Classes of Origin Graphs Are Generated by Transducers? In International Colloquium on Automata, Languages and Programming (ICALP'17), volume 80 of LIPIcs, pages 114:1-114:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  20. Mikolaj Bojańczyk, Laure Daviaud, and Shankara Narayanan Krishna:. Regular and First-Order List Functions. In Proc. of Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pages 125-134. ACM, 2018. Google Scholar
  21. Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-Equivalence of Two-Way Word Transducers Is in PSPACE. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), volume 122 of LIPIcs, pages 1-18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  22. Julius Richard Büchi. Weak Second-order Arithmetic and Finite Automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. Google Scholar
  23. Olivier Carton, Christian Choffrut, and Serge Grigorieff. Decision problems among the main subfamilies of rational relations. ITA, 40(2):255-275, 2006. Google Scholar
  24. Olivier Carton and Luc Dartois. Aperiodic two-way transducers and FO-transductions. In Proc. of EACSL Annual Conference on Computer Science Logic (CSL'15), LIPIcs, pages 160-174. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  25. Olivier Carton, Léo Exibard, and Olivier Serre. Two-Way Two-Tape Automata. In Proc. in Developments in Language Theory (DLT'17), number 10396 in LNCS, pages 147-159. Springer, 2017. Google Scholar
  26. Christian Choffrut. Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theor. Comput. Sci., 5:325-338, 1977. Google Scholar
  27. Christian Choffrut. Minimizing subsequential transducers: a survey. Theor. Comput. Sci., 292(131-143), 2003. Google Scholar
  28. 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
  29. 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
  30. 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
  31. Luc Dartois, Emmanuel Filiot, Pierre-Alain Reynier, and Jean-Marc Talbot. Two-Way Visibly Pushdown Automata and Transducers. In Proc. of Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), pages 217-226. ACM, 2016. Google Scholar
  32. Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote. On Reversible Transducers. In Proc. of International Colloquium on Automata, Languages, and Programming (ICALP'17,), number 113 in LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  33. Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna. Regular Transducer Expressions for Regular Transformations. In Proc. of Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pages 315-324. ACM, 2018. Google Scholar
  34. Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A Generalised Twinning Property for Minimisation of Cost Register Automata. In Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16), pages 857-866. ACM, 2016. Google Scholar
  35. María Emilia Descotte, Diego Figueira, and Santiago Figueira. Closure properties of synchronized relations. In International Symposium on Theoretical Aspects of Computer Science (STACS'19), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. to appear. Google Scholar
  36. María Emilia Descotte, Diego Figueira, and Gabriele Puppis. Resynchronizing Classes of Word Relations. In International Colloquium on Automata, Languages, and Programming (ICALP'18), volume 123 of LIPIcs, pages 1-13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  37. Volker Diekert. Makanin’s Algorithm. In M. Lothaire, editor, Algebraic combinatorics on words. Cambridge University Press, 2002. Google Scholar
  38. Volker Diekert, Paul Gastin, and Manfred Kufleitner. A survey on Small Fragments of First-Order Logic over Finite Words. International Journal of Foundations of Computer Science, 19(3):513-548, 2008. Google Scholar
  39. Volker Diekert and Manfred Kufleitner. A Survey on the Local Divisor Technique. Theor. Comput. Sci., 610:13-23, 2016. Google Scholar
  40. Samuel Eilenberg. Automata, Languages and Machines. Academic Press, New York, 1976. Google Scholar
  41. Calvin C. Elgot and Jorge E. Mezei. On Relations Defined by Generalized Finite Automata. IBM Journal of Research and Development, 9(1):47-68, 1965. Google Scholar
  42. 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
  43. Diego Figueira and Leonid Libkin. Synchronizing Relations on Words. Theory Comput. Syst., 57(2):287-318, 2015. Google Scholar
  44. Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote. Aperiodicity of Rational Functions Is PSPACE-Complete. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'16), volume 65 of LIPIcs, pages 13:1-13:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  45. Emmanuel Filiot, Olivier Gauwin, Nathan Lhote, and Anca Muscholl. On Canonical Models for Rational Functions over Infinite Words. In Proc. of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), volume 30 of LIPIcs, pages 1-17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  46. Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. From Two-Way to One-Way Finite State Transducers. In ACM/IEEE Symposium on Logic in Computer Science (LICS'13), pages 468-477, 2013. Google Scholar
  47. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On Equivalence and Uniformisation Problems for Finite Transducers. In Proc. of nternational Colloquium on Automata, Languages, and Programming (ICALP'16), number 125 in LIPIcs, pages 1-14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  48. Emmanuel Filiot, Shankara Narayanan Krishna, and Ashutosh Trivedi. First-order Definable String Transformations. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14), LIPIcs, pages 147-159. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  49. Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais, and Jean-Marc Talbot. Visibly pushdown transducers. J. Comput. Syst. Sci., 97:147-181, 2018. Google Scholar
  50. Emmanuel Filiot and Pierre-Alain Reynier. Transducers, logic and algebra for functions of finite words. ACM SIGLOG News, pages 4-19, 2016. Google Scholar
  51. Emmanuel Filiot and Pierre-Alain Reynier. Copyful Streaming String Transducers. In International Workshop on Reachability Problems (RP'17), number 10506 in LNCS, pages 75-86. Springer, 2017. Google Scholar
  52. Patrick C. Fischer and Arnold L. Rosenberg. Multi-tape one-way nonwriting automata. J. Comput. and System Sci., 2:88-101, 1968. Google Scholar
  53. 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
  54. Seymour Ginsburg and Gene F. Rose. A characterization of machine mappings. Canad. J. Math., 18:381-388, 1966. Google Scholar
  55. 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
  56. Eitan M. Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal of Computing, 448-452, 1982. Google Scholar
  57. Eitan M. Gurari and Oscar H. Ibarra. The complexity of decision problems for finite-turn multicounter machines. J. Comput. and System Sci., 16(1):61-66, 1981. Google Scholar
  58. 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
  59. Oscar H. Ibarra. Reversal-bounded multicounter machines and their decision problems. JACM, 1978. Google Scholar
  60. 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
  61. Juhani Karhumäki. The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids. Theor. Comput. Sci., 29:285-308, 1984. Google Scholar
  62. Dexter Kozen. Lower bounds for natural proof systems. In Annual Symposium on Foundations of Computer Science (FOCS'77), pages 254-266. IEEE, 1977. Google Scholar
  63. Christof Löding and Christopher Spinrath. Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words. Discrete mathematics and theoretical computer science, 2019. Google Scholar
  64. Robert McNaughton and Seymour Papert. Counter-Free Automata. MIT Press, 1971. Google Scholar
  65. Albert R. Meyer and Larry J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129. IEEE Computer Society, 1972. Google Scholar
  66. Edward F Moore. Gedanken-experiments on sequential machines. Automata studies, 34:129-153, 1956. Google Scholar
  67. Maurice Nivat. Transduction des langages de Chomsky. Annales de l'Institut Fourier, 18:339-455, 1968. Google Scholar
  68. Jean-Eric Pin. Logic, Semigroups and Automata on Words. Annals of Mathematics and Artificial Intelligence, 16:343-384, 1996. Google Scholar
  69. Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development, pages 114-125, 1959. Google Scholar
  70. Christophe Reutenauer and Marcel-Paul Schützenberger. Minimization of rational word functions. SIAM Journal of Computing, 20(4):669-685, 1991. Google Scholar
  71. Sasha Rubin. Automata Presenting Structures: A Survey of the Finite String Case. Bulletin of Symbolic Logic, 14(2):169-209, 2008. Google Scholar
  72. Jacques Sakarovitch and Rodrigo de Souza. Lexicographic decomposition of K-valued transducers. Theory Comput. Sci., 47:758-785, 2010. Google Scholar
  73. Marcel-Paul Schützenberger. A remark on finite transducers. Information and Control, 4(2-3):185-196, 1961. Google Scholar
  74. Marcel-Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  75. Marcel-Paul Schützenberger. Sur les relations rationnelles. In Proc. of 2nd GI conference, Automata Theory and Formal Languages, number 33 in LNCS, pages 209-213. Springer, 1975. Google Scholar
  76. Marcel-Paul Schützenberger. Sur les relations rationnelles entre monoïdes libres. Theor. Comput. Sci., 3(2):243-259, 1976. Google Scholar
  77. John C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. Google Scholar
  78. Richard E. Stearns and Harry B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, grammars and automata. In Annual Symposium on Foundations of Computer Science (FOCS'81), pages 74-81, 1981. Google Scholar
  79. Moshe Y. Vardi. A Note on the Reduction of Two-Way Automata to One-Way Automata. Information Processing Letters, 30:261-264, 1989. Google Scholar
  80. Andreas Weber. Decomposing A k-Valued Transducer into k Unambiguous Ones. RAIRO-ITA, 30(5):379-413, 1996. Google Scholar
  81. Andreas Weber and Reinhard Klemm. Economy of description for single-valued transducers. Inf. Comput., pages 327-340, 1995. Google Scholar
  82. Thomas Wilke. Classifying Discrete Temporal Properties. In Annual Symposium on Theoretical Aspects of Computer Science (STACS'99), volume 1563 of LNCS, pages 32-46. Springer, 1999. 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