Semigroups and languages of dot-depth two
From MaRDI portal
The author discusses the problem of membership of a finite monoid M in the i-th member \({\mathcal V}_ i\) of a sequence of pseudo-varieties of monoids corresponding to the varieties of regular languages forming the so called Brzozowski hierarchy of locally testable languages. He gives two partial results: a necessary condition for M to belong to \({\mathcal V}_ 2\); for a 2-generated M it is also a sufficient condition.
Recommendations
Cites work
- A generalization of the Schützenberger product of finite monoids
- Algebraic decision procedures for local testability
- An application of the Ehrenfeucht-Fraisse game in formal language theory
- Application of model theoretic games to discrete linear orders and finite automata
- Categories as algebra: An essential ingredient in the theory of monoids
- Catégories et langages de dot-depth un
- Characterizations of locally testable events
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Dot-depth of star-free events
- Finite semigroup varieties of the form V*D
- First-order logic and star-free sets
- Graph congruences and wreath products
- scientific article; zbMATH DE number 3961008 (Why is no real title available?)
- scientific article; zbMATH DE number 4034007 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3624806 (Why is no real title available?)
- scientific article; zbMATH DE number 3640907 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Locally trivial categories and unambiguous concatenation
- On finite monoids having only trivial subgroups
- Parity, circuits, and the polynomial-time hierarchy
- Partially ordered finite monoids and a theorem of I. Simon
- The dot-depth hierarchy of star-free languages is infinite
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(24)- Polynomial operations and hierarchies of concatenation
- On a conjecture concerning dot-depth two languages
- Closure of varieties of languages under products with counter
- A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups
- Some results on the dot-depth hierarchy
- Polynomial closure and unambiguous product
- Programs over semigroups of dot-depth one
- Logic, semigroups and automata on words
- Algebraic tools for the concatenation product.
- Languages of dot-depth 3/2
- Varieties generated by 2-testable monoids.
- A Note on Decidable Separability by Piecewise Testable Languages
- Theme and variations on the concatenation product
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- A conjecture on the concatenation product
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- scientific article; zbMATH DE number 3961008 (Why is no real title available?)
- scientific article; zbMATH DE number 1500543 (Why is no real title available?)
- Separating regular languages with two quantifier alternations
- The product of rational languages
- Polynomial closure and unambiguous product
- The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin
- Dot-depth three, return of the j-class
- A counterexample to a conjecture concerning concatenation hierarchies
This page was built for publication: Semigroups and languages of dot-depth two
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109125)
