Cross-Serial Dependencies Are Not Hard to Process

Cross-Serial Dependencies Are Not Hard to Process Carl Vogel Ulrike Hahn Holly Branigan Institute for Computational Department of Experimental Centre for Cognitive Science Linguistics University of Stuttgart Azenbergstr. 12 D-70174 Stuttgart Germany Psychology University of Oxford South Parks Road Oxford OX1 3UD England University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW Scotland {vogel,holly,ueh}~cogsci.ed.ac.uk Abstract Cross-serial dependencies in Dutdl and Swiss-German are the only known extra- context fi'ee natural language syntactic phenonmna. Psycholinguistie evidence suggests cross-serial orderings tend to be easier to process t, lmn nested cons[,ruc- |iions. We, argue thai; |;tie expressivity re- quirements of the corresponding formal languages do not actually entail |;hat pro- cessing reduplication languages require the worst-ease time complexity for lmi- guages of the same expressive class. We dist;inguish between context-free repre- sentability and contc, xt-free processing. We show that for any language with up to context fl'ee expressive power, pro- cessing cross-scriM dependencies can be accommodated without atfect;ing tmrsing complexil,y. This is relal,ed to other work on reduplication phenonmna in formal models of computation. 1 Introduction The cross-serial dependencies in Dutch and Swiss- German are the only known constituent-h;vel syn- tacl;ic phenomena whMl make natural languages not representable in con|,ext fi'ee languages (Gaz- dar, 198,5; Gazdar mid Pullum, 1985). Psycholin- guistic s~,udy of the cross-scriM dependencies re- veals thai; tim cross-serial orderings tend to be preferred over nested constructions (Bach eL al., 1986)} Bach et al. argue Dora this dmt tim push- down stack cannot be the universal basis of the human parsing mechanism (since the pushdown automaton is essentially a context free recognil, ion device whidt cannot represent cross-serial depen- dencies). Stabler (1994), on the other hand, con- siders t;tm findings of Bach el; al. (1986) as evi- dence for finite hunian sentence processing capac- ity. In l, his paper, we dist, inguish between conl,ext- fi'ee representability and context-fl'ee processing. 1Nested constructions are a quintessentially con- text free phenomenon. We show that for any language with up to con- text fi'ee expressive power, processin9 cross-serial dependencies can be accommodated without af- fecting parsing complexity. While this does essen- tially inflme the language with indexed expressiv- ity, it does so while allowing us to rc~ain eollt,ext free (or even regular) parsing eonqJexity. Ess~'n- tially, il; is possible t,o carve oul; a cross-section of l,he expressivity hierarchy with dm dcaircd pro- cessing complexity. The result is based oil the sim- ple observation that t,he cross-serial dependencies m'e idealized by the string duplication language (whereas the nested dependencies m'e idealized by the palindrome language), and that it is t, rivial to provide a context-free (or regular) language parse for half of the st;ring, followed by a Lest: of equal- il,y for the remaining half of the string. This is consis(,ent; with tindings that cross-serial depen- dencies are not; hard to process, but qualilies the interpret;ation that Bach el; al. give to their re- suits and l,he implications on the human parsing niechanism, hi parl;icular, this suggests thai, with ml addil, ional operation |tie pushdown stack can …

Content truncated to 500 words