Going Higher in First-Order Quantifier Alternation Hierarchies on Words

DOI10.1145/3303991zbMath1427.03050arXiv1707.05696OpenAlexW2963241423WikidataQ128243317 ScholiaQ128243317MaRDI QIDQ5244385

Thomas Place, Marc Zeitoun

Publication date: 21 November 2019

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicmembership problemregular languagesdot-depth hierarchyseparation problemStraubing-Thérien hierarchyquantifier alternationdecidable characterizationlogical hierarchies

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13)

Related Items (6)

Positive First-order Logic on Words and Graphs ⋮ First-order separation over countable ordinals ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Difference hierarchies and duality with an application to formal languages ⋮ Unnamed Item ⋮ Characterizing level one in group-based concatenation hierarchies

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