Search Results

Documents authored by Rigo, Michel

Document
DOI: 10.4230/LIPIcs.MFCS.2022.79
On Extended Boundary Sequences of Morphic and Sturmian Words

Authors: Michel Rigo, Manon Stipulanti, and Markus A. Whiteland

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Generalizing the notion of the boundary sequence introduced by Chen and Wen, the nth term of the 𝓁-boundary sequence of an infinite word is the finite set of pairs (u,v) of prefixes and suffixes of length 𝓁 appearing in factors uyv of length n+𝓁 (n ≥ 𝓁 ≥ 1). Otherwise stated, for increasing values of n, one looks for all pairs of factors of length 𝓁 separated by n-𝓁 symbols. For the large class of addable numeration systems U, we show that if an infinite word is U-automatic, then the same holds for its 𝓁-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and U-automatic words with a boundary sequence that is not U-automatic. In the second part of the paper, we study the 𝓁-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.
Cite as

Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. On Extended Boundary Sequences of Morphic and Sturmian Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 79:1-79:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rigo_et_al:LIPIcs.MFCS.2022.79,
  author =	{Rigo, Michel and Stipulanti, Manon and Whiteland, Markus A.},
  title =	{{On Extended Boundary Sequences of Morphic and Sturmian Words}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{79:1--79:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.79},
  URN =		{urn:nbn:de:0030-drops-168776},
  doi =		{10.4230/LIPIcs.MFCS.2022.79},
  annote =	{Keywords: Boundary sequences, Sturmian words, Numeration systems, Automata, Graph of addition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.118
An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Authors: Bernard Boigelot, Isabelle Mainz, Victor Marsault, and Michel Rigo

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a b-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.
Cite as

Bernard Boigelot, Isabelle Mainz, Victor Marsault, and Michel Rigo. An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 118:1-118:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boigelot_et_al:LIPIcs.ICALP.2017.118,
  author =	{Boigelot, Bernard and Mainz, Isabelle and Marsault, Victor and Rigo, Michel},
  title =	{{An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{118:1--118:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.118},
  URN =		{urn:nbn:de:0030-drops-74317},
  doi =		{10.4230/LIPIcs.ICALP.2017.118},
  annote =	{Keywords: integer-base systems, automata, recognisable sets, periodic sets}
}
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