TAILIEUCHUNG - Báo cáo khoa học: "COMPUTATIONAL COMPLEXITY OF CURRENT GPSG THEORY"

An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance, generalized phrase structure grammar (GPSG) appears to be a blessing on two counts. First, the precise formalisms of GPSG might be a direct and fransparent guide for parser design and implementation. Second, since GPSG has weak context-free generative power and context-free languages can be parsed in O(n ~) by a wide range of algorithms, GPSG parsers would appear to run in polynomial time. This widely-assumed GPSG "efficient parsability" result is misleading: here. | COMPUTATIONAL COMPLEXITY OF CURRENT GPSG THEORY Eric Sven Ristad MIT Artificial Intelligence Lab 545 Technology Square Cambridge MA 02139 Thinking Machines Corporation and 245 First Street Cambridge MA 02142 ABSTRACT An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance generalized phrase structure grammar GPSG appears to be a blessing on two counts. First the precise formalisms of GPSG might be a direct and transparent guide for parser design and implementation. Second since GPSG has weak context-free generative power and context-free languages can be parsed in o n2 3 by a wide range of algorithms GPSG parsers would appear to run in polynomial time. This widely-assumed GPSG efficient parsability result is misleading here we prove that the universal recognition problem for current GPSG theory is exponential-polynomial time hard and assuredly intractable. The paper pinpoints sources of complexity . metarules and the theory of syntactic features in the current GPSG theory and concludes with some linguistically and computationally motivated restrictions on GPSG. 1 Introduction An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. Generalized Phrase Structure Grammar GPSG linguistic theory holds out considerable promise as an aid in this task. The precise formalisms of GPSG offer the prospect of a direct and transparent guide for parser design and implementation. Furthermore and more importantly GPSG s weak context-free generative power suggests an efficiency advantage for GPSG-based parsers. Since context-free languages can be parsed in polynomial time it seems plausible that GPSGs can also be parsed in polynomial time. This would in turn seem to provide the beginnings of an explanation for the

• Báo cáo khoa học
• COMPUTATIONAL COMPLEXITY
• CURRENT GPSG THEORY
• Eric Sven
• scientific reports
• model language
• process natural language
• Computational complexity theory
• Basic complexity classes
• The computational model
• Non deterministic Turing machines
• The Cook Levin Theorem
• Time Hierarchy Theorem
• Communication complexity
• Algebraic computation models
• Circuit lower bounds
• The Blum Shub Smale Model
• On the Computational Complexity
• Dominance Links
• Grammatical Formalisms
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• TWO LEVEL MORPHOLOGY
• G
• Edward Barton
• THE COMPUTATIONAL COMPLEXITY
• AVOIDING CONVERSATIONAL IMPLICATURES
• Ehud Reiterf
• Statistical Machine Translation
• Raghavendra Udupa
• Lecture Data Structures and Algorithms
• Data Structures and Algorithms
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Complexity of Algorithms
• Control structures
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• Time complexity of algorithms
• Asymptotic notations
• expand and improve
• recruit a highly
• skilled and educated
• efforts depend
• community and creating
• attractive business
• BMC Bioinformatics
• Network analysis
• Complexity measure
• Computational algorithm
• Fractal dimension
• Human brain application
• Functional connectivity
• Fundamental data structures
• Cấu trúc dữ liệu và giải thuật
• Analyze the computational complexity
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• computer engineering
• electrical engineering
• computer organization
• digital logic design
• Computer Architecture
• Language Architecture
• SAT Modulo Theories
• Computational Finance
• Algebra
• Logic
• and Complexity
• Distinguished Papers
• medical analysis
• environmental medicine
• raccoon experiments
• medical knowledge
• medical research
• báo cáo hóa học
• công trình nghiên cứu về hóa học
• tài liệu về hóa học
• Basics of algorithms
• Numeric calculation
• design algorithms
• Physical data design
• program design
• Approximation algorithms
• Heuristic computation
• Heuristic methods
• NP hard problems
• Diameter constrained reliability
• Graph theory
• Non failed links
• Motifs discovery
• PPI interaction network
• Food web network
• Network compression
• Lecture Algorithms
• Bài giảng Thuật toán
• Bottom up mergesort
• Sorting complexity
• Computational infrastructure
• Robot localization
• Computational geometry
• Algorithm complexity
• Approximation algorithm
• Polygon triangulation
• Logging Operations
• Perspective on Membership
• Private Forest
• Owner Cooperative
• Economic Feasibility
• Agroforestry System