A first-order axiomatization of the theory of finite trees

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

Abstract

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

Categories

Keywords

Reprint years

DOI

10.1007/bf01048403

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,127

External links

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

Through your library

My notes

Similar books and articles

Classes and theories of trees associated with a class of linear orders.Valentin Goranko & Ruaan Kellerman - 2011 - Logic Journal of the IGPL 19 (1):217-232.
Approximating trees as coloured linear orders and complete axiomatisations of some classes of trees.Ruaan Kellerman & Valentin Goranko - 2021 - Journal of Symbolic Logic 86 (3):1035-1065.
First-order theories of bounded trees.Ruaan Kellerman - 2021 - Archive for Mathematical Logic 61 (1):263-297.
Axiomatization of a Branching Time Logic with Indistinguishability Relations.Alberto Gatto - 2016 - Journal of Philosophical Logic 45 (2):155-182.
Linguistics, Logic and Finite Trees.Patrick Blackburn & Wilfried Meyer-Viol - 1994 - Logic Journal of the IGPL 2 (1):3-29.
Tree Theory: Interpretability Between Weak First-Order Theories of Trees.Zlatan Damnjanovic - 2023 - Bulletin of Symbolic Logic 29 (4):465-502.
PDL for ordered trees.Loredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrand Gaiffe, Evan Goris, Maarten Marx & Maarten de Rijke - 2005 - Journal of Applied Non-Classical Logics 15 (2):115-135.
Finite Trees in Tense Logic.Bellissima Fabio & Cittadini Saverio - 1999 - Studia Logica 62 (2):121-140.
Definability in the h -quasiorder of labeled forests.Oleg V. Kudinov, Victor L. Selivanov & Anton V. Zhukov - 2009 - Annals of Pure and Applied Logic 159 (3):318-332.
Mereology and Infinity.Karl-Georg Niebergall - 2016 - Logic and Logical Philosophy 25 (3):309-350.

Analytics

Added to PP
2009-01-28

Downloads
8 (#1,345,183)

6 months
82 (#64,618)

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. kluwer. 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

Generalized Phrase Structure Grammar.G. Gazdar, E. Klein, G. Pullum & I. Sag - 1987 - Linguistics and Philosophy 10 (3):389-426.
Linguistics, Logic and Finite Trees.Patrick Blackburn & Wilfried Meyer-Viol - 1994 - Logic Journal of the IGPL 2 (1):3-29.
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