Thomas Braipson

dblp:414/5747 · DBLP profile ↗
← Back
3ranked-venue papers
2as first author
3since 2021 · last 2026
0009-0003-0543-5265ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 first-author · 3 since 2021
YearPublicationVenuePosition
2026 Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings
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.
Thomas Braipson, Tom Clara
MFCS1
2026 Efficiently Testing Emptiness of Automata on Linear Orderings
Thomas Braipson, Tom Clara
CIAA1
2025 Epsilon Automata on Linear Orderings
Bernard Boigelot, Thomas Braipson, Tom Clara
CIAA2