Article ID Journal Published Year Pages File Type
9657780 Theoretical Computer Science 2005 19 Pages PDF
Abstract
Our proof techniques are based on the characterization of the quantifier rank as the length of the Ehrenfeucht game on non-isomorphic graphs. We use the separator theorems to design a winning strategy for Spoiler in this game.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The first order definability of graphs with separators via the Ehrenfeucht game
Authors
,