An operational and denotational approach to non-context-freeness
conference paper
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. © 2002 Elsevier Science B.V. All rights reserved.
Topics
TNO Identifier
280277
ISSN
03043975
Source title
Algebraic Methods in Language Processing, 20 May 2000 through 22 May 2000, Iowa City, IA. Conference code: 60650
Editor(s)
Nijholt A.
Scollo G.
Heylen D.
Scollo G.
Heylen D.
Pages
261-289
Files
To receive the publication files, please send an e-mail request to TNO Repository.