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
DOI
https://dx.doi.org/10.1016/S0304-3975(01)00348-6
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.