A first-order axiomatization of the theory of finite trees

Journal of Logic, Language and Information 4 (1):5-39 (1995)
  Copy   BIBTEX


We provide first-order axioms for the theories of finite trees with bounded branching and finite trees with arbitrary (finite) branching. The signature is chosen to express, in a natural way, those properties of trees most relevant to linguistic theories. These axioms provide a foundation for results in linguistics that are based on reasoning formally about such properties. We include some observations on the expressive power of these theories relative to traditional language complexity classes



    Upload a copy of this work     Papers currently archived: 91,998

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

81 (#206,942)

6 months
7 (#431,609)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Language, Lambdas, and Logic.Reinhard Muskens - 2003 - In R. Oehrle & J. Kruijff (eds.), Resource Sensitivity, Binding, and Anaphora (Studies in Linguistics and Philosophy 80). Dordrecht: Kluwer Academic Publishers. pp. 23--54.
Categorial Grammar and Lexical-Functional Grammar.Reinhard Muskens - 2001 - In Miriam Butt & Tracey Holloway King (eds.), Proceedings of the LFG01 Conference, University of Hong Kong. Stanford, CA: CSLI Publications. pp. 259-279.
First-order theories of bounded trees.Ruaan Kellerman - 2021 - Archive for Mathematical Logic 61 (1):263-297.

View all 15 citations / Add more citations

References found in this work

Linguistics, Logic and Finite Trees.Patrick Blackburn & Wilfried Meyer-Viol - 1994 - Logic Journal of the IGPL 2 (1):3-29.
Generalized Phrase Structure Grammar.G. Gazdar, E. Klein, G. Pullum & I. Sag - 1987 - Linguistics and Philosophy 10 (3):389-426.
Monadic $\Pi^11$-theories of $\Pi1^1$}-properties.Kees Doets - 1989 - Notre Dame Journal of Formal Logic 30 (2):224-240.

View all 8 references / Add more references