The dot-depth hierarchy of star-free languages is infinite
From MaRDI portal
(Redirected from Publication:1242697)
Cites work
Cited in
(67)- Perfect correspondences between dot-depth and polynomial-time hierarchies
- Programs over aperiodic monoids
- Sur le produit avec compteur modulo un nombre premier
- On dot-depth two
- Brzozowski hierarchy of \(\omega\)-languages
- Some complexity results for polynomial rational expressions.
- Level Two of the Quantifier Alternation Hierarchy over Infinite Words
- Games, equations and dot-depth two monoids
- On a conjecture concerning dot-depth two languages
- Subsequence versus substring constraints in sequence pattern languages
- Some results on the dot-depth hierarchy
- Theme and variations on the concatenation product
- Separating regular languages with two quantifier alternations
- \(NC^ 1\): The automata-theoretic viewpoint
- A graphic language based on timing diagrams
- Level two of the quantifier alternation hierarchy over infinite words
- scientific article; zbMATH DE number 3892608 (Why is no real title available?)
- Inverse monoids of dot-depth two
- Continuity of functional transducers: a profinite study of rational functions
- The power of diversity
- Covering and separation for logical fragments with modular predicates
- Complexity of universality and related problems for partially ordered NFAs
- Inclusion relations between some congruences related to the dot-depth hierarchy
- scientific article; zbMATH DE number 3827223 (Why is no real title available?)
- The finite power property in free groups
- Generic results for concatenation hierarchies
- The Gap Between Partial and Full
- The product of rational languages
- Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
- Non-uniform automata over groups
- Robert Knast (1940-1994)
- A sufficient condition to polynomially compute a minimum separating DFA
- Languages polylog-time reducible to dot-depth 1/2
- Classifying regular languages by a split game
- Variétés de langages et monoide des parties
- Succinct representation, leaf languages, and projection reductions
- Classifying regular events in symbolic logic
- Checking whether an automaton is monotonic is NP-complete
- First-order logic and star-free sets
- Semigroups and languages of dot-depth two
- The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin
- Equations and monoid varieties of dot-depth one and two
- Recognizable languages and congruences
- Regular languages in \(NC\)
- scientific article; zbMATH DE number 7407796 (Why is no real title available?)
- scientific article; zbMATH DE number 7350780 (Why is no real title available?)
- On a complete set of generators for dot-depth two
- Polynomial closure and unambiguous product
- A generalization of the Schützenberger product of finite monoids
- The regular languages of wire linear \(\mathrm{AC}^0\)
- Games, equations and the dot-depth hierarchy
- Circuit complexity of regular languages
- Measuring power of locally testable languages
- Logic, semigroups and automata on words
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- A reducibility for the dot-depth hierarchy
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Finite semigroup varieties of the form V*D
- A conjecture on the concatenation product
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- An application of the Ehrenfeucht-Fraisse game in formal language theory
- Around dot-depth one
- Quantifier alternation for infinite words
- Languages of dot-depth 3/2
- On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
- Concatenation hierarchies: new bottle, old wine
- Equations and dot-depth one
This page was built for publication: The dot-depth hierarchy of star-free languages is infinite
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1242697)
