An operational and denotational approach to non-context-freeness

The main result of this paper is a description of linguistically motivated non-context-free phenomena equivalently in terms of regular tree languages (to express the recursive properties) and both a logical and an operational perspective (to establish the intended linguistic relations). The result i...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2003-02, Vol.293 (2), p.261-289
Main Authors: Kolb, Hans-Peter, Michaelis, Jens, Mönnich, Uwe, Morawietz, Frank
Format: Article
Language:English
Subjects:
MSO logic
Non-context-free phenomena
Tree Grammars
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The main result of this paper is a description of linguistically motivated non-context-free phenomena equivalently in terms of regular tree languages (to express the recursive properties) and both a logical and an operational perspective (to establish the intended linguistic relations). The result is exemplified with a particular non-context-free phenomenon, namely cross-serial dependencies in natural languages such as Swiss German or Dutch. The logical description is specified in terms of binary monadic second-order (MSO) formulas and the operational description is achieved by means of a linear and non-deleting macro tree transducer. Besides giving a grammatical presentation for the regular tree language we shall also specify an implementation in the form of a finite-state (tree) automaton to emphasize the effectivity of our approach.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(01)00348-6