Document Open Access Logo

Continuous Rational Functions Are Deterministic Regular

Authors Olivier Carton , Gaëtan Douéneau-Tabot

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2022.28.pdf
  • Filesize: 0.78 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • infinite words
  • rational functions
  • determinization
  • continuity
  • streaming string transducers
  • two-way transducers

Metrics

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

Abstract

A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers).
This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al.

Cite As Get BibTex

Olivier Carton and Gaëtan Douéneau-Tabot. Continuous Rational Functions Are Deterministic Regular. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.28

Author Details

Olivier Carton
  • IRIF, Université Paris Cité, France
Gaëtan Douéneau-Tabot
  • IRIF, Université Paris Cité, France
  • Direction générale de l'armement - Ingénierie de projets, Paris, France

Funding

This work was supported by the DeLTA ANR project (https://anr.fr/Projet-ANR-16-CE40-0007).

References

  1. 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, volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl, 2010. Google Scholar
  2. 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, pages 65-74. IEEE Computer Society, 2012. Google Scholar
  3. Christian Choffrut and Serge Grigorieff. Uniformization of rational relations. In Jewels are Forever, pages 59-71. Springer, 1999. Google Scholar
  4. Luc Dartois, Ismaël Jecker, and Pierre-Alain Reynier. Aperiodic string transducers. Int. J. Found. Comput. Sci., 29(5):801-824, 2018. Google Scholar
  5. Vrunda Dave, Emmanuel Filiot, Shankara Narayanan Krishna, and Nathan Lhote. Synthesis of computable regular functions of infinite words. In 31st International Conference on Concurrency Theory (CONCUR 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  6. Gaëtan Douéneau-Tabot, Emmanuel Filiot, and Paul Gastin. Register transducers are marble transducers. In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, 2020. Google Scholar
  7. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001. Google Scholar
  8. Emmanuel Filiot and Sarah Winter. Synthesizing computable functions from rational specifications over infinite words. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, December 15-17, 2021, Virtual Conference. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  9. Dominique Perrin and Jean-Éric Pin. Infinite words: automata, semigroups, logic and games. Academic Press, 2004. Google Scholar
  10. Christophe Prieur. How to decide continuity of rational functions on infinite words. Theoretical Computer Science, 250(1-2):71-82, 2001. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact