A complete axiomatization for Blocks World
Blocks World (BW) has been one of the most popular model domains in At history. However, there has not been serious work on axiomatizing the state constraints of BW and giving justification for its soundness and completeness, In this paper, we model a state of BW by a finite collection of finite chains, and call the theory of all these structures BW theory. We present seven simple axioms and prove that their consequences are precisely BW theory, using Ehrenfeucht-Fraisse games. We give a simple decision procedure for the theory which can be implemented in exponential space, and prove that every decision procedure (even if nondeterministic) for the theory must take at least exponential time. We also give a characterization of all nonstandard models for the theory. Finally, we present an expansion of BW theory and show that it admits elimination of quantifiers. As a result, we are able to characterize all definable predicates in BW theory, and give simple examples of undefinable predicates.
blocks world ehrenfeucht-fraisse games definable predicates finite axiomatization complexity of logical theories