Document Open Access Logo

Continuity and Rational Functions

Authors Michaël Cadilhac, Olivier Carton, Charles Paperman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.115.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Michaël Cadilhac
Olivier Carton
Charles Paperman

Cite As Get BibTex

Michaël Cadilhac, Olivier Carton, and Charles Paperman. Continuity and Rational Functions. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.115

Abstract

A word-to-word function is continuous for a class of languages V if its inverse maps V languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes.

Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages.  Previous algebraic studies of transducers have focused on the structure of the underlying input automaton, disregarding the output.  We propose a comparison of the two algebraic approaches through two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?

Subject Classification

Keywords
  • Transducers
  • rational functions
  • language varieties
  • continuity

Metrics

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

References

  1. Jorge Almeida. Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen, 54(1):531-552, 1999. Google Scholar
  2. Jorge Almeida and Alfredo Costa. Equidivisible pseudovarieties of semigroups. Publicationes Mathematicae Debrecen, 90(3-4), 2017. Google Scholar
  3. Jean Berstel. Transductions and Context-Free Languages, volume 38 of Leitfäden der angewandten Mathematik und Mechanik LAMM. Teubner, 1979. Google Scholar
  4. Michaël Cadilhac, Andreas Krebs, Michael Ludwig, and Charles Paperman. A circuit complexity approach to transductions. In MFCS, pages 141-153, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48057-1_11.
  5. Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote. First-order definability of rational transductions: An algebraic approach. In LICS, pages 387-396. ACM, 2016. URL: http://dx.doi.org/10.1145/2933575.2934520.
  6. Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin. Duality and equational theory of regular languages. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 246-257. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_21.
  7. Seymour Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, Inc., New York, NY, USA, 1966. Google Scholar
  8. Jean-Éric Pin. Mathematical foundations of automata theory, 2016. Google Scholar
  9. Jean-Éric Pin and Jacques Sakarovitch. Some operations and transductions that preserve rationality. In Theoretical Computer Science, pages 277-288. Springer, 1982. URL: http://dx.doi.org/10.1007/BFb0036488.
  10. Jean-Éric Pin and Jacques Sakarovitch. Une application de la representation matricielle des transductions. Theoretical Computer Science, 35:271-293, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90019-2.
  11. Jean-Éric Pin and Pedro V. Silva. A topological approach to transductions. Theoretical Computer Science, 340(2):443-456, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.03.029.
  12. Jean-Éric Pin and Pedro V. Silva. On profinite uniform structures defined by varieties of finite monoids. Int. J. of Algebra and Computation, 21(01n02):295-314, 2011. URL: http://dx.doi.org/10.1142/S0218196711006170.
  13. Jean-Éric Pin and Pedro V. Silva. On uniformly continuous functions for some profinite topologies. Theoretical Computer Science, 658, Part A:246-262, 2017. Formal Languages and Automata: Models, Methods and Application In honour of the 70th birthday of Antonio Restivo. URL: http://dx.doi.org/10.1016/j.tcs.2016.06.013.
  14. Jean-Éric Pin and Pascal Weil. Profinite semigroups, Mal'cev products and identities. Journal of Algebra, 182(3):604-626, 1996. Google Scholar
  15. Christophe Reutenaeur and Marcel-Paul Schützenberger. Variétés et fonctions rationnelles. Theoretical Computer Science, 145(1–2):229-240, July 1995. URL: http://dx.doi.org/10.1016/0304-3975(94)00180-Q.
  16. Derek J. S. Robinson. A Course in the Theory of Groups. Springer, 2 edition, 1995. Google Scholar
  17. Klaus Schneider. Verification of Reactive Systems: Formal Methods and Algorithms. SpringerVerlag, 2004. Google Scholar
  18. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, 1994. URL: http://dx.doi.org/10.1007/978-1-4612-0289-9.
  19. Pascal Tesson and Denis Thérien. Logic meets algebra: the case of regular languages. Logical Methods in Computer Science, 3(1), 2007. 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 About DROPS Imprint Privacy Contact