LIPIcs.ICALP.2019.125.pdf
- Filesize: 0.51 MB
- 13 pages
Document
A Mahler’s Theorem for Word Functions (Track B: Automata, Logic, Semantics, and Theory of Programming)
Authors
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
Cite As Get 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)
0PDF Downloads
References
-
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.
-
Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, New York, 1976.
-
M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997.
-
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.
-
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.
-
Jean-Éric Pin. Topologie p-adique sur les mots. Journal de théorie des nombres de Bordeaux, 5:263-281, 1993.
-
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.
-
Jean-Éric Pin and Pedro V. Silva. A topological approach to transductions. Theoret. Comput. Sci., 340:443-456, 2005.
-
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.
-
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.
-
Jean-Éric Pin and Pedro V. Silva. A noncommutative extension of Mahler’s theorem on interpolation series. European J. Combin., 36:564-578, 2014.
-
Christophe Reutenauer and Marcel-Paul Schützenberger. Variétés et fonctions rationnelles. Theoret. Comput. Sci., 145(1-2):229-240, 1995.
-
Harvey E. Rose. A course on finite groups. Universitext. Springer-Verlag London, Ltd., London, 2009.