The key tool is proving inexpressibility results in finite-model theory is Ehrenfeucht-Fraisse games. This paper surveys various game-theoretic techniques and tools that lead to simpler proofs of inexpressibility results. The focus is on first-order logic and monadic NP.
By: Ronald Fagin
Published in: RJ10035 in 1996
This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.
Questions about this service can be mailed to reports@us.ibm.com .