scientific article; zbMATH DE number 3827223

zbMATH Open0522.68063MaRDI QIDQ3673124FDOQ3673124

Authors: R. Knast 

Publication date: 1983

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

Title of this publication is not available (Why is that?)

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

• Title not available (Why is that?)
• 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
• Separating regular languages with two quantifier alternations
• Theme and variations on the concatenation product
• Some results on the dot-depth hierarchy
• Profinite categories, implicit operations and pseudovarieties of categories
• Title not available (Why is that?)
• 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
• The product of rational languages
• Generic results for concatenation hierarchies
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Robert Knast (1940-1994)
• A property of the Schützenberger product
• Languages polylog-time reducible to dot-depth 1/2
• Algebraic tools for the concatenation product.
• Locality and Centrality: The Variety ZG
• The globals of pseudovarieties of ordered semigroups containingB₂and an application to a problem proposed by Pin
• Characterizations of some classes of regular events
• Title not available (Why is that?)
• Equations and monoid varieties of dot-depth one and two
• 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
• Alternation Hierarchies of First Order Logic with Regular Predicates
• 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
• Title not available (Why is that?)
• Characterizing level one in group-based concatenation hierarchies

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)