2 Search Results for "Reutenauer, Christophe"


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

Authors: Jean-Éric Pin and Christophe Reutenauer

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{pin_et_al:LIPIcs.ICALP.2019.125,
  author =	{Pin, Jean-\'{E}ric and Reutenauer, Christophe},
  title =	{{A Mahler’s Theorem for Word Functions}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{125:1--125:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.125},
  URN =		{urn:nbn:de:0030-drops-107019},
  doi =		{10.4230/LIPIcs.ICALP.2019.125},
  annote =	{Keywords: group languages, interpolation series, pro-p metric, regularity preserving}
}
Document
Invited Talk
Some Variations on Lyndon Words (Invited Talk)

Authors: Francesco Dolce, Antonio Restivo, and Christophe Reutenauer

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)


Abstract
In this paper we compare two finite words u and v by the lexicographical order of the infinite words u^omega and v^omega. Informally, we say that we compare u and v by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Algèbres de Lie libres et monoïdes libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].

Cite as

Francesco Dolce, Antonio Restivo, and Christophe Reutenauer. Some Variations on Lyndon Words (Invited Talk). In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dolce_et_al:LIPIcs.CPM.2019.2,
  author =	{Dolce, Francesco and Restivo, Antonio and Reutenauer, Christophe},
  title =	{{Some Variations on Lyndon Words}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.2},
  URN =		{urn:nbn:de:0030-drops-104732},
  doi =		{10.4230/LIPIcs.CPM.2019.2},
  annote =	{Keywords: Lyndon words, Infinite words, Left Lyndon trees, Left Cartesian trees}
}
  • Refine by Author
  • 2 Reutenauer, Christophe
  • 1 Dolce, Francesco
  • 1 Pin, Jean-Éric
  • 1 Restivo, Antonio

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Algebraic language theory
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Infinite words
  • 1 Left Cartesian trees
  • 1 Left Lyndon trees
  • 1 Lyndon words
  • 1 group languages
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2019

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