Structure Theorem and Strict Alternation Hierarchy for FO2 on Words

DOI10.1007/978-3-540-74915-8_27zbMath1168.03328OpenAlexW1569275717MaRDI QIDQ3608423

Philipp Weis, Neil Immerman

Publication date: 5 March 2009

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74915-8_27

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 (2)

On FO 2 Quantifier Alternation over Words ⋮ On Simon's congruence closure of a string

This page was built for publication: Structure Theorem and Strict Alternation Hierarchy for FO2 on Words