Elamur Research⌕
☰
home / papers / 2003 / Dependency Parsing with an Extended Finite-State Approach

Dependency Parsing with an Extended Finite-State Approach

Paper · 2003 · Kemal Oflazer

Summary

The paper applies finite-state machinery to dependency parsing. Earlier extended finite-state parsers, such as those of Roche and Abney, produced constituent bracketing. Oflazer instead represents a sentence as a symbol string with extra "channels" where symbols marking head–dependent links can be inserted. A transducer encoding linking rules is run over the string repeatedly. Each pass adds links that do not interfere with one another, and parsing stops at a fixed point. Finite-state filters remove intermediate results that violate projective well-formedness, such as crossing links or unattached words other than the sentence head. Rules can stop links from spanning barriers like punctuation or words with particular morphological properties. Lenient composition allows partial parses with a few unattached words when full attachment fails. The parser has no statistical component. It outputs every analysis, packed into a transducer lattice, and ranks them by total link length following Lin (1995). Tested on Turkish, an agglutinative language with flexible word order, it shows that rule-based finite-state methods can produce dependency structures directly.

Key points

  • In the Turkish prototype, the correct parse was among the trees with the smallest total link length for over 48% of sentences.
  • The number of passes depends on the input sentence and continues until no new links can be added. This differs from Abney's cascades, where the grammar fixes the number of stages.
  • The structural filters implement Robinson's (1970) axioms for dependency trees, including projectivity.
  • Robustness comes from lenient composition, which relaxes constraints so that a small number of unlinked dependents is allowed.
  • Related work discussed includes Roche (1997), Abney (1996), Elworthy (2000) and FASTUS (Hobbs et al. 1997).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Sabancı ÜniversitesiIstanbul · Türkiye5 works · 228 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Dependency parsing · 131 works

Cite

Cite as Kemal Oflazer. 2003. Dependency Parsing with an Extended Finite-State Approach. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/089120103322753338

