TAILIEUCHUNG - Báo cáo khoa học: "Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers*"

We show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output languages of deterministic treewalking transducers. From equivalences that have previously been established we know that this class of languages is also equal to the string languages generated by context-free hypergraph grammars, multicomponent tree-adjoining grammars, and multiple contextfree grammars and to the class of yields of images of the regular tree languages under finite-copying topdown tree transducers. . | Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers David J. Weir School of Cognitive and Computing Sciences University of Sussex Falmer Brighton BN1 9QH davidw@ Abstract We show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output languages of deterministic treewalking transducers. From equivalences that have previously been established we know that this class of languages is also equal to the string languages generated by context-free hypergraph grammars multicomponent tree-adjoining grammars and multiple context-free grammars and to the class of yields of images of the regular tree languages under finite-copying top-down tree transducers. Introduction In 9 a comparison was made of the generative capacity of a number of grammar formalisms. Several were found to share a number of characteristics described below and the class of such formalisms was called linear context-free rewriting systems. This paper shows how the class of string languages generated by linear context-free rewriting systems relates to a number of other systems that have been studied by formal language theorists. In particular we show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output languages of deterministic tree-walking transducers 1 . A number of other equivalences have already been established. In 10 it was shown that linear context-free rewriting systems and multicomponent tree adjoining grammars 6 generate the same string languages. The multiple context-free grammars of 7 are equivalent to linear context-free systems. This follows T would like to thank Joost Engelfriet for drawing my attention to context-free hypergraph grammars and their relationship to deterministic tree-walking automata. from the fact that multiple context-free grammars are exactly that subclass of the linear context-free rewriting systems in .

• Báo cáo khoa học
• Linear Context Free Rewriting Systems
• Deterministic Tree Walking Transducers
• David J
• Weir
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• 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 n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• 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