Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Ehrenfeucht-Fraïssé games:
TR06-035 | 19th January 2006
Till Tantau

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

The reachability problem for graphs cannot be described, in the
sense of descriptive complexity theory, using a single first-order
formula. This is true both for directed and undirected graphs, both
in the finite and infinite. However, if we restrict ourselves to
graphs in which a certain graph parameter is fixed ... more >>>

TR07-008 | 27th November 2006
Philipp Weis, Neil Immerman

Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

It is well-known that every first-order property on words is expressible
using at most three variables. The subclass of properties expressible with
only two variables is also quite interesting and well-studied. We prove
precise structure theorems that characterize the exact expressive power of
first-order logic with two variables on words. ... more >>>

TR13-065 | 21st April 2013
Yijia Chen, Joerg Flum

On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

ISSN 1433-8092 | Imprint