Going Higher in the First-Order Quantifier Alternation Hierarchy on Words

DOI10.1007/978-3-662-43951-7_29zbMath1407.03055arXiv1404.6832OpenAlexW209374521MaRDI QIDQ5167850

Thomas Place, Marc Zeitoun

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10)

Related Items (29)

On Decidability of Intermediate Levels of Concatenation Hierarchies ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Level two of the quantifier alternation hierarchy over infinite words ⋮ Unnamed Item ⋮ Concatenation hierarchies: new bottle, old wine ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Unnamed Item ⋮ Separating Without Any Ambiguity. ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ Unnamed Item ⋮ Pro-aperiodic monoids via saturated models ⋮ Local testability from words to traces, a suitable definition ⋮ Unnamed Item ⋮ Quantifier Alternation for Infinite Words ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ On All Things Star-Free ⋮ Generic results for concatenation hierarchies ⋮ Unnamed Item ⋮ The Quantifier Alternation Hierarchy of Synchronous Relations ⋮ Varieties ⋮ Profinite topologies ⋮ The factorisation forest theorem

This page was built for publication: Going Higher in the First-Order Quantifier Alternation Hierarchy on Words