Monadic Second-Order Logic and Transitive Closure Logics over Trees
| Autor: | Stephan Kepser, Hans Joerg Tiede |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Linguistics and Language
Theoretical computer science General Computer Science derivation tree media_common.quotation_subject Descriptive complexity theory Theoretical Computer Science Computer Science::Logic in Computer Science Computer Science (miscellaneous) media_common Mathematics natural language Discrete mathematics Grammar Monadic second order logic model theoretic syntax Transitive closure Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Rotation formalisms in three dimensions Syntax Cross-serial dependencies descriptive complexity TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES transitive closure logic Tree (set theory) Natural language Computer Science(all) |
| Zdroj: | Electronic Notes in Theoretical Computer Science. 165:189-199 |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2006.05.044 |
| Popis: | Model theoretic syntax is concerned with studying the descriptive complexity of grammar formalisms for natural languages by defining their derivation trees in suitable logical formalisms. The central tool for model theoretic syntax has been monadic second-order logic (MSO). Much of the recent research in this area has been concerned with finding more expressive logics to capture the derivation trees of grammar formalisms that generate non-context-free languages. The motivation behind this search for more expressive logics is to describe formally certain mildly context-sensitive phenomena of natural languages. Several extensions to MSO have been proposed, most of which no longer define the derivation trees of grammar formalisms directly, while others introduce logically odd restrictions. We therefore propose to consider first-order transitive closure logic. In this logic, derivation trees can be defined in a direct way. Our main result is that transitive closure logic, even deterministic transitive closure logic, is more expressive in defining classes of tree languages than MSO. (Deterministic) transitive closure logics are capable of defining non-regular tree languages that are of interest to linguistics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect