Factorization forests of finite height
From MaRDI portal
We introduce factorization forests. It is shown that the vertex set of a dense factorization forest of finite height satisfies a bounded gap Ramsey-type property of words. The main result is that every morphism from a free semigroup to a finite semigroup S admits a Ramseyan factorization forest of height at most \(9| S|\). Technique for constructing factorization forests are developed.
Recommendations
Cites work
- An interesting combinatorial method in the theory of locally finite semigroups
- Generalisation du theoreme de van der Waerden sur les semi-groupes repetitifs
- scientific article; zbMATH DE number 3873610 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3719449 (Why is no real title available?)
- scientific article; zbMATH DE number 3552814 (Why is no real title available?)
- scientific article; zbMATH DE number 1988973 (Why is no real title available?)
- Limitedness theorem on finite automata with distance functions
- On a natural extension of Jacob's ranks
- Two combinatorial properties of partitions of the free semigroup into finitely many parts
- Un théorème de factorisation des produits d'endomorphismes de K^N
Cited in
(59)- Polynomial closure and unambiguous product
- New upper bounds to the limitedness of distance automata
- The word problem for omega-terms over the Trotter-Weil hierarchy
- Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
- Logic, semigroups and automata on words
- Some properties of recognizable \(\mathcal Z\)-subsets
- The limitedness problem on distance automata: Hashiguchi's method revisited
- On factorization forests of finite height
- What's decidable about weighted automata?
- The factorisation forest theorem
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- One-way resynchronizability of word transducers
- Generic results for concatenation hierarchies
- Entropy of regular timed languages
- Locally countable pseudovarieties
- A Note on Decidable Separability by Piecewise Testable Languages
- Thin and thick timed regular languages
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- R-Automata
- The Height of Factorization Forests
- Factorization Forests
- scientific article; zbMATH DE number 475428 (Why is no real title available?)
- On semigroups of matrices over the tropical semiring
- Separating regular languages with two quantifier alternations
- scientific article; zbMATH DE number 7003194 (Why is no real title available?)
- The product of rational languages
- Polynomial closure and unambiguous product
- The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets
- Around dot-depth one
- Learning definable hypotheses on trees
- String-to-string interpretations with polynomial-size output
- Tight polynomial worst-case bounds for loop programs
- Structure and generation of crossing-critical graphs
- -algebras
- Universality of R-automata with Value Copying
- Definable decompositions for graphs of bounded linear cliquewidth
- From two-way transducers to regular function expressions
- Testing membership for timed automata
- Pebble minimization: the last theorems
- Regular \(\mathcal{D}\)-length: a tool for improved prefix-stable forward Ramsey factorisations
- The boundedness and zero isolation problems for weighted automata over nonnegative rationals
- Stable graphs of bounded twin-width
- Computing the bandwidth of meager timed automata
- On a question about factorization forests
- The expansion problem for infinite trees
- Single-use automata and transducers for infinite alphabets
- MSO queries on trees: enumerating answers under updates using forest algebras
- Edit distance of finite state transducers
- The big-O problem for max-plus automata is decidable (PSPACE-complete)
- Bandwidth of timed automata: 3 classes
- Polynomial kernel for immersion hitting in tournaments
- Rank-decreasing transductions
- Deciding conjugacy of a rational relation (extended abstract)
- A Ramsey theorem for finite monoids
- A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies
- Labelled well quasi ordered classes of bounded linear clique-width
- Factorization forests for infinite words and applications to countable scattered linear orderings
- A survey on the local divisor technique
This page was built for publication: Factorization forests of finite height
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908712)
