Locality and modular Ehrenfeucht-Fraïssé games

DOI10.1016/J.JAL.2011.09.002MaRDI QIDQ420850zbMATH OpenOpenAlexFDO

Authors Achim Blumensath

Publication date 23 May 2012

Published in Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jal.2011.09.002

zbMATH Keywords

first-order logiclocalityEhrenfeucht-Fraïssé games

Mathematics Subject Classification ID

Model theory of finite structures (03C13)

Recommendations

• On complexity of Ehrenfeucht-Fraïssé games
• On Complexity of Ehrenfeucht-Fraïssé Games
• Computer Science Logic
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• Shrinking games and local formulas

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 1059242 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• A model-theoretic characterisation of clique width
• Clique-width of countable graphs: A compactness property.
• Computer Science Logic
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• On winning strategies in Ehrenfeucht-Fraïssé games
• The computational complexity of logical theories
• The first order definability of graphs: Upper bounds for quantifier depth

Cited in

(4)

• The localization game on oriented graphs
• Shrinking games and local formulas
• Game-based notions of locality over finite models
• Computer Science Logic

This page was built for publication: Locality and modular Ehrenfeucht-Fraïssé games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q420850)