Frank Morawietz
Seminar für Sprachwissenschaft
Theoretische Computerlinguistik
Neuphilologische Fakultät
Universität Tübingen

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

Descriptions of Cross-Serial Dependencies

30pp., PS (531kb).


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 regular string languages (to establish the intended linguistic relations) and (b) transductions definable in monadic second-order (MSO) logic which are defined on a domain of finite trees that is characterized as the model set of a closed MSO formula. In fact, we shall not deal directly with the two types of regular language families and MSO definable structures, but shall instead consider implementation in the form of finite-state (tree) automata to emphasize the effectivity of our approach.

In case of problems or for comments, please contact:
Last updated: 13-Mar-2000