The dot-depth hierarchy of star-free languages is infinite

Cites Work

Title not available (Why is that?)
On finite monoids having only trivial subgroups
Title not available (Why is that?)
Dot-depth of star-free events
Classification of noncounting events

Cited In (67)

Theme and variations on the concatenation product
A graphic language based on timing diagrams
The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
Perfect correspondences between dot-depth and polynomial-time hierarchies
Programs over aperiodic monoids
On dot-depth two
Sur le produit avec compteur modulo un nombre premier
Brzozowski hierarchy of $\omega$-languages
Level Two of the Quantifier Alternation Hierarchy over Infinite Words
Some complexity results for polynomial rational expressions.
Games, equations and dot-depth two monoids
On a conjecture concerning dot-depth two languages
Subsequence versus substring constraints in sequence pattern languages
Separating regular languages with two quantifier alternations
Some results on the dot-depth hierarchy
$NC^ 1$: The automata-theoretic viewpoint
Level two of the quantifier alternation hierarchy over infinite words
Title not available (Why is that?)
Continuity of functional transducers: a profinite study of rational functions
Inverse monoids of dot-depth two
Covering and separation for logical fragments with modular predicates
The power of diversity
Complexity of universality and related problems for partially ordered NFAs
Inclusion relations between some congruences related to the dot-depth hierarchy
Title not available (Why is that?)
The finite power property in free groups
The Gap Between Partial and Full
Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
The product of rational languages
Generic results for concatenation hierarchies
Non-uniform automata over groups
Robert Knast (1940-1994)
A sufficient condition to polynomially compute a minimum separating DFA
Classifying regular languages by a split game
Languages polylog-time reducible to dot-depth 1/2
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
Title not available (Why is that?)
First-order logic and star-free sets
Semigroups and languages of dot-depth two
Equations and monoid varieties of dot-depth one and two
Title not available (Why is that?)
Recognizable languages and congruences
Regular languages in $NC$
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$
Circuit complexity of regular languages
Games, equations and the dot-depth hierarchy
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
A conjecture on the concatenation product
Finite semigroup varieties of the form V*D
A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
Around dot-depth one
An application of the Ehrenfeucht-Fraisse game in formal language theory
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)