Applications of diamonded double negation
- Nested complementation plays an important role in expressing counter- i.e. star-free and first-order definable languages and their hierarchies. In addition, methods that compile phonological rules into finite-state networks use double-nested complementation or “double negation”. This paper reviews how the double-nested complementation extends to a relatively new operation, generalized restriction (GR), coined by the author (Yli-Jyrä and Koskenniemi 2004). This operation encapsulates a double-nested complementation and elimination of a concatenation marker, diamond, whose finite occurrences align concatenations in the arguments of the operation. The paper demonstrates that the GR operation has an interesting potential in expressing regular languages, various kinds of grammars, bimorphisms and relations. This motivates a further study of optimized implementation of the operator.
Author details: | Anssi Yli-Jyrä |
---|---|
URN: | urn:nbn:de:kobv:517-opus-27109 |
Publication type: | Conference Proceeding |
Language: | English |
Publication year: | 2008 |
Publishing institution: | Universität Potsdam |
Release date: | 2008/12/11 |
Organizational units: | Extern / Extern |
DDC classification: | 4 Sprache / 40 Sprache / 400 Sprache |
Collection(s): | Universität Potsdam / Tagungsbände/Proceedings (nicht fortlaufend) / Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 / I Invited Papers |
License (German): | Keine öffentliche Lizenz: Unter Urheberrechtsschutz |
External remark: | The complete edition of the proceedings "Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 ; Revised Papers" is available: URN urn:nbn:de:kobv:517-opus-23812 |