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 .

• Báo cáo khoa học
• MIX Is Not a Tree Adjoining Language
• Makoto Kanazawa
• Long Papers
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball