Semigroups and languages of dot-depth two

DOI10.1016/0304-3975(88)90034-5MaRDI QIDQ1109125zbMATH OpenOpenAlexFDO

Authors 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) Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Finite semigroup varieties of the form V*D
• On dot-depth two
• Some results on the dot-depth hierarchy
• On a conjecture concerning dot-depth two languages
• Inverse monoids of dot-depth two

Cites work

• 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?)
• 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
• 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)

• Dot-depth three, return of the j-class
• A Note on Decidable Separability by Piecewise Testable Languages
• On a conjecture concerning dot-depth two languages
• A unified syntactical approach to theorems of Putcha, Margolis, and Straubing on finite power semigroups
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• Some results on the dot-depth hierarchy
• Theme and variations on the concatenation product
• Separating regular languages with two quantifier alternations
• A counterexample to a conjecture concerning concatenation hierarchies
• Varieties generated by 2-testable monoids.
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Closure of varieties of languages under products with counter
• The product of rational languages
• Polynomial operations and hierarchies of concatenation
• Algebraic tools for the concatenation product.
• The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
• Polynomial closure and unambiguous product
• Programs over semigroups of dot-depth one
• Polynomial closure and unambiguous product
• Logic, semigroups and automata on words
• A conjecture on the concatenation product
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Languages of dot-depth 3/2
• scientific article; zbMATH DE number 3961008 (Why is no real title available?)

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)