Variable free reasoning on finite trees
Résumé
In this paper we examine three modal languages that have been proposed in the model-theoretic syntax literature for describing finite ordered trees. We compare their expressive power, and then examine a key complexity-theoretic issue: how expensive is it to decide --- given a theory specifying a certain class of trees --- whether a formula describes a model? Our main result is that for two of these languages this problem is EXPTIME-complete.