On Reversible Transducers

Authors Luc Dartois, Paulin Fournier, Ismaël Jecker, Nathan Lhote



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.113.pdf
  • Filesize: 0.53 MB
  • 12 pages

Document Identifiers

Author Details

Luc Dartois
Paulin Fournier
Ismaël Jecker
Nathan Lhote

Cite AsGet BibTex

Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote. On Reversible Transducers. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 113:1-113:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.113

Abstract

Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this paper, we introduce a class of transducers for which the composition has polynomial complexity. It is the class of reversible transducers, for which the computation steps can be reversed deterministically. While in the one-way setting this class is not very expressive, we prove that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we prove that the composition of two-way transducers can be done with a single exponential blow-up in the number of states. A uniformization of a relation is a function with the same domain and which is included in the original relation. Our main result actually states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up, improving the known result by de Souza which has a quadruple exponential complexity. As a side result, our construction also gives a quadratic transformation from copyless streaming string transducers to two-way transducers, improving the exponential previous bound.
Keywords
  • Transducers
  • reversibility
  • two-way
  • uniformization

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. Mathematical Systems Theory, 3(3):193-221, 1969. Google Scholar
  2. Rajeev Alur and Pavol Cerný. Expressiveness of streaming string transducers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, pages 1-12, 2010. Google Scholar
  3. 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, 2012. Google Scholar
  4. Julius R. Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math., 6:66-92, 1960. Google Scholar
  5. Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote. On reversible transducers. CoRR, abs/1702.07157, 2017. URL: http://arxiv.org/abs/1702.07157.
  6. Luc Dartois, Ismaël Jecker, and Pierre-Alain Reynier. Aperiodic string transducers. In Developments in Language Theory - 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings, pages 125-137, 2016. Google Scholar
  7. Rodrigo de Souza. Uniformisation of two-way transducers. In Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings, pages 547-558, 2013. Google Scholar
  8. John E. Hopcroft and Jeffrey D. Ullman. An approach to a unified theory of automata. In 8th Annual Symposium on Switching and Automata Theory, Austin, Texas, USA, October 18-20, 1967, pages 140-147, 1967. Google Scholar
  9. Attila Kondacs and John Watrous. On the power of quantum finite state automata. In 38th Annual Symposium on Foundations of Computer Science, FOCS'97, Miami Beach, Florida, USA, October 19-22, 1997, pages 66-75, 1997. Google Scholar
  10. Michal Kunc and Alexander Okhotin. Reversibility of computations in graph-walking automata. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, pages 595-606, 2013. Google Scholar
  11. Jean-Eric Pin. On reversible automata. In LATIN'92, 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6-10, 1992, Proceedings, pages 401-416, 1992. Google Scholar
  12. 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
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