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.

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • Export XML

Additional Services

Share in Twitter Search Google Scholar
Author:Anssi Yli-Jyrä
Document Type:Conference Proceeding
Year of Completion:2008
Publishing Institution:Universität Potsdam
Release Date:2008/12/11
Organizational units:Extern / Extern
Dewey Decimal Classification:4 Sprache / 40 Sprache / 400 Sprache
Collections:Universität Potsdam / Tagungen / Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 / I Invited Papers
Licence (German):License LogoKeine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht
Notes extern:
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