On a hierarchy involving transitive closure logic and existential second-order quantification
From MaRDI portal
Publication:3147357
DOI10.1093/jigpal/9.6.769zbMath1001.03036OpenAlexW2103196177MaRDI QIDQ3147357
Iain A. Stewart, Richard L. Gault
Publication date: 21 October 2002
Published in: Logic Journal of IGPL (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1093/jigpal/9.6.769
monadic second-order logicEhrenfeucht-Fraïssé gamefinite model theorydescriptive complexitytransitive closure logic
Logic in computer science (03B70) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)