scientific article; zbMATH DE number 3827223

MaRDI QIDQ3673124zbMATH OpenFDO

Authors R. Knast

Publication date 1983

Full work available at URL https://eudml.org/doc/92191

zbMATH Keywords

dot-depth hierarchydot-depth onealgebraic characterization of the syntactic semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Cites work

• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• Dot-depth of star-free events
• The dot-depth hierarchy of star-free languages is infinite

Cited in

(40)

• Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata.
• Profinite categories and semidirect products
• On the equation \(x^ t=x^{t+q}\) in categories
• Games, equations and dot-depth two monoids
• On a conjecture concerning dot-depth two languages
• Some results on the dot-depth hierarchy
• Theme and variations on the concatenation product
• Separating regular languages with two quantifier alternations
• Profinite categories, implicit operations and pseudovarieties of categories
• scientific article; zbMATH DE number 3892608 (Why is no real title available?)
• Inverse monoids of dot-depth two
• Inclusion relations between some congruences related to the dot-depth hierarchy
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Generic results for concatenation hierarchies
• The product of rational languages
• A property of the Schützenberger product
• Robert Knast (1940-1994)
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Languages polylog-time reducible to dot-depth 1/2
• Algebraic tools for the concatenation product.
• Alternation hierarchies of first order logic with regular predicates
• Locality and Centrality: The Variety ZG
• Characterizations of some classes of regular events
• The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
• Equations and monoid varieties of dot-depth one and two
• scientific article; zbMATH DE number 7407796 (Why is no real title available?)
• Polynomial closure and unambiguous product
• Programs over semigroups of dot-depth one
• Games, equations and the dot-depth hierarchy
• Imre Simon: an exceptional graduate student
• Polynomial closure and unambiguous product
• Locally countable pseudovarieties
• Catégories et langages de dot-depth un
• A conjecture on the concatenation product
• Varieties of finite categories
• On varieties of rational languages and variable length codes. II
• Concatenation hierarchies: new bottle, old wine
• Equations and dot-depth one
• Characterizing level one in group-based concatenation hierarchies
• scientific article; zbMATH DE number 7533353 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3673124)