Separating regular languages with two quantifiers alternations

DOI10.1109/LICS.2015.28MaRDI QIDQ4635804zbMATH OpenOpenAlexFDO

Authors Thomas Place

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2015.28

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Quantifier alternation for infinite words
• Quantifier alternation in two-variable first-order logic with successor is decidable
• Alternation hierarchies of first order logic with regular predicates

Cited in

(17)

• Separating regular languages with two quantifier alternations
• On upper and lower bounds on the length of alternating towers
• Covering and separation for logical fragments with modular predicates
• Complexity of universality and related problems for partially ordered NFAs
• Varieties
• On All Things Star-Free
• Separating Without Any Ambiguity.
• Generic results for concatenation hierarchies
• Separating regular languages with first-order logic
• Alternation hierarchies of first order logic with regular predicates
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• On decidability of intermediate levels of concatenation hierarchies
• Quantifier alternation for infinite words
• The covering problem
• Concatenation hierarchies: new bottle, old wine
• Separating regular languages with first-order logic

This page was built for publication: Separating regular languages with two quantifiers alternations

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