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

DOI10.1016/0022-0000(78)90049-1zbMath0368.68074OpenAlexW2078174437MaRDI QIDQ1242697

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90049-1

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Some complexity results for polynomial rational expressions., Unnamed Item, First-order logic and star-free sets, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, Level two of the quantifier alternation hierarchy over infinite words, Brzozowski hierarchy of $\omega$-languages, Polynomial closure and unambiguous product, Languages polylog-time reducible to dot-depth 1/2, Semigroups and languages of dot-depth two, Robert Knast (1940-1994), Measuring power of locally testable languages, Concatenation hierarchies: new bottle, old wine, The regular languages of wire linear $\mathrm{AC}^0$, Inclusion relations between some congruences related to the dot-depth hierarchy, Programs over aperiodic monoids, Inverse monoids of dot-depth two, Checking Whether an Automaton Is Monotonic Is NP-complete, Unnamed Item, Sur le produit avec compteur modulo un nombre premier, Variétés de langages et monoide des parties, Separability by piecewise testable languages is \textsc{PTime}-complete, A generalization of the Schützenberger product of finite monoids, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, Recognizable languages and congruences, Classifying regular events in symbolic logic, Perfect correspondences between dot-depth and polynomial-time hierarchies, The product of rational languages, Regular languages in $NC$, Unnamed Item, Theme and Variations on the Concatenation Product, $NC^ 1$: The automata-theoretic viewpoint, On a conjecture concerning dot-depth two languages, Games, equations and dot-depth two monoids, Equations and dot-depth one, Languages of dot-depth 3/2, Circuit complexity of regular languages, Some results on the dot-depth hierarchy, AROUND DOT-DEPTH ONE, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, Finite semigroup varieties of the form V*D, Complexity of universality and related problems for partially ordered NFAs, On dot-depth two, An application of the Ehrenfeucht-Fraisse game in formal language theory, Subsequence versus substring constraints in sequence pattern languages, The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin, A graphic language based on timing diagrams, Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures, A sufficient condition to polynomially compute a minimum separating DFA, The Power of Diversity, Unnamed Item, The Gap Between Partial and Full, Quantifier Alternation for Infinite Words, Unnamed Item, Separating regular languages with two quantifier alternations, Classifying regular languages by a split game, Logic, semigroups and automata on words, Succinct representation, leaf languages, and projection reductions, Generic results for concatenation hierarchies, Games, equations and the dot-depth hierarchy, Unnamed Item, On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, A reducibility for the dot-depth hierarchy, Non-uniform automata over groups, Equations and monoid varieties of dot-depth one and two, A conjecture on the concatenation product, The finite power property in free groups, On a complete set of generators for dot-depth two

Cites Work