TAILIEUCHUNG - Báo cáo khoa học: "COMPUTATIONAL COMPLEXITY IN TWO-LEVEL MORPHOLOGY"

Morphological analysis must take into account the spelling-change processes of a language as well as its possible configurations of stems, affixes, and inflectional markings. The computational difficultyof the task can be clarified by investigating specific models of morphological processing. The use of finite-state machinery in the "twolevel" model by K i m m o Koskenniemi gives it the appearance of computational efficiency, but closer examination shows the model does not guarantee efficient processing. Reductions of the satisfiability problem show that finding the proper lexical/surface correspondence in a two-level generation or recognition problem can be computationally difficult. The difficulty increases. | COMPUTATIONAL COMPLEXITY IN TWO-LEVEL MORPHOLOGY G. Edward Barton Jr. . Artificial Intelligence Laboratory 545 Technology Square Cambridge MA 02139 ABSTRACT Morphological analysis must take into account the spelling-change processes of a language as well as its possible configurations of stems affixes and inflectional markings. The computational difficulty of the task can be clarified by investigating specific models of morphological processing. The use of finite-state machinery in the two-level model by Kimmo Koskenniemi gives it the appearance of computational efficiency but closer examination shows the model does not guarantee efficient processing. Reductions of the satisfiability problem show that finding the proper lexical surface correspondence in a two-level generation or recognition problem can be computationally difficult. The difficulty increases if unrestricted deletions null characters are allowed. INTRODUCTION The dictionary lookup stage in a natural-language system can involve much more than simple retrieval. Inflectional endings prefixes suffixes spelling-change processes reduplication non-concatenative morphology and clitics may cause familiar words to show up in heavily disguised form requiring substantial morphological analysis. Superficially it seems that word recognition might potentially be complicated and difficult. This paper examines the question more formally by investigating the computational characteristics of the two-level model of morphological processes. Given the kinds of constraints that can be encoded in two-level systems how difficult could it be to translate between lexical and surface forms Although the use of finite-state machinery in the two-level model gives it the appearance of computational efficiency the model itself does not guarantee efficient processing. Taking the Kimmo system Kart-tunen 1983 for concreteness it will be shown that the general problem of mapping between lexical and surface forms in two-level systems

• Báo cáo khoa học
• COMPUTATIONAL COMPLEXITY
• TWO LEVEL MORPHOLOGY
• G
• Edward Barton
• 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
• CURRENT GPSG THEORY
• Eric Sven
• 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