Dot-depth of star-free events

DOI10.1016/S0022-0000(71)80003-XzbMath0217.29602MaRDI QIDQ2546343

Janusz A. Brzozowski, Rina S. Cohen

Publication date: 1971

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

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

The pseudovariety of semigroups of triangular matrices over a finite field, Imre Simon: an exceptional graduate student, Unnamed Item, On dot-depth two, Descriptional and computational complexity of finite automata -- a survey, Equations and dot-depth one, Non-uniform automata over groups, On the expressive power of temporal logic for infinite words, Languages polylog-time reducible to dot-depth 1/2, Classifying regular languages by a split game, Characterizations of some classes of regular events, Brzozowski hierarchy of \(\omega\)-languages, Semigroups and languages of dot-depth two, Inverse monoids of dot-depth two, Languages of R-trivial monoids, A generalization of the Schützenberger product of finite monoids, Classifying regular events in symbolic logic, Star-free trace languages, On a conjecture concerning dot-depth two languages, Games, equations and dot-depth two monoids, A generalization of finiteness, Run languages, The dot-depth hierarchy of star-free languages is infinite, Equations and monoid varieties of dot-depth one and two, On a complete set of generators for dot-depth two, Games, equations and the dot-depth hierarchy, Inclusion relations between some congruences related to the dot-depth hierarchy, Machines that can output empty words, On the expressive power of temporal logic, Languages of dot-depth 3/2, Dot-depth of star-free events, Classification of noncounting events, Characterizations of locally testable events, A reducibility for the dot-depth hierarchy, Theme and Variations on the Concatenation Product, On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, A conjecture on the concatenation product, An application of the Ehrenfeucht-Fraisse game in formal language theory, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, Hierarchies and reducibilities on regular languages related to modulo counting, Unnamed Item, Descriptional and Computational Complexity of Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dot-depth of star-free events
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• A Note on Star-Free Events
• Derivatives of Regular Expressions