Around dot-depth one

DOI10.1142/S0129054112400552MaRDI QIDQ4923283zbMATH OpenOpenAlexFDO

Authors Manfred Kufleitner, Alexander Lauser

Publication date 6 June 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054112400552

zbMATH Keywords

dot-depth hierarchyfinite semigroupfirst-order logicquantifier alternationstar-free language

Mathematics Subject Classification ID

Classical first-order logic (03B10) Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Recommendations

• Around dot-depth one
• The dot-depth hierarchy, 45 years later
• scientific article; zbMATH DE number 1500543
• Some logical characterizations of the dot-depth hierarchy and applications
• scientific article; zbMATH DE number 1747443

Cites work

• A generalization of the Schützenberger product of finite monoids
• Categories as algebra: An essential ingredient in the theory of monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Dot-depth of star-free events
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Factorization forests of finite height
• Finite semigroup varieties of the form V*D
• Languages and scanners
• Languages of dot-depth 3/2
• On finite monoids having only trivial subgroups
• Piecewise testable languages via combinatorics on words
• Polynomial closure and unambiguous product
• The dot-depth hierarchy of star-free languages is infinite
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS

Cited in

(14)

• Separability by piecewise testable languages is \textsc{PTime}-complete
• Some logical characterizations of the dot-depth hierarchy and applications
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Around dot depth two
• scientific article; zbMATH DE number 2080228 (Why is no real title available?)
• The dot-depth hierarchy, 45 years later
• scientific article; zbMATH DE number 3999320 (Why is no real title available?)
• Separation for dot-depth two
• Separation for dot-depth two
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Around dot-depth one
• Stone duality, topological algebra, and recognition.
• Relativized adjacency
• Dot-depth three, return of the j-class

This page was built for publication: Around dot-depth one

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