Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

DOI10.2168/LMCS-5(3:4)2009zbMath1168.03019arXiv0907.0616MaRDI QIDQ3395099

Philipp Weis, Neil Immerman

Publication date: 20 August 2009

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

finite model theorydescriptive complexityEhrenfeucht-Fraïssé gamesalternation hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Temporal logic (03B44) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)

Related Items (14)

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ The word problem for omega-terms over the Trotter-Weil hierarchy ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Conelikes and ranker comparisons ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ Unnamed Item ⋮ Simon's congruence pattern matching ⋮ The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy ⋮ On the lattice of sub-pseudovarieties of DA. ⋮ Two Variable vs. Linear Temporal Logic in Model Checking and Games ⋮ Unnamed Item ⋮ On Simon's congruence closure of a string

This page was built for publication: Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words