An Ehrenfeucht-Fraïssé class game

DOI10.1002/malq.200310088zbMath1040.03030MaRDI QIDQ4459599

Wafik Boulos Lotfallah

Publication date: 29 March 2004

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310088

zbMATH Keywords

Henkin quantifier; Ehrenfeucht-Fraïssé game; Ajtai-Fagin game; function quantifier; Logical inexpressibility

Mathematics Subject Classification ID

03B70: Logic in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03C80: Logic with extra quantifiers and operators

03C13: Model theory of finite structures

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03C85: Second- and higher-order model theory

03C52: Properties of classes of models

68Q19: Descriptive complexity and finite models