On complexity of Ehrenfeucht–Fraïssé games |
| |
Authors: | Bakhadyr Khoussainov Jiamou Liu |
| |
Affiliation: | aDepartment of Computer Science, University of Auckland, Auckland, New Zealand |
| |
Abstract: | 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: | Finite model theory Ehrenfeucht– Fraï ssé game Computation complexity |
本文献已被 ScienceDirect 等数据库收录! |
|