Search Results

Documents authored by Braipson, Thomas

Document
DOI: 10.4230/LIPIcs.MFCS.2026.25
Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings

Authors: Thomas Braipson and Tom Clara

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
Automata on linear orderings are finite-state automata introduced by Bruyère and Carton as a broad generalization of finite, infinite and transfinite-word automata. In this context, a word is defined as a function from a linear ordering to a finite alphabet. This general definition can make automata on linear orderings difficult to reason about. In this work, we introduce constructible words as an intuitive way of tackling this difficulty. These words can be obtained by a finite number of applications of simple operators and thus admit a finite notation. We show that a rational language of words indexed by scattered (countable and uncountable) linear orderings is characterized by its constructible words. Our proof of this result relies on an interesting theorem of semigroup theory due to Colcombet. We expect this property to be useful in future theoretical developments about automata on scattered linear orderings.
Cite as

Thomas Braipson and Tom Clara. Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{braipson_et_al:LIPIcs.MFCS.2026.25,
  author =	{Braipson, Thomas and Clara, Tom},
  title =	{{Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.25},
  URN =		{urn:nbn:de:0030-drops-274062},
  doi =		{10.4230/LIPIcs.MFCS.2026.25},
  annote =	{Keywords: Automata on linear orderings, Rational languages, Ultimately periodic words, Constructible Words, Complementation, Algebraic properties of automata, Semigroups}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact