On a hierarchy involving transitive closure logic and existential second-order quantification
From MaRDI portal
Publication:3147357
DOI10.1093/jigpal/9.6.769zbMath1001.03036MaRDI 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 logic; Ehrenfeucht-Fraïssé game; finite model theory; descriptive complexity; transitive closure logic
03B70: Logic in computer science
03C13: Model theory of finite structures
68Q19: Descriptive complexity and finite models