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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Patrick Blackburn and Wilfried Meyer-Viol, 1994, “Linguistics, logic, and finite trees,”Bulletin of the IGPL,2, 3–29.
Patrick Blackburn, Claire Gardent, and Wilfried Meyer-Viol, (1993), “Talking about trees,” pp. 21–29, inProceedings of the 6th Conference of the EACL, European Chapter of the Association for Computational Linguistics.
Thomas Longacre Cornell, (1992),Description Theory, Licensing Theory, and Principle-Based Grammars and Parsers, PhD thesis, University of California Los Angeles.
Bruno Courcelle, (1983), “Fundamental properties of infinite trees,”Theoretical Computer Science 25, 95–169.
Kees Doets, (1989), “Monadic II 11 -theories of II 11 -properties,”Notre Dame Journal of Formal Logic 30(2) 224–240.
John Doner, (1970), “Tree acceptors and some of their applications,”Journal of Computer and System Sciences 4, 406–451.
H.-D. Ebbinghaus, J. Flum, and W. Thomas, (1984),Mathematical Logic. New York: Springer-Verlag.
G. Gazdar, E. Klein, G. Pullum, and I. Sag, (1985),Generalized Phrase Structure Grammar. Basil Blackwell.
James Henderson, (1990), “Structure Unification Grammar: A unifying framework for investigating natural language,” Master's thesis, University of Pennsylvania, Phila., PA.
Mark Johnson, (1989), “The use of knowledge of language,”Journal of Psycholinguistic Research 18(1), 105–128.
Richard S. Kayne, (1981), “Unambiguous paths,” pp. 143–183,in Levels of Syntactic Representation, R. May and J. Koster, eds, Dordrecht: Foris.
Richard S. Kayne, (1994),The Antisymmetry of Syntax. Cambridge, MA: MIT Press.
Marcus Kracht, (1993), “Mathematical aspects of command relations,” inProceedings of the 6th Conference of the EACL. European Chapter of the Association for Computational Linguistics.
Michael J. Maher, (1988), “Complete axiomatizations of the algebras of finite, rational and infinite trees,” pp. 348–357, inProceedings of the 3rd Annual Symposium on Logic in Computer Science, Scotland: Edinburgh.
Mitchell P. Marcus, Donald Hindle, and Margaret M. Fleck, (1983), “D-theory: Talking about talking about trees,” inProceedings of the 21st Annual Meeting of the Association for Computational Linguistics.
Barbara Partee, Alice ter Meulen, and Robert Wall, (1990),Mathematical Methods in Linguistics, volume 20 ofStudies in Linguistics and Philosophy. Kluwer Academic Publishers, Dordrecht, 1990.
Michael O. Rabin, (1969), “Decidability of second-order theories and automata on infinite trees,”Transactions of the American Mathematical Society 141, 1–35.
James Rogers and K, Vijay-Shanker, (1994), “Obtaining trees from their descriptions: An application to Tree-Adjoining Grammars,”Computational Intelligence 10, 401–421.
James Rogers, (1994),Studies in the Logic of Trees with Applications to Grammar Formalisms. Ph.D. dissertation, University of Delaware.
Dirk Siefkes, (1978), “An axiom system for the weak monadic second order theory of two successors,”Israel Journal of Mathematics 30(3), 264–284.
Edward P. Stabler, Jr., 1992,The Logical Approach to Syntax, Bradford.
K. Vijay-Shanker, 1992, “Using descriptions of trees in a Tree-Adjoining Grammar,”Computational Linguistics 18(4), 481–517.
Author information
Authors and Affiliations
Additional information
The research reported in this paper has been supported by the Bundesminister für Forschung und Technologie under contract ITW 01 IV 101 K/1 (Verbmobil).
Part of this work was done during the period when this author was at DFKI, Saarbrücken. This author would like to thank Prof. Dr. H. Uszkoreit and Prof. Dr. W. Wahlster for providing the facilities and a supportive environment.
Rights and permissions
About this article
Cite this article
Backofen, R., Rogers, J. & Vijay-Shanker, K. A first-order axiomatization of the theory of finite trees. J Logic Lang Inf 4, 5–39 (1995). https://doi.org/10.1007/BF01048403
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01048403