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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Roche, E., Schabes, Y. (eds.): Finite-State Language Processing. MIT Press, Cambridge (1997)
Carroll, J.: Parsing. In: Mitkov, R. (ed.) The Oxford Handbook of Computational Linguistics, pp. 233–248. Oxford University Press, Oxford (2003)
Nederhof, M.J.: Practical experiments with regular approximation of context-free languages. Computational Linguistics 26(1), 17–44 (2000)
Grimley Evans, E.: Approximating context-free grammars with a finite-state calculus. In: Proceedings of ACL/EACL 1997, Association for Computational Linguistics, pp. 452–459 (1997)
Johnson, M.: Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In: Proceedings of ACL/COLING 1998, Association for Computational Linguistics, pp. 619–623 (1998)
Oflazer, K.: Dependency parsing with an extended finite-state approach. Computational Linguistics 29(4), 515–544 (2003)
Elworthy, D.: A finite state parser with dependency structure output. In: Proceedings of the Sixth International Workshop on Parsing Technologies IWPT 2000, Trento, Italy (2000)
Koskenniemi, K.: Finite-state parsing and disambiguation. In: Karlgren, H. (ed.) Proceedings of the 13th International Conference on Computational Linguistics COLING 1990, Helsinki, Finland, ACL, pp. 229–232 (1990)
Yli-Jyrä, A.M.: Approximating dependency grammars through intersection of star-free regular languages. International Journal of Foundations of Computer Science 16(3), 565–579 (2005)
Hays, D.G.: Dependency theory: A formalism and some observations. Language 40, 511–525 (1964)
Gaifman, H.: Dependency systems and phrase-structure systems. Information and Control 8, 304–337 (1965)
Sleator, D.D., Temperley, D.: Parsing English with a Link Grammar. In: Proceedings of the Third International Workshop on Parsing Technologies IWPT 1993, Tilburg, Netherlands (1993)
Miller, S., Fox, H., Ramshaw, L., Weischedel, R.: A novel use of statistical parsing to extract information from text. In: Proceedings of NAACL 2000, pp. 226–233. Morgan Kaufmann, San Francisco (2000)
Ginter, F., Mylläri, A., Salakoski, T.: A probabilistic search for the best solution among partially completed candidates. In: Proceedings of the HLT/NAACL 2006 Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing, Association for Computational Linguistics, pp. 33–40 (2006)
Grinberg, D., Lafferty, J., Sleator, D.D.: A robust parsing algorithm for link grammars. In: Proceedings of the Fourth International Workshop on Parsing Technologies IWPT 1995, Prague, Czech Republic (1995)
van Noord, G.: FSA utilities: A toolbox to manipulate finite-state automata. In: Wood, D., Darrell, R., Yu, S. (eds.) WIA 1996. LNCS, vol. 1260, pp. 87–108. Springer, Heidelberg (1997)
Mohri, M., Pereira, F.C.N., Riley, M.: A rational design for a weighted finite-state transducer library. In: Wood, D., Yu, S. (eds.) WIA 1997. LNCS, vol. 1436, pp. 144–158. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ginter, F., Pyysalo, S., Boberg, J., Salakoski, T. (2006). Regular Approximation of Link Grammar. In: Salakoski, T., Ginter, F., Pyysalo, S., Pahikkala, T. (eds) Advances in Natural Language Processing. FinTAL 2006. Lecture Notes in Computer Science(), vol 4139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11816508_56
Download citation
DOI: https://doi.org/10.1007/11816508_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37334-6
Online ISBN: 978-3-540-37336-0
eBook Packages: Computer ScienceComputer Science (R0)