Finite-State Methods and Natural Language Processing: 8th International Workshop, FSMNLP 2009, Pretoria, South Africa, July 21-24, 2009, Revised ... (Lecture Notes in Computer Science, 6062)

This book constitutes the refereed proceedings of the 8th International Workshop on the Finite-State-Methods and Natural Language Processing, FSMNLP 2009. The workshop was held at the University of Pretoria, South Africa on July 2009. In total 21 papers were submitted and of those papers 13 were accepted as regular papers and a further 6 as extended abstracts. The papers are devoted to computational morphology, natural language processing, finite-state methods, automata, and related formal language theory. Title Preface Organization Table of Contents Tutorials Learning Finite State Machines Introduction Some of the Key Ideas You Can’t ‘Have Learnt’ Identification in the Limit Complexity Matters Some Basic Tools Three Types of States The Prefix Tree Acceptor ($P_TA$) Red, Blue and White States Merge and Fold Some Techniques and Results $D_FA$ and $N_FA$ Probabilistic Automata Transducers Some Open Problems and Challenges References Special Theme Tutorials Developing Computational Morphology for Low- and Middle-Density Languages What Is Computational Morphology? Contents of the Tutorial Links Invited Papers $f$sm2 – A Scripting Language Interpreter for Manipulating Weighted Finite-State Automata Introduction Formal Background Featuresof $fsm2$ Supported Semirings Algebraic Operations Equivalence Transformations Symbolic Formalism Input/Output Scripts Special Features Macros Language Modeling Further Directions References Appendix Selected Operations and Applications of n-Tape Weighted Finite-State Machines Introduction Definitions Operations Simple Operations Join Operation Auto-intersection Compilation of Auto-intersection Post’s Correspondence Problem A Class of Rational Auto-intersections An Auto-intersection Algorithm Applications Morphological Analysis of Semitic Languages Intermediate Results in Transduction Cascades Induction of Morphological Rules String Alignment for Lexicon Construction Acronym and Meaning Extraction Cognate Search Conclusion References OpenFst Special Theme Invited Talks Morphological Analysis of Tone Marked Kinyarwanda Text Introduction The Characteristics of Tones Tone in Computational Morphology The Structure of This Paper Characteristics of the Kinyarwanda Language General Facts The Underspecific Orthography Manifestation of Tones in Verbs Implementation of Tone Handling Rules Evaluation Test Corpus Metrics Comparison with the Orthographic Analyser Conclusion References Regular Papers Minimizing Weighted Tree Grammars Using Simulation Introduction Trees and Weighted Tree Grammars Backward Simulation Forward Simulation Conclusion References Compositions of Top-Down Tree Transducers with \epsilon-Rules Introduction Notation Top-Down Tree Transducers with Top-Down Tree Transducers with \epsilon-Rules Separating Output Symbols Composition Construction Conclusions and Open Problems References Reducing Nondeterministic Finite Automata with SAT Solvers Introduction Related Work Reduction Algorithm Initial State Constraints Final State Constraints Transition Constraints Additional Constraints The Size of the SAT Problem Example Reduction v. Minimization Experimental Results Conclusion References Joining Composition and Trimming of Finite-State Transducers Introduction Preliminaries Composition Depth-First Composition Acyclic Case General Case Complexity Experiment Conclusion References Special Theme Extended Abstracts Porting Basque Morphological Grammars to foma, an Open-Source Tool Introduction Basque Morphology Earlier Work and Current Migration to Open Source Porting Basque Grammars to Foma Conversion Procedure Compatibility and Efficiency Auxiliary Applications: Spelling Correction Internal Support for Spelling Correction in Foma Conclusion References Describing Georgian Morphology with a Finite-State System Introduction Analyzing the Morphology of Georgian The Structure of Nouns, Adjectives and Pronouns The Verb System of Georgian Finite-State Implementation Overview Approach Evaluation Future Plans Supporting the Non-Roman Script Shallow Parsing Integration to Other Resources References Finite State Morphology of the Nguni Language Cluster: Modelling and Implementation Issues Introduction Morphology of the Nguni Cluster of Languages Overview Typical Constraints Approach for Zulu Modelling and Implementation Bootstrapping for Xhosa, Swati and Ndebele Conclusion and Future Work References A Finite State Approach to Setswana Verb Morphology Introduction Overview of Setswana Verb Morphology Affixes of the Setswana Verb Auxiliary Verbs and Copulatives Formation of Verbs TheVerbAnalyser From Text to Tokens Two Tokenising Transducers Application and Results Conclusion and Future Work References Competition Announcements Zulu: An Interactive Learning Competition Introduction, Motivations, History and Background A Brief Overview of Zulu Other Related Competitions A More Complete Presentation of Zulu Registration Phase Training Phase Competition Phase Discussion References Author Index