Document Open Access Logo

Aperiodic Two-way Transducers and FO-Transductions

Authors Olivier Carton, Luc Dartois

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.160.pdf
  • Filesize: 461 kB
  • 15 pages

Document Identifiers

Author Details

Olivier Carton
Luc Dartois

Cite AsGet BibTex

Olivier Carton and Luc Dartois. Aperiodic Two-way Transducers and FO-Transductions. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 160-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CSL.2015.160

Abstract

Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperiodicity for these transducers and we show that aperiodic transducers correspond exactly to FO-transductions. This lifts to transducers the classical equivalence for languages between FO-definability, recognition by aperiodic monoids and acceptance by counter-free automata.
Keywords
  • Transducer
  • first-order
  • two-way
  • transition monoid
  • aperiodic

Metrics

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

References

  1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. A general theory of translation. Math. Systems Theory, 3:193-221, 1969. Google Scholar
  2. Jorge Almeida. Finite semigroups and universal algebra, volume 3 of Series in Algebra. World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. Google Scholar
  3. Rajeev Alur and Pavol Černý. Expressiveness of streaming string transducers. In 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (STACS'10), volume 8 of LIPIcs - Leibniz International Proceedings in Informatics, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, 2010. Google Scholar
  4. Rajeev Alur, Emmanuel Filiot, and Ashutosh Trivedi. Regular transformations of infinite strings. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, pages 65-74. IEEE Computer Society, 2012. Google Scholar
  5. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS'14, Vienna, Austria, July 14-18, 2014, page 9. ACM, 2014. Google Scholar
  6. Jean-Camille Birget. Concatenation of inputs in a two-way automaton. Theoret. Comput. Sci., 63(2):141-156, 1989. Google Scholar
  7. Mikolaj Bojanczyk. Transducers with origin information. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 26-37. Springer, 2014. Google Scholar
  8. J. Richard Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math., 6:66-92, 1960. Google Scholar
  9. Christian Choffrut. Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theoret. Comput. Sci., 5:325-338, 1977. Google Scholar
  10. Michal P. Chytil and Vojtěch Jákl. Serial composition of 2-way finite-state transducers and simple programs on strings. In Automata, languages and programming (Fourth Colloq., Univ. Turku, Turku, 1977), pages 135-137. Lecture Notes in Comput. Sci., Vol. 52. Springer, Berlin, 1977. Google Scholar
  11. A. Cohen and J.-F. Collard. Instance-wise reaching definition analysis for recursive programs using context-free transductions. In PACT'98, 1998. Google Scholar
  12. Bruno Courcelle. Monadic second-order definable graph transductions: a survey [see MR1251992 (94f:68009)]. Theoret. Comput. Sci., 126(1):53-75, 1994. Seventeenth Colloquium on Trees in Algebra and Programming (CAAP'92) and European Symposium on Programming (ESOP) (Rennes, 1992). Google Scholar
  13. 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
  14. Emmanuel Filiot, Shankara Narayanan Krishna, and Ashutosh Trivedi. First-order definable string transformations. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS'14, December 15-17, 2014, New Delhi, India, volume 29 of LIPIcs - Leibniz International Proceedings in Informatics, pages 147-159. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, 2014. Google Scholar
  15. Christiane Frougny. Numeration systems. In M. Lothaire, editor, Algebraic Combinatorics on Words. Cambridge, 1999. to appear. Google Scholar
  16. J. E. Hopcroft and J. D. Ullman. An approach to a unified theory of automata. Bell System Tech. J., 46:1793-1829, 1967. Google Scholar
  17. S. C. Kleene. Representation of events in nerve nets and finite automata. In Automata studies, Annals of mathematics studies, no. 34, pages 3-41. Princeton University Press, Princeton, N. J., 1956. Google Scholar
  18. Pierre McKenzie, Thomas Schwentick, Denis Thérien, and Heribert Vollmer. The many faces of a translation. In Automata, languages and programming (Geneva, 2000), volume 1853 of Lecture Notes in Comput. Sci., pages 890-901. Springer, Berlin, 2000. Google Scholar
  19. Robert McNaughton and Seymour Papert. Counter-free automata. The M.I.T. Press, Cambridge, Mass.-London, 1971. Google Scholar
  20. A. Nerode. Linear automaton transformation. In Proceeding of the AMS, volume 9, pages 541-544, 1958. Google Scholar
  21. J.-P. Pécuchet. Automates boustrophédon, semi-groupe de Birget et monoïde inversif libre. RAIRO Inform. Théor., 19(1):71-100, 1985. Google Scholar
  22. M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3, 1959. Google Scholar
  23. Christophe Reutenauer and Marcel-Paul Schützenberger. Variétés et fonctions rationnelles. Theoretical Computer Science, 145:229-240, 1995. Google Scholar
  24. Emmanuel Roche and Yves Schabes. Finite-State Language Processing, chapter 7. MIT Press, Cambridge, 1997. Google Scholar
  25. Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  26. Marcel-Paul Schützenberger. Sur le produit de concaténation non ambigu. Semigroup Forum, 13(1):47-75, 1976/77. Google Scholar
  27. J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM J. Res. Develop., 3:198-200, 1959. Google Scholar
  28. Denis Thérien and Thomas Wilke. Over words, two variables are as powerful as one quantifier alternation. In ACM STOCS'98, pages 256-263, 1998. 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