Annals of Pure and Applied Logic 161 (3):404-415 (2010)

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Reprint years 2009, 2010
DOI 10.1016/j.apal.2009.07.011
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,577
Through your library

References found in this work BETA

Logic with Denumerably Long Formulas and Finite Strings of Quantifiers.Dana Scott - 1965 - In J. W. Addison (ed.), Journal of Symbolic Logic. Amsterdam: North-Holland Pub. Co.. pp. 1104--329.
Finite Quantifier Equivalence.Carol Karp - 1965 - In J. W. Addison (ed.), Journal of Symbolic Logic. Amsterdam: North-Holland Pub. Co.. pp. 407--412.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Ehrenfeucht-Fraïssé Equivalence of Linear Orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
Comparing the Power of Games on Graphs.Ronald Fagin - 1997 - Mathematical Logic Quarterly 43 (4):431-455.
An Ehrenfeucht‐Fraïssé Game for Lω1ω.Jouko Väänänen & Tong Wang - 2013 - Mathematical Logic Quarterly 59 (4-5):357-370.
An Ehrenfeucht‐Fraïssé Class Game.Wafik Boulos Lotfallah - 2004 - Mathematical Logic Quarterly 50 (2):179-188.
On Potential Isomorphism and Non-Structure.Taneli Huuskonen, Tapani Hyttinen & Mika Rautila - 2004 - Archive for Mathematical Logic 43 (1):85-120.
A First-Order Axiomatization of the Theory of Finite Trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.


Added to PP index

Total views
11 ( #858,866 of 2,533,586 )

Recent downloads (6 months)
1 ( #390,861 of 2,533,586 )

How can I increase my downloads?


My notes