Compiling Generalized Two-Level Rules and Grammars
| Autor: | Kimmo Koskenniemi, Anssi Yli-Jyrä |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Theoretical computer science
Finite-state machine Grammar Computer science business.industry media_common.quotation_subject computer.software_genre Automaton Rule-based machine translation Phonological rule Compiler Regular expression Artificial intelligence Alphabet business computer Algorithm Natural language Natural language processing media_common |
| Zdroj: | Advances in Natural Language Processing ISBN: 9783540373346 FinTAL |
| DOI: | 10.1007/11816508_19 |
| Popis: | New methods to compile morphophonological two-level rules into finite-state machines are presented. Compilation of the original and new two-level rules and grammars is formulated using an operation called the generalized restriction that constructs a one-tape finite-state automaton over an input alphabet of symbol pairs. The generalized restriction is first used to compile the original two-level formalism where the rules were restricted to single symbol pairs as their centers (i.e. the left-hand sides of the rules). The solution handles also strings of symbol pairs (or regular expressions over the pair alphabet) as centers of two-level rules. Then, the treatment of context conditions is generalized with unions and relative complements etc. Moreover, an extended rule type, the presence requirement, combines the generalized context conditions with center conditions at both sides of the rules. The left-hand side specifies where the rule applies and the right-hand side specifies which of the applications are successful. The original two-level grammars were represented as a separate finite-state machine for each rule and the whole grammar as their intersection. The new methods are used first to redefine this setup, and then to implement a uniform conflict resolution scheme for all rules. The resolution scheme prefers successful and the longest embedded applications of rules, but it treats partially overlapping or explicitly independent applications of rules conjunctively. The composite rules of the original formalism have a marginal status in the new formalism because only identity pairs are allowed in locations where no rule is applicable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|