Finite-state Machine Construction Methods and Algorithms for Phonology and Morphology

Persistent Link:
http://hdl.handle.net/10150/196112
Title:
Finite-state Machine Construction Methods and Algorithms for Phonology and Morphology
Author:
Hulden, Mans
Issue Date:
2009
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
This dissertation is concerned with finite state machine-based technology for modeling natural language. Finite-state machines have proven to be efficient computational devices in modeling natural language phenomena in morphology and phonology. Because of their mathematical closure properties, finite-state machines can be manipulated and combined in many flexible ways that closely resemble formalisms used in different areas of linguistics to describe natural language. The use of finite-state transducers in constructing natural language parsers and generators has proven to be a versatile approach to describing phonological alternation, morphological constraints and morphotactics, and syntactic phenomena on the phrase level.The main contributions of this dissertation are the development of a new model of multitape automata, the development of a new logic formalism that can substitute for regular expressions in constructing complex automata, and adaptations of these techniques to solving classical construction problems relating to finite-state transducers, such as modeling reduplication and complex phonological replacement rules.The multitape model presented here goes hand-in-hand with the logic formalism, the latter being a necessary step to constructing the former. These multitape automata can then be used to create entire morphological and phonological grammars, and can also serve as a neutral intermediate tool to ease the construction of automata for other purposes.The construction of large-scale finite-state models for natural language grammars is a very delicate process. Making any solution practicable requires great care in the efficient implementation of low-level tasks such as converting regular expressions, logical statements, sets of constraints, and replacement rules to automata or finite transducers. To support the overall endeavor of showing the practicability of the logical and multitape extensions proposed in this thesis, a detailed treatment of efficient implementation of finite-state construction algorithms for natural language purposes is also presented.
Type:
text; Electronic Dissertation
Keywords:
computational linguistics; finite state machines; morphology; multitape automata; predicate logic; reduplication in morphology
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Linguistics; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Hammond, Michael
Committee Chair:
Hammond, Michael

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleFinite-state Machine Construction Methods and Algorithms for Phonology and Morphologyen_US
dc.creatorHulden, Mansen_US
dc.contributor.authorHulden, Mansen_US
dc.date.issued2009en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThis dissertation is concerned with finite state machine-based technology for modeling natural language. Finite-state machines have proven to be efficient computational devices in modeling natural language phenomena in morphology and phonology. Because of their mathematical closure properties, finite-state machines can be manipulated and combined in many flexible ways that closely resemble formalisms used in different areas of linguistics to describe natural language. The use of finite-state transducers in constructing natural language parsers and generators has proven to be a versatile approach to describing phonological alternation, morphological constraints and morphotactics, and syntactic phenomena on the phrase level.The main contributions of this dissertation are the development of a new model of multitape automata, the development of a new logic formalism that can substitute for regular expressions in constructing complex automata, and adaptations of these techniques to solving classical construction problems relating to finite-state transducers, such as modeling reduplication and complex phonological replacement rules.The multitape model presented here goes hand-in-hand with the logic formalism, the latter being a necessary step to constructing the former. These multitape automata can then be used to create entire morphological and phonological grammars, and can also serve as a neutral intermediate tool to ease the construction of automata for other purposes.The construction of large-scale finite-state models for natural language grammars is a very delicate process. Making any solution practicable requires great care in the efficient implementation of low-level tasks such as converting regular expressions, logical statements, sets of constraints, and replacement rules to automata or finite transducers. To support the overall endeavor of showing the practicability of the logical and multitape extensions proposed in this thesis, a detailed treatment of efficient implementation of finite-state construction algorithms for natural language purposes is also presented.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectcomputational linguisticsen_US
dc.subjectfinite state machinesen_US
dc.subjectmorphologyen_US
dc.subjectmultitape automataen_US
dc.subjectpredicate logicen_US
dc.subjectreduplication in morphologyen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineLinguisticsen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorHammond, Michaelen_US
dc.contributor.chairHammond, Michaelen_US
dc.contributor.committeememberKarttunen, Laurien_US
dc.contributor.committeememberUssishkin, Adamen_US
dc.contributor.committeememberWedel, Andrewen_US
dc.contributor.committeememberChan, Erwinen_US
dc.identifier.proquest10793en_US
dc.identifier.oclc659753644en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.