The factorisation forest theorem

DOI10.4171/AUTOMATA-1/18MaRDI QIDQ2074219zbMATH OpenOpenAlexFDO

Authors Thomas Colcombet

Publication date 4 February 2022

Full work available at URL https://doi.org/10.4171/automata-1/18

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• scientific article; zbMATH DE number 475428
• On factorization forests of finite height
• Factorisation Forests for Infinite Words
• Factorization forests of finite height
• Factorization forests for infinite words and applications to countable scattered linear orderings

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 4072419 (Why is no real title available?)
• scientific article; zbMATH DE number 475428 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A Combinatorial Theorem for Trees
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• An extension of data automata that captures XPath
• An interesting combinatorial method in the theory of locally finite semigroups
• Approximate comparison of distance automata
• Complementation of rational sets on scattered linear orderings of finite rank
• Efficient evaluation of nondeterministic automata using factorization forests
• Enumeration of monadic second-order queries on trees
• Equations Defining the Polynomial Closure of a Lattice of Regular Languages
• Factorisation Forests for Infinite Words
• Factorization Forests
• Factorization forests for infinite words and applications to countable scattered linear orderings
• Factorization forests of finite height
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Limitedness theorem on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Linear time solvable optimization problems on graphs of bounded clique-width
• Logical theories and compatible operations
• Magnitude monadic logic over words and the use of relative internal set theory
• New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
• On factorization forests of finite height
• On semigroups of matrices over the tropical semiring
• Polynomial closure and unambiguous product
• Regular cost functions. I: Logic and algebra over words
• Regular languages of words over countable linear orderings
• Size-Change Abstraction and Max-Plus Automata
• The Height of Factorization Forests
• The limitedness problem on distance automata: Hashiguchi's method revisited
• The monadic theory of order
• XPath evaluation in linear time

Cited in

(2)

• Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
• Regular \(\mathcal{D}\)-length: a tool for improved prefix-stable forward Ramsey factorisations

This page was built for publication: The factorisation forest theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074219)