Semigroups and languages of dot-depth two
type: Item
instance of: scholarly article
title: Semigroups and languages of dot-depth two
zbMATH Open document ID: 0655.18004
DOI: 10.1016/0304-3975(88)90034-5
author: Howard Straubing
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 18B40
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4069152
zbMATH Keywords: pseudo-varieties of monoids
zbMATH Keywords: varieties of regular languages
reviewed by: Václav Koubek
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90034-5
OpenAlex ID: W2047822387
cites work: Dot-depth of star-free events
cites work: The dot-depth hierarchy of star-free languages is infinite
cites work: Characterizations of locally testable events
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Q4132170
cites work: Q4199560
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Application of model theoretic games to discrete linear orders and finite automata
cites work: Q3853827
cites work: Algebraic decision procedures for local testability
cites work: Q5641083
cites work: First-order logic and star-free sets
cites work: Q4187326
cites work: Q3774066
cites work: Locally trivial categories and unambiguous concatenation
cites work: On finite monoids having only trivial subgroups
cites work: Q4077455
cites work: A generalization of the Schützenberger product of finite monoids
cites work: Finite semigroup varieties of the form V*D
cites work: Q3730029
cites work: Partially ordered finite monoids and a theorem of I. Simon
cites work: Classification of finite monoids: the language approach
cites work: Catégories et langages de dot-depth un
cites work: Graph congruences and wreath products
cites work: Classifying regular events in symbolic logic
cites work: An application of the Ehrenfeucht-Fraisse game in formal language theory
cites work: Categories as algebra: An essential ingredient in the theory of monoids
description: scientific article; zbMATH DE number 4069152