TAILIEUCHUNG - Báo cáo khoa học: "RECOGNITION OF LINEAR CONTEXT-FREE REWRITING SYSTEMS*"

The class of linear context-free rewriting systems has been introduced as a generalization of a class of grammar formalisms known as mildly context-sensitive. The recognition problem for linear context-free rewriting languages is studied at length here, presenting evidence that, even in some restricted cases, it cannot be solved efficiently. This entails the existence of a gap between, for example, tree adjoining languages and the subclass of linear context-free rewriting languages that generalizes the former class; such a gap is attributed to "crossing configurations". A few other interesting consequences of the main result are discussed, that concern the recognition problem. | RECOGNITION OF LINEAR CONTEXT-FREE REWRITING SYSTEMS Giorgio Satta Institute for Research in Cognitive Science University of Pennsylvania Philadelphia PA 19104-6228 USA gsatt a@linc .cis. upenn .edu ABSTRACT The class of linear context-free rewriting systems has been introduced as a generalization of a class of grammar formalisms known as mildly context-sensitive. The recognition problem for linear context-free rewriting languages is studied at length here presenting evidence that even in some restricted cases it cannot be solved efficiently. This entails the existence of a gap between for example tree adjoining languages and the subclass of linear context-free rewriting languages that generalizes the former class such a gap is attributed to crossing configurations . A few other interesting consequences of the main result are discussed that concern the recognition problem for linear context-free rewriting languages. 1 INTRODUCTION Beginning with the late 70 s there has been a considerable interest within the computational linguistics field for rewriting systems that enlarge the generative power of context-free grammars CFG both from the weak and the strong perspective still remaining far below the power of the class of contextsensitive grammars CSG . The denomination of mildly context-sensitive MCS has been proposed for the class of the studied systems see Joshi et al 1991 for discussion . The rather surprising fact that many of these systems have been shown to be weakly equivalent has led researchers to generalize 1 am indebted to Anuj Dawar Shyam Kapur and Owen Rambow for technical discussion on this work. I am also grateful to Aravind Joshi for his support in this research. None of these people is responsible for any error in this work. This research was partially funded by the following grants ARO grant DAAL 03-89-C-0031 DARPA grant N00014d r J-1863 NSF grant IRI 90-16592 and Ben Franklin grant . the elementary operations involved in only apparently

Đã 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.