tailieunhanh - Báo cáo khoa học: "MIX Is Not a Tree-Adjoining Language"

The language MIX consists of all strings over the three-letter alphabet {a, b, c} that contain an equal number of occurrences of each letter. We prove Joshi’s (1985) conjecture that MIX is not a tree-adjoining language. 1 Introduction The language MIX = { w ∈ {a, b, c}∗ | |w|a = |w|b = |w|c } has attracted considerable attention in computational linguistics. | MIX Is Not a Tree-Adjoining Language Makoto Kanazawa National Institute of Informatics 2-1-2 Hitotsubashi Chiyoda-ku Tokyo 101-8430 Japan kanazawa@ Sylvain Salvati INRIA Bordeaux Sud-Ouest LaBRI 351 Cours de la Liberation F-33405 Talence Cedex France Abstract The language MIX consists of all strings over the three-letter alphabet a b c that contain an equal number of occurrences of each letter. We prove Joshi s 1985 conjecture that MIX is not a tree-adjoining language. 1 Introduction The language MIX w e a b c w a w b w c has attracted considerable attention in computational This language was used by Bach 1981 in an exercise to show that the permutation closure of a context-free language is not necessarily MIX may be considered a prototypical example of free word order language but as remarked by Bach 1981 it seems that no human language has such complete freedom for order because typically certain constituents act as boundary domains for scrambling . Joshi 1985 refers to MIX as representing an extreme case of the degree of free word order permitted in a language which is linguistically not relevant . Gazdar 1988 adopts a similar position regarding the relation between MIX 1If w is a string and d is a symbol we write w d to mean the number of occurrences of d in w. We will use the notation w to denote the length of w . the total number of occurrences of symbols in w. 2According to Gazdar 1988 MIX was originally described by Emmon Bach and was so-dubbed by students in the 1983 Hampshire College Summer Studies in Mathematics . According to Bach 1988 the name MIX was the happy invention of Bill Marsh . 666 and natural languages noting that it seems rather unlikely that any natural language will turn out to have a MIX-like characteristic . It therefore seems natural to assume that languages such as MIX should be excluded from any class of formal languages that purports to be a tight formal .