On complexity of Ehrenfeucht-Fraïssé games

DOI10.1016/j.apal.2009.07.011zbMath1221.03024OpenAlexW2065551051MaRDI QIDQ636279

Bakhadyr Khoussainov, Jiamou Liu

Publication date: 26 August 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2009.07.011

zbMATH Keywords

computational complexityEhrenfeucht-Fraïssé gamefinite model theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (2)

Reactive synthesis from interval temporal logic specifications ⋮ On distinguishing sets of structures by first-order sentences of minimal quantifier rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• An Ehrenfeucht-Fraïssé game approach to collapse results in database theory
• On winning strategies in Ehrenfeucht-Fraïssé games
• Infinitary logic and inductive definability over finite structures
• Equivalence in finite-variable logics is complete for polynomial time
• An application of games to the completeness problem for formalized theories
• Computer Science Logic

This page was built for publication: On complexity of Ehrenfeucht-Fraïssé games