AROUND DOT-DEPTH ONE

DOI10.1142/S0129054112400552zbMath1308.68071OpenAlexW1750190114MaRDI QIDQ4923283

Alexander Lauser, Manfred Kufleitner

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

first-order logicdot-depth hierarchyfinite semigroupstar-free languagequantifier alternation

Mathematics Subject Classification ID

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

Related Items

The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Stone duality, topological algebra, and recognition.

Cites Work

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