Separation for dot-depth two

MaRDI QIDQ5155687zbMATH OpenFDO

Authors Thomas Place, Marc Zeitoun

Publication date 8 October 2021

Full work available at URL https://arxiv.org/abs/1901.03361, https://lmcs.episciences.org/8489

zbMATH Keywords

wordsfirst-order logicseparationregular languagesmembershipconcatenation hierarchiesquantifier alternation

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Separation for dot-depth two
• Separating regular languages with two quantifier alternations
• The dot-depth hierarchy, 45 years later
• The Complexity of Separation for Levels in Concatenation Hierarchies
• Around dot-depth one

Cites work

• scientific article; zbMATH DE number 3827223 (Why is no real title available?)
• scientific article; zbMATH DE number 4034007 (Why is no real title available?)
• scientific article; zbMATH DE number 4035179 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• A generalization of the Schützenberger product of finite monoids
• Adding Successor
• An explicit formula for the intersection of two polynomials of regular languages
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Discrete algebraic methods. Arithmetic, cryptography, automata and groups
• Dot-depth of star-free events
• Efficient separability of regular languages by subsequences and suffixes
• First-order logic and star-free sets
• Generic results for concatenation hierarchies
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• On finite monoids having only trivial subgroups
• Polynomial closure and unambiguous product
• Separating regular languages by piecewise testable and unambiguous languages
• Separating regular languages with two quantifier alternations
• Separation for dot-depth two
• The covering problem
• The dot-depth hierarchy of star-free languages is infinite

Cited in

(5)

• All about unambiguous polynomial closure
• First-order separation over countable ordinals
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• Measuring power of locally testable languages
• Characterizing level one in group-based concatenation hierarchies

This page was built for publication: Separation for dot-depth two

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