Factorization forests for infinite words and applications to countable scattered linear orderings

DOI10.1016/j.tcs.2009.10.013zbMath1183.68336MaRDI QIDQ846364

Thomas Colcombet

Publication date: 9 February 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.10.013

zbMATH Keywords

semigroups; automata; formal languages; infinite words; factorization trees

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Weak MSO with the unbounding quantifier, Regular Languages of Words over Countable Linear Orderings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factorization forests of finite height
• Algorithms for determining relative star height and star height
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• Polynomial closure and unambiguous product
• On factorization forests of finite height
• An interesting combinatorial method in the theory of locally finite semigroups
• Weak Second‐Order Arithmetic and Finite Automata
• Logic and Rational Languages of Words Indexed by Linear Orderings
• R-Automata
• The Height of Factorization Forests
• Equations Defining the Polynomial Closure of a Lattice of Regular Languages
• Modest theory of short chains. I
• Modest theory of short chains. II
• Automata, Semigroups and Recognizability of Words on Ordinals
• Factorisation Forests for Infinite Words
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• $ℵ_0$-categoricity of linear orderings
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees