Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Regular Approximation of Link ...

Regular Approximation of Link Grammar

Filip Ginter, Sampo Pyysalo, Jorma Boberg, Tapio Salakoski, Regular Approximation of Link Grammar. In: Advances in Natural Language Processing, 5th International Conference, FinTAL 2006 Turku, Finland, August 23-25, 2006 Proceedings, Lecture Notes in Computer Science 4139, 564–575, Springer Berlin / Heidelberg, 2006.

Abstract:

We present a regular approximation of Link Grammar, a
dependency-type formalism with context-free expressive power, as a first
step toward a finite-state joint inference system. The approximation is
implemented by limiting the maximum nesting depth of links, and otherwise retains the features of the original formalism. We present a string
encoding of Link Grammar parses and describe finite-state machines implementing the grammar rules as well as the planarity, connectivity, ordering and exclusion axioms constraining grammatical Link Grammar
parses. The regular approximation is then defined as the intersection
of these machines. Finally, we implement two approaches to finite-state
parsing using the approximation and discuss their feasibility. We find
that parsing in the intersection grammars framework using the approximation is feasible, although inefficient, and we discuss several approaches to improve the efficiency.

BibTeX entry:

@INPROCEEDINGS{inpGiPyBoSa06a,
  title = {Regular Approximation of Link Grammar},
  booktitle = {Advances in Natural Language Processing, 5th International Conference, FinTAL 2006 Turku, Finland, August 23-25, 2006 Proceedings},
  author = {Ginter, Filip and Pyysalo, Sampo and Boberg, Jorma and Salakoski, Tapio},
  volume = {4139},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer Berlin / Heidelberg},
  pages = {564–575},
  year = {2006},
}

Belongs to TUCS Research Unit(s): Turku BioNLP Group

Publication Forum rating of this publication: level 1

Edit publication