HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:40:35 AM
Last modification on : Friday, February 4, 2022 - 3:30:17 AM


  • HAL Id : inria-00099716, version 1



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



Record views