Variable free reasoning on finite trees

Abstract : 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.
Type de document :
Communication dans un congrès
Proceedings of Mathematics of Language - MOL-8, Jun 2003, Bloomington, Indiana, USA, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099716
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:40:35
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099716, version 1

Collections

Citation

Patrick Blackburn, Bertrand Gaiffe, Maarten Marx. Variable free reasoning on finite trees. Proceedings of Mathematics of Language - MOL-8, Jun 2003, Bloomington, Indiana, USA, 2003. 〈inria-00099716〉

Partager

Métriques

Consultations de la notice

94