Games on Trees and Syntactical Complexity of Formulas

DOI10.1093/JIGPAL/JZM051MaRDI QIDQ5436997zbMATH OpenOpenAlexFDO

Authors Michał Krynicki, Jose Maria Turull Torres

Publication date 18 January 2008

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/jigpal/jzm051

zbMATH Keywords

definabilityEhrenfeucht-Fraisse gamesgames on treessyntactical complexity

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13) Database theory (68P15) Games involving graphs (91A43)

Recommendations

• On complexity of Ehrenfeucht-Fraïssé games
• On Complexity of Ehrenfeucht-Fraïssé Games
• On winning Ehrenfeucht games and monadic NP
• scientific article; zbMATH DE number 1678371
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)

Cited in

(17)

• First-order provenance games
• Tree canonization and transitive closure
• Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
• On distinguishing sets of structures by first-order sentences of minimal quantifier rank
• scientific article; zbMATH DE number 1678371 (Why is no real title available?)
• Measure Properties of Game Tree Languages
• An extension of the Ehrenfeucht-Fraïssé game for first order logics augmented with Lindström quantifiers
• scientific article; zbMATH DE number 4008381 (Why is no real title available?)
• On Some Applications of Games for Härtig Quantifier
• scientific article; zbMATH DE number 1342211 (Why is no real title available?)
• scientific article; zbMATH DE number 1136084 (Why is no real title available?)
• scientific article; zbMATH DE number 219196 (Why is no real title available?)
• An n! lower bound on formula size
• Computer Science Logic
• On Complexity of Ehrenfeucht-Fraïssé Games
• On n-equivalence of binary trees
• On complexity of Ehrenfeucht-Fraïssé games

This page was built for publication: Games on Trees and Syntactical Complexity of Formulas

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