Please use this identifier to cite or link to this item:
doi:10.22028/D291-25008
Title: | A first-order axiomatization of the theory of finite trees |
Author(s): | Backofen, Rolf Rogers, James Vijay-Shanker, K. |
Language: | English |
Year of Publication: | 1995 |
OPUS Source: | Kaiserslautern ; Saarbrücken : DFKI, 1995 |
SWD key words: | Künstliche Intelligenz |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-38181 hdl:20.500.11880/25064 http://dx.doi.org/10.22028/D291-25008 |
Series name: | Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x] |
Series volume: | 95-05 |
Date of registration: | 5-Jul-2011 |
Faculty: | SE - Sonstige Einrichtungen |
Department: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
RR_95_05.pdf | 17,23 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.