Semigroups and languages of dot-depth two

DOI10.1016/0304-3975(88)90034-5zbMath0655.18004OpenAlexW2047822387MaRDI QIDQ1109125

Howard Straubing

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90034-5

zbMATH Keywords

pseudo-varieties of monoidsvarieties of regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40)

Related Items

Efficient algorithms for membership in Boolean hierarchies of regular languages, Polynomial closure and unambiguous product, Polynomial closure and unambiguous product, A Note on Decidable Separability by Piecewise Testable Languages, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, The product of rational languages, Polynomial operations and hierarchies of concatenation, Theme and Variations on the Concatenation Product, On a conjecture concerning dot-depth two languages, Closure of varieties of languages under products with counter, Languages of dot-depth 3/2, A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups, Some results on the dot-depth hierarchy, The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin, A counterexample to a conjecture concerning concatenation hierarchies, Separating regular languages with two quantifier alternations, Logic, semigroups and automata on words, Algebraic tools for the concatenation product., A conjecture on the concatenation product

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Categories as algebra: An essential ingredient in the theory of monoids
• First-order logic and star-free sets
• Locally trivial categories and unambiguous concatenation
• Partially ordered finite monoids and a theorem of I. Simon
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Finite semigroup varieties of the form V*D
• Graph congruences and wreath products
• Dot-depth of star-free events
• Characterizations of locally testable events
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Catégories et langages de dot-depth un
• Application of model theoretic games to discrete linear orders and finite automata
• Algebraic decision procedures for local testability
• On finite monoids having only trivial subgroups