Dot-depth of star-free events
From MaRDI portal
Publication:2546343
DOI10.1016/S0022-0000(71)80003-XzbMath0217.29602OpenAlexW2039934838MaRDI QIDQ2546343
Janusz A. Brzozowski, Rina S. Cohen
Publication date: 1971
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(71)80003-x
Related Items (73)
Characterizations of some classes of regular events ⋮ On the expressive power of temporal logic ⋮ On Decidability of Intermediate Levels of Concatenation Hierarchies ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Brzozowski hierarchy of \(\omega\)-languages ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Semigroups and languages of dot-depth two ⋮ Measuring power of locally testable languages ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Inverse monoids of dot-depth two ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Expressive Capacity of Concatenation Freeness ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Unnamed Item ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Languages of R-trivial monoids ⋮ A Trichotomy for Regular Trail Queries ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ A generalization of the Schützenberger product of finite monoids ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Classifying regular events in symbolic logic ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ The product of rational languages ⋮ Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups ⋮ Unnamed Item ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ The expressivity of autosegmental grammars ⋮ LANGUAGES VERSUS ω-LANGUAGES IN REGULAR INFINITE GAMES ⋮ Unnamed Item ⋮ Star-free trace languages ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Theme and Variations on the Concatenation Product ⋮ 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 ⋮ AROUND DOT-DEPTH ONE ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Unnamed Item ⋮ On dot-depth two ⋮ Machines that can output empty words ⋮ An application of the Ehrenfeucht-Fraisse game in formal language theory ⋮ Subsequence versus substring constraints in sequence pattern languages ⋮ The pseudovariety of semigroups of triangular matrices over a finite field ⋮ Imre Simon: an exceptional graduate student ⋮ A generalization of finiteness ⋮ Run languages ⋮ The dot-depth hierarchy of star-free languages is infinite ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Separating regular languages with two quantifier alternations ⋮ Expressive capacity of subregular expressions ⋮ Classifying regular languages by a split game ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ On All Things Star-Free ⋮ Generic results for concatenation hierarchies ⋮ Unnamed Item ⋮ Dot-depth of star-free events ⋮ Games, equations and the dot-depth hierarchy ⋮ Classification of noncounting events ⋮ Varieties ⋮ Characterizations of locally testable events ⋮ 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 ⋮ On the expressive power of temporal logic for infinite words ⋮ A conjecture on the concatenation product ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints ⋮ On a complete set of generators for dot-depth two ⋮ Concatenation-free languages
Cites Work
This page was built for publication: Dot-depth of star-free events
