Separation for dot-depth two

MaRDI QIDQ5155687FDOQ5155687

Authors: Thomas Place, Marc Zeitoun 

Publication date: 8 October 2021

Full work available at URL: https://arxiv.org/abs/1901.03361

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

zbMATH Keywords

wordsfirst-order logicseparationregular languagesmembershipconcatenation hierarchiesquantifier alternation

Mathematics Subject Classification ID

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

Cites Work

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

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)