An Operational and Denotational Approach to Non-Context-Free Phenomena

Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich and Frank Morawietz

An Operational and Denotational Approach to Non-Context-Free Phenomena

27pp., PS (448kb).

Abstract

The main result of this paper is a description of cross-serial dependencies equivalently in terms of (a) regular tree languages (to express the recursive properties) and (b) both a logical and an operational description (to establish the intended linguistic relations). 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.

In case of problems or for comments, please contact: frank@sfs.uni-tuebingen.de
Last updated: 14-Jul-2000