A Mahler’s Theorem for Word Functions (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Jean-Éric Pin, Christophe Reutenauer



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.125.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Jean-Éric Pin
  • IRIF, Université Paris Denis Diderot, CNRS - Case 7014 - F-75205 Paris Cedex 13, France
Christophe Reutenauer
  • Mathématiques, Université du Québec à Montréal, CP 8888, succ. Centre Ville, Canada H3C 3P8

Cite AsGet BibTex

Jean-Éric Pin and Christophe Reutenauer. A Mahler’s Theorem for Word Functions (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. 125:1-125:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.125

Abstract

Let p be a prime number and let G_p be the variety of all languages recognised by a finite p-group. We give a construction process of all G_p-preserving functions from a free monoid to a free group. Our result follows from a new noncommutative generalization of Mahler’s theorem on interpolation series, a celebrated result of p-adic analysis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Algebraic language theory
Keywords
  • group languages
  • interpolation series
  • pro-p metric
  • regularity preserving

Metrics

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

References

  1. Michaël Cadilhac, Olivier Carton, and Charles Paperman. Continuity and rational functions. In 44th International Colloquium on Automata, Languages, and Programming, volume 80 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 115, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017. Google Scholar
  2. Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, New York, 1976. Google Scholar
  3. M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. Google Scholar
  4. Kurt Mahler. An interpolation series for continuous functions of a p-adic variable. J. Reine Angew. Math., 199:23-34, 1958. Correction 208 (1961), 70-72. Google Scholar
  5. Kurt Mahler. A correction to the paper "An interpolation series for continuous functions of a p-adic variable.". J. Reine Angew. Math., 208:70-72, 1961. Google Scholar
  6. Jean-Éric Pin. Topologie p-adique sur les mots. Journal de théorie des nombres de Bordeaux, 5:263-281, 1993. Google Scholar
  7. Jean-Éric Pin. Newton’s forward difference equation for functions from words to words. In Arnold Beckmann, Victor Mitrana, and Mariya Soskova, editors, Evolving Computability, volume 9136 of Lect. Notes Comp. Sci., pages 71-82. Springer International Publishing, 2015. Google Scholar
  8. Jean-Éric Pin and Pedro V. Silva. A topological approach to transductions. Theoret. Comput. Sci., 340:443-456, 2005. Google Scholar
  9. Jean-Éric Pin and Pedro V. Silva. A Mahler’s theorem for functions from words to integers. In Susanne Albers and Pascal Weil, editors, 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pages 585-596, Dagstuhl, Germany, 2008. Internationales Begegnungs- Und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany. Google Scholar
  10. Jean-Éric Pin and Pedro V. Silva. On profinite uniform structures defined by varieties of finite monoids. Internat. J. Algebra Comput., 21:295-314, 2011. Google Scholar
  11. Jean-Éric Pin and Pedro V. Silva. A noncommutative extension of Mahler’s theorem on interpolation series. European J. Combin., 36:564-578, 2014. Google Scholar
  12. Christophe Reutenauer and Marcel-Paul Schützenberger. Variétés et fonctions rationnelles. Theoret. Comput. Sci., 145(1-2):229-240, 1995. Google Scholar
  13. Harvey E. Rose. A course on finite groups. Universitext. Springer-Verlag London, Ltd., London, 2009. 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