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: 92,813

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

On Scott and Karp trees of uncountable models.Tapani Hyttinen & Jouko Väänänen - 1990 - Journal of Symbolic Logic 55 (3):897-908.
Computable categoricity of trees of finite height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
Finite trees and the necessary use of large cardinals.Harvey Friedman - manuscript
On intermediate predicate logics of some finite Kripke frames, I. levelwise uniform trees.Dmitrij Skvortsov - 2004 - Studia Logica 77 (3):295 - 323.
Generalizations of the Kruskal-Friedman theorems.L. Gordeev - 1990 - Journal of Symbolic Logic 55 (1):157-181.
Uniformization, choice functions and well orders in the class of trees.Shmuel Lifsches & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (4):1206-1227.
The decision problem for branching time logic.Yuri Gurevich & Saharon Shelah - 1985 - Journal of Symbolic Logic 50 (3):668-681.
Querying linguistic trees.Catherine Lai & Steven Bird - 2010 - Journal of Logic, Language and Information 19 (1):53-73.
Pseudo-finite homogeneity and saturation.Jörg Flum & Martin Ziegler - 1999 - Journal of Symbolic Logic 64 (4):1689-1699.

Analytics

Added to PP
2009-01-28

Downloads
82 (#208,643)

6 months
8 (#411,218)

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

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