@article{oflazer2003dependency,
  title = {{Dependency Parsing with an Extended Finite-State Approach}},
  author = {Kemal Oflazer},
  journal = {Computational Linguistics},
  year = {2003},
  doi = {10.1162/089120103322753338},
  url = {https://doi.org/10.1162/089120103322753338}
}

References

44 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Abney, Steven. 1996. Partial parsing via finite-state cascades. Journal of Natural Language Engineering, 2(4):337–344. find
  2. Ait-Mokhtar, Salah and Jean-Pierre Chanod. 1997. Incremental finite-state parsing. In Proceedings of ANLP’97, pages 72–79, April. find
  3. Black, Alan. 1989. Finite state machines from feature grammars. In Proceedings of International Workshop on Parsing Technologies, pages 277–285. find
  4. Chanod, Jean-Pierre and Pasi Tapanainen. 1996. A robust finite-state grammar for French. In John Carroll and Ted Briscoe, editors, Proceedings of the ESSLLI’96 Workshop on Robust Parsing, pages 16–25, August. find
  5. Chelba, Ciprian, David Engle, Frederick Jelinek, Victor Jimenez, Sanjeev Khudanpur, Lidia Mangu, Harry Printz, Eric Ristad, Ronald Rosenfeld, Andreas Stolcke, and Dekai Wu. 1997. Structure and estimation of a dependency language model. In Processings of Eurospeech’97. find
  6. Collins, Michael. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 184–191. find
  7. Collins, Michael, Jan Hajic̆, Lance Ramshaw, and Christoph Tillman. 1999. A statistical parser for Czech. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages 505–512, June.
  8. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. find
  9. Eisner, Jason. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96), pages 340–345, August.
  10. Elworthy, David. 2000. A finite state parser with dependency structure output. In Proceedings of International Workshop on Parsing Technologies. find
  11. Eppstein, David. 1998. Finding k-shortest paths. Siam Journal on Computing, 28(2):652–673. find
  12. Giguet, Emmanuel and Jacques Vergne. 1997. From part-of-speech tagging to memory-based deep syntactic analysis. In Proceedings of the International Workshop on Parsing Technologies, pages 77–88. find
  13. Grefenstette, Gregory. 1996. Light parsing as finite-state filtering. In ECAI ’96 Workshop on Extended Finite State Models of Language, August. find
  14. Grimley-Evans, Edmund. 1997. Approximating context-free grammars with a finite-state calculus. In Proceedings of ACL-EACL’97, pages 452–459. find
  15. Hajič, Jan. 1998. Building a syntactically annotated corpus: The Prague Dependency Treebank. In Eva Hajicova, editor, Issues in Valency and Meaning: Studies in Honour of Jarmila Panenova. Karolinum–Charles University Press, Prague, pages 106–132. find
  16. Hankamer, Jorge. 1989. Morphological parsing and the lexicon. In W. Marslen-Wilson, editor, Lexical Representation and Process. MIT Press, Cambridge, MA, pages 392–408. find
  17. Hobbs, Jerry R., Douglas Appelt, John Bear, David Israel, Megumi Kameyama, Mark Stickel, and Mabry Tyson. 1997. FASTUS: A cascaded finite state transducer for extracting information from natural language text. In Emmanuel Roche and Yves Schabes, editors, Finite State Language Processing. MIT Press,… find
  18. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. find
  19. Järvinen, Timo and Pasi Tapanainen. 1998. Towards an implementable dependency grammar. In Proceedings of COLING/ACL’98 Workshop on Processing Dependency-Based Grammars, pages 1–10. find
  20. Johnson, Mark. 1998. Finite state approximation of constraint-based grammars using left-corner grammar transforms. In Proceedings of COLING-ACL’98, pages 619–623, August. find
  21. Kaplan, Ronald M. and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378. find
  22. Karttunen, Lauri. 1998. The proper treatment of optimality theory in computational linguistics. In Lauri Karttunen and Kemal Oflazer, editors, Proceedings of the International Workshop on Finite State Methods in Natural Language Processing (FSMNLP), June. find
  23. Karttunen, Lauri, Jean-Pierre Chanod, Gregory Grefenstette, and Anne Schiller. 1996. Regular expressions for language engineering. Natural Language Engineering, 2(4):305–328. find
  24. Kokkinakis, Dimitrios and Sofie Johansson Kokkinakis. 1999. A cascaded finite state parser for syntactic analysis of Swedish. In Proceedings of EACL’99. find
  25. Koskenniemi, Kimmo. 1990. Finite-state parsing and disambiguation. In Proceedings of the 13th International Conference on Computational Linguistics (COLING’90), pages 229–233. find
  26. Koskenniemi, Kimmo, Pasi Tapanainen, and Atro Voutilainen. 1992. Compiling and using finite-state syntactic rules. In Proceedings of the 14th International Conference on Computational Linguistics, COLING-92, pages 156–162. find
  27. Lafferty, John, Daniel Sleator, and Davy Temperley. 1992. Grammatical trigrams: A probabilistic model of link grammars. In Proceedings of the 1992 AAAI Fall Symposium on Probablistic Approaches to Natural Language. find
  28. Lai, Bong Yeung Tom and Changning Huang. 1994. Dependency grammar and the parsing of Chinese sentences. In Proceedings of the 1994 Joint Conference of 8th ACLIC and 2nd PaFoCol. find
  29. Lin, Dekang. 1995. A dependency-based method for evaluation of broad-coverage parsers. In Proceedings of IJCAI’95. find
  30. Lin, Dekang. 1996. On the structural complexity of natural language sentences. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96). find
  31. Melčuk, Igor A. 1988. Dependency Syntax: Theory and Practice. State University of New York Press, Albany, NY. find
  32. Mohri, Mehryar, Fernando C. N. Pereira, and Michael Riley. 1998. A rational design for a weighted finite-state transducer library. In Derick Wood and Sheng Yu, editors, Proceedings of the Second International Workshop on Implementing Automata (WIA ’97), volume 1436 of Lecture Notes in Computer Scien… find
  33. Nederhof, Mark-Jan. 1998. Context-free parsing through regular approximation. find
  34. In Lauri Karttunen and Kemal Oflazer, editors, Proceedings of International Workshop on Finite State Methods in Natural Language Processing, pages 13–24, Ankara, Turkey. find
  35. Nederhof, Mark-Jan. 2000. Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1):17–44. find
  36. Oflazer, Kemal. 1993. Two-level description of Turkish morphology. In Proceedings of the Sixth Conference of the European Chapter of the Association for Computational Linguistics, April. (A full version appears in Literary and Linguistic Computing, 9(2), 1994).
  37. Oflazer, Kemal, Bilge Say, Dilek Zeynep Hakkani-Tür, and Gökhan Tür. 2003. Building a Turkish treebank. In Anne Abeillé, editor, Treebanks. Kluwer Academic Publishers, Dordrecht, the Netherlands. find
  38. Pereira, Fernando C. N., and Rebecca N. Wright. 1997. Finite state approximation of phrase structure grammars. In Emmanuel Roche and Yves Schabes, editors, Finite State Language Processing. MIT Press, Cambridge, MA. find
  39. Robinson, Jane J. 1970. Dependency structures and transformational rules. Language, 46(2):259–284. find
  40. Roche, Emmanuel. 1997. Parsing with finite state transducers. In Emmanuel Roche and Yves Schabes, editors, Finite–State Language Processing, chap. 8. MIT Press, Cambrigde, MA. find
  41. Roche, Emmanuel and Yves Schabes, editors. 1997. Finite State Language Processing. MIT Press, Cambridge, MA. find
  42. Sleator, Daniel and Davy Temperley. 1991. Parsing English with a link grammar. Technical Report CMU-CS-91-196, Computer Science Department, Carnegie Mellon University.
  43. Tapanainen, Pasi and Timo Järvinen. 1997. A non-projective dependency parser. In Proceedings of ANLP’97, pages 64–71, April. van Noord, Gertjan. 1997. FSA utilities: A toolbox to manipulate finite-state automata. In Derick Wood, Darrell Raymond, and Sheng Yu, editors, Automata Implementation, volum…
  44. Yüret, Deniz. 1998. Discovery of Linguistic Relations Using Lexical Attraction. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/oflazer-2003-dependency-parsing-extended-finite-state/