TAILIEUCHUNG - Báo cáo khoa học: "On the Mathematical Properties of Linguistic Theories"

Meta-theoretical results on the decidability, generatire capacity, and recognition complexity o~ several syntactic theories are surveyed These include context-free , lexical func-computer o r a parallel array of neurons. These results over whole classes of machines are very difficult to obtain, and none el any significance exist for problems. Restricting ourselves to a specific machine model and an algorithm M for j', we can ask about the cost. ( time or space) e(z) of executing M on a specific input z. . | On the Mathematical Properties of Linguistic Theories c. Raymond Dept of Computer Science University of Toronto Toronto Ontario Canada M5S 1A4 ABSTRACT Meta-theoretical results on the decidability generative capacity and recognition complexity of several syntactic theories are surveyed. These include context-free grammars transformational grammars lexical functional grammars generalized phrase structure grammars and tree adjunct grammars. 1. Introduction. The development of new formalisms in which to express linguistic theories has been accompanied at least since Chomsky and Miller s early work on context-free languages by the study of their meta-theory. In particular. numerous results on the decidability generative capacity and more recently the complexity of recognition of these formalisms have been published and rumoured strangely enough much less attention seems to have been devoted to a discussion of the significance of these mathematical results. As a preliminary to the panel on formal properties which will address the significance issue it seemed appropriate to survey the existing results. Such is the modest goal of this paper. We will consider context-free languages transformational grammars lexical functional grammars generalized phrase structure grammars and tree adjunct grammars. Although we will not examine them here formal studies of other syntactic theories have been undertaken . Warren 51 for Montague s PTQ 30 . and Bor-gida 7 tor the stratificational grammars of Lamb 25 . There follows a brief summary of some comments in the Literature about related empirical issues but we avoid entirely the issue of whether one theory is more descriptively adequate than another. 2. Preliminary Definitions We assume the reader is familiar with the basic definitions of regular context-free CF context-sensitive CS recursive and recursively enumerable . Languages and with their acceptors as can be found in Some elementary definitions from complexity .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.