zbMATH — the first resource for mathematics

On complexity of Ehrenfeucht-Fraïssé games. (English) Zbl 1133.03013
Artemov, Sergei N. (ed.) et al., Logical foundations of computer science. International symposium, LFCS 2007, New York, NY, USA, June 4–7, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72732-3/pbk). Lecture Notes in Computer Science 4514, 293-309 (2007).
Summary: 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 Ehrenfeucht-Fraïssé problem. Given \(n \in \omega \) as a parameter, two relational structures \(\mathcal A\) and \(\mathcal B\) from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the \(n\)-round EF game \(G_n(\mathcal A,\mathcal B)\)? 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\).
For the entire collection see [Zbl 1121.03005].
Reviewer: Reviewer (Berlin)

03C13 Model theory of finite structures
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI