• Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich & Frank Morawietz (2000). An Operational and Denotational Approach to Non-Context-Freeness. (abstract, .html), (.ps , 634K), (.ps.gz , 212K). A revised version is to appear in a special issue of Theoretical Computer Science.

Abstract

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.

previous page personal homepage