Document Open Access Logo

Sequentiality of String-to-Context Transducers (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Pierre-Alain Reynier, Didier Villevalois

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.128.pdf
  • Filesize: 0.63 MB
  • 14 pages

Document Identifiers

Author Details

Pierre-Alain Reynier
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Didier Villevalois
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

Funding

This work has been funded by the DeLTA project (ANR-16-CE40-0007).

Cite As Get BibTex

Pierre-Alain Reynier and Didier Villevalois. Sequentiality of String-to-Context Transducers (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. 128:1-128:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.128

Abstract

Transducers extend finite state automata with outputs, and describe transformations from strings to strings. Sequential transducers, which have a deterministic behaviour regarding their input, are of particular interest. However, unlike finite-state automata, not every transducer can be made sequential. The seminal work of Choffrut allows to characterise, amongst the functional one-way transducers, the ones that admit an equivalent sequential transducer.
In this work, we extend the results of Choffrut to the class of transducers that produce their output string by adding simultaneously, at each transition, a string on the left and a string on the right of the string produced so far. We call them the string-to-context transducers. We obtain a multiple characterisation of the functional string-to-context transducers admitting an equivalent sequential one, based on a Lipschitz property of the function realised by the transducer, and on a pattern (a new twinning property). Last, we prove that given a string-to-context transducer, determining whether there exists an equivalent sequential one is in coNP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Formal languages and automata theory
Keywords
  • Transducers
  • Sequentiality
  • Twinning Property
  • Two-Way Transducers

Metrics

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

Related Versions

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. A General Theory of Translation. Mathematical Systems Theory, 3(3):193-221, 1969. URL: http://dx.doi.org/10.1007/BF01703920.
  2. Rajeev Alur and Pavol Černý. Expressiveness of streaming string transducers. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  3. Rajeev Alur and Pavol Černý. Streaming transducers for algorithmic verification of single-pass list-processing programs. In Proc. of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, pages 599-610. ACM, 2011. Google Scholar
  4. Rajeev Alur and Jyotirmoy V. Deshmukh. Nondeterministic Streaming String Transducers. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, volume 6756 of Lecture Notes in Computer Science, pages 1-20. Springer, 2011. Google Scholar
  5. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In CSL-LICS '14, pages 9:1-9:10. ACM, 2014. Google Scholar
  6. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing Resources of Sweeping and Streaming String Transducers. In ICALP 2016, volume 55 of LIPIcs, pages 114:1-114:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  7. Nicolas Baudru and Pierre-Alain Reynier. From Two-Way Transducers to Regular Function Expressions. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, volume 11088 of Lecture Notes in Computer Science, pages 96-108. Springer, 2018. Google Scholar
  8. Marie-Pierre Béal and Olivier Carton. Determinization of transducers over finite and infinite words. Theoretical Computer Science, 289(1):225-251, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00271-7.
  9. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theoretical Computer Science, 292(1):45-63, 2003. Google Scholar
  10. Mikolaj Boja'nczyk, Laure Daviaud, and Shankara Narayanan Krishna. Regular and First-Order List Functions. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 125-134. ACM, 2018. Google Scholar
  11. Adam L. Buchsbaum, Raffaele Giancarlo, and Jeffery Westbrook. On the Determinization of Weighted Finite Automata. SIAM J. Comput., 30(5):1502-1531, 2000. URL: http://dx.doi.org/10.1137/S0097539798346676.
  12. Christian Choffrut. Une Caractérisation des Fonctions Séquentielles et des Fonctions Sous-Séquentielles en tant que Relations Rationnelles. Theor. Comput. Sci., 5(3):325-337, 1977. URL: http://dx.doi.org/10.1016/0304-3975(77)90049-4.
  13. Michal Chytil and Vojtech Jákl. Serial Composition of 2-Way Finite-State Transducers and Simple Programs on Strings. In Automata, Languages and Programming, Fourth Colloquium, University of Turku, Finland, July 18-22, 1977, Proceedings, volume 52 of Lecture Notes in Computer Science, pages 135-147. Springer, 1977. Google Scholar
  14. Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna. Regular Transducer Expressions for Regular Transformations. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 315-324. ACM, 2018. Google Scholar
  15. Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A Generalised Twinning Property for Minimisation of Cost Register Automata. In LICS '16, pages 857-866. ACM, 2016. Google Scholar
  16. 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
  17. Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin. Quantitative Languages Defined by Functional Automata. Logical Methods in Computer Science, 11(3), 2015. URL: http://dx.doi.org/10.2168/LMCS-11(3:14)2015.
  18. Emmanuel Filiot, Nicolas Mazzocchi, and Jean-François Raskin. A Pattern Logic for Automata with Outputs. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, volume 11088 of Lecture Notes in Computer Science, pages 304-317. Springer, 2018. Google Scholar
  19. Emmanuel Filiot and Pierre-Alain Reynier. Transducers, logic and algebra for functions of finite words. SIGLOG News, 3(3):4-19, 2016. URL: https://dl.acm.org/citation.cfm?id=2984453.
  20. N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109-114, 1965. URL: http://dx.doi.org/10.2307/2034009.
  21. Eitan M. Gurari. The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable. SIAM J. Comput., 11(3):448-452, 1982. URL: http://dx.doi.org/10.1137/0211035.
  22. Daniel Kirsten and Ina Mäurer. On the Determinization of Weighted Automata. Journal of Automata, Languages and Combinatorics, 10(2/3):287-312, 2005. URL: http://dx.doi.org/10.25596/jalc-2005-287.
  23. Sylvain Lombardy and Jacques Sakarovitch. Sequential? Theor. Comput. Sci., 356(1-2):224-244, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.01.028.
  24. M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002. URL: http://dx.doi.org/10.1017/CBO9781107326019.
  25. Dana S. Scott. Some Definitional Suggestions for Automata Theory. J. Comput. Syst. Sci., 1(2):187-212, 1967. URL: http://dx.doi.org/10.1016/S0022-0000(67)80014-X.
  26. Helmut Seidl. When Is a Functional Tree Transduction Deterministic? In TAPSOFT'93: Theory and Practice of Software Development, International Joint Conference CAAP/FASE, Orsay, France, April 13-17, 1993, Proceedings, volume 668 of Lecture Notes in Computer Science, pages 251-265. Springer, 1993. Google Scholar
  27. Andreas Weber and Reinhard Klemm. Economy of Description for Single-Valued Transducers. Inf. Comput., 118(2):327-340, 1995. URL: http://dx.doi.org/10.1006/inco.1995.1071.
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 About DROPS Imprint Privacy Contact