---
title: "Dependency Parsing with an Extended Finite-State Approach"
description: "The paper applies finite-state machinery to dependency parsing. 44 references, cited by 20 papers here."
authors: ["Kemal Oflazer"]
year: 2003
venue: "Computational Linguistics"
source: "https://aclanthology.org/J03-4001/"
doi: "10.1162/089120103322753338"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/oflazer-2003-dependency-parsing-extended-finite-state/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/oflazer-2003-dependency-parsing-extended-finite-state/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2003](https://md.research.elamur.ai/free/en/papers/2003/) / Dependency Parsing with an Extended Finite-State Approach

# Dependency Parsing with an Extended Finite-State Approach

**Authors:** [Kemal Oflazer](https://md.research.elamur.ai/free/en/authors/kemal-oflazer/) · **Year:** 2003 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 2003](https://md.research.elamur.ai/free/en/venues/cl/2003/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J03-4001/) · [PDF](https://aclanthology.org/J03-4001.pdf) · [DOI 10.1162/089120103322753338](https://doi.org/10.1162/089120103322753338) · [OpenAlex](https://openalex.org/W2028908189)

**Citations:** 66 citations (OpenAlex, 2026-10-14) · [20](https://md.research.elamur.ai/free/en/papers/oflazer-2003-dependency-parsing-extended-finite-state/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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ı Üniversitesi](https://md.research.elamur.ai/free/en/universities/sabanci-universitesi/) — University, Istanbul, Türkiye · 5 works · 228 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

🧭 Topics (1): [🌳 Dependency parsing](https://md.research.elamur.ai/free/en/topics/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.

```bibtex
@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}
}
```

- [← previous Maximum Entropy Models for FrameNet Classification](https://md.research.elamur.ai/free/en/papers/fleischman-2003-maximum-entropy-models-framenet-classification/)
- [next → Hedge Trimmer: A Parse-and-Trim Approach to Headline Generation](https://md.research.elamur.ai/free/en/papers/dorr-2003-hedge-trimmer-parse-trim-approach/)
- [↑ back to papers of 2003](https://md.research.elamur.ai/free/en/papers/2003/)

## 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](https://scholar.google.com/scholar?q=Abney%2C+Steven%2E+1996%2E+Partial+parsing+via+finite%2Dstate+cascades%2E+Journal+of+Natural+Language+Engineering%2C+2%284%29%3A337%E2%80%93344%2E)
2. Ait-Mokhtar, Salah and Jean-Pierre Chanod. 1997. Incremental finite-state parsing. In Proceedings of ANLP’97, pages 72–79, April. [find](https://scholar.google.com/scholar?q=Ait%2DMokhtar%2C+Salah+and+Jean%2DPierre+Chanod%2E+1997%2E+Incremental+finite%2Dstate+parsing%2E+In+Proceedings+of+ANLP%E2%80%9997%2C+pages+72%E2%80%9379%2C+April%2E)
3. Black, Alan. 1989. Finite state machines from feature grammars. In Proceedings of International Workshop on Parsing Technologies, pages 277–285. [find](https://scholar.google.com/scholar?q=Black%2C+Alan%2E+1989%2E+Finite+state+machines+from+feature+grammars%2E+In+Proceedings+of+International+Workshop+on+Parsing+Technologies%2C+pages+277%E2%80%93285%2E)
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](https://scholar.google.com/scholar?q=Chanod%2C+Jean%2DPierre+and+Pasi+Tapanainen%2E+1996%2E+A+robust+finite%2Dstate+grammar+for+French%2E+In+John+Carroll+and+Ted+Briscoe%2C+editors%2C+Proceedings+of+the+ESSLLI%E2%80%9996+Workshop+on+Robust+Parsing%2C+pages+16%E2%80%9325%2C)
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](https://scholar.google.com/scholar?q=Chelba%2C+Ciprian%2C+David+Engle%2C+Frederick+Jelinek%2C+Victor+Jimenez%2C+Sanjeev+Khudanpur%2C+Lidia+Mangu%2C+Harry+Printz%2C+Eric+Ristad%2C+Ronald+Rosenfeld%2C+Andreas+Stolcke%2C+and+Dekai+Wu%2E+1997%2E+Structure+and+estimat)
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](https://scholar.google.com/scholar?q=Collins%2C+Michael%2E+1996%2E+A+new+statistical+parser+based+on+bigram+lexical+dependencies%2E+In+Proceedings+of+the+34th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+184%E2%80%93191%2E)
7. Collins, Michael, Jan Hajic̆, Lance Ramshaw, and Christoph Tillman. 1999. [A statistical parser for Czech](https://md.research.elamur.ai/free/en/papers/collins-1999-statistical-parser-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](https://scholar.google.com/scholar?q=Cormen%2C+Thomas+H%2E%2C+Charles+E%2E+Leiserson%2C+and+Ronald+L%2E+Rivest%2E+1990%2E+Introduction+to+Algorithms%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
9. Eisner, Jason. 1996. [Three new probabilistic models for dependency parsing: An exploration](https://md.research.elamur.ai/free/en/papers/eisner-1996-three-new-probabilistic-models-dependency/). 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](https://scholar.google.com/scholar?q=Elworthy%2C+David%2E+2000%2E+A+finite+state+parser+with+dependency+structure+output%2E+In+Proceedings+of+International+Workshop+on+Parsing+Technologies%2E)
11. Eppstein, David. 1998. Finding k-shortest paths. Siam Journal on Computing, 28(2):652–673. [find](https://scholar.google.com/scholar?q=Eppstein%2C+David%2E+1998%2E+Finding+k%2Dshortest+paths%2E+Siam+Journal+on+Computing%2C+28%282%29%3A652%E2%80%93673%2E)
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](https://scholar.google.com/scholar?q=Giguet%2C+Emmanuel+and+Jacques+Vergne%2E+1997%2E+From+part%2Dof%2Dspeech+tagging+to+memory%2Dbased+deep+syntactic+analysis%2E+In+Proceedings+of+the+International+Workshop+on+Parsing+Technologies%2C+pages+77%E2%80%9388%2E)
13. Grefenstette, Gregory. 1996. Light parsing as finite-state filtering. In ECAI ’96 Workshop on Extended Finite State Models of Language, August. [find](https://scholar.google.com/scholar?q=Grefenstette%2C+Gregory%2E+1996%2E+Light+parsing+as+finite%2Dstate+filtering%2E+In+ECAI+%E2%80%9996+Workshop+on+Extended+Finite+State+Models+of+Language%2C+August%2E)
14. Grimley-Evans, Edmund. 1997. Approximating context-free grammars with a finite-state calculus. In Proceedings of ACL-EACL’97, pages 452–459. [find](https://scholar.google.com/scholar?q=Grimley%2DEvans%2C+Edmund%2E+1997%2E+Approximating+context%2Dfree+grammars+with+a+finite%2Dstate+calculus%2E+In+Proceedings+of+ACL%2DEACL%E2%80%9997%2C+pages+452%E2%80%93459%2E)
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](https://scholar.google.com/scholar?q=Hajic%CC%8C%2C+Jan%2E+1998%2E+Building+a+syntactically+annotated+corpus%3A+The+Prague+Dependency+Treebank%2E+In+Eva+Hajicova%2C+editor%2C+Issues+in+Valency+and+Meaning%3A+Studies+in+Honour+of+Jarmila+Panenova%2E+Karolinum%E2%80%93C)
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](https://scholar.google.com/scholar?q=Hankamer%2C+Jorge%2E+1989%2E+Morphological+parsing+and+the+lexicon%2E+In+W%2E+Marslen%2DWilson%2C+editor%2C+Lexical+Representation+and+Process%2E+MIT+Press%2C+Cambridge%2C+MA%2C+pages+392%E2%80%93408%2E)
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](https://scholar.google.com/scholar?q=Hobbs%2C+Jerry+R%2E%2C+Douglas+Appelt%2C+John+Bear%2C+David+Israel%2C+Megumi+Kameyama%2C+Mark+Stickel%2C+and+Mabry+Tyson%2E+1997%2E+FASTUS%3A+A+cascaded+finite+state+transducer+for+extracting+information+from+natural+langu)
18. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. [find](https://scholar.google.com/scholar?q=Hopcroft%2C+John+E%2E+and+Jeffrey+D%2E+Ullman%2E+1979%2E+Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation%2E+Addison%2DWesley%2C+Reading%2C+MA%2E)
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](https://scholar.google.com/scholar?q=Ja%CC%88rvinen%2C+Timo+and+Pasi+Tapanainen%2E+1998%2E+Towards+an+implementable+dependency+grammar%2E+In+Proceedings+of+COLING%2FACL%E2%80%9998+Workshop+on+Processing+Dependency%2DBased+Grammars%2C+pages+1%E2%80%9310%2E)
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](https://scholar.google.com/scholar?q=Johnson%2C+Mark%2E+1998%2E+Finite+state+approximation+of+constraint%2Dbased+grammars+using+left%2Dcorner+grammar+transforms%2E+In+Proceedings+of+COLING%2DACL%E2%80%9998%2C+pages+619%E2%80%93623%2C+August%2E)
21. Kaplan, Ronald M. and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378. [find](https://scholar.google.com/scholar?q=Kaplan%2C+Ronald+M%2E+and+Martin+Kay%2E+1994%2E+Regular+models+of+phonological+rule+systems%2E+Computational+Linguistics%2C+20%283%29%3A331%E2%80%93378%2E)
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](https://scholar.google.com/scholar?q=Karttunen%2C+Lauri%2E+1998%2E+The+proper+treatment+of+optimality+theory+in+computational+linguistics%2E+In+Lauri+Karttunen+and+Kemal+Oflazer%2C+editors%2C+Proceedings+of+the+International+Workshop+on+Finite+State)
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](https://scholar.google.com/scholar?q=Karttunen%2C+Lauri%2C+Jean%2DPierre+Chanod%2C+Gregory+Grefenstette%2C+and+Anne+Schiller%2E+1996%2E+Regular+expressions+for+language+engineering%2E+Natural+Language+Engineering%2C+2%284%29%3A305%E2%80%93328%2E)
24. Kokkinakis, Dimitrios and Sofie Johansson Kokkinakis. 1999. A cascaded finite state parser for syntactic analysis of Swedish. In Proceedings of EACL’99. [find](https://scholar.google.com/scholar?q=Kokkinakis%2C+Dimitrios+and+Sofie+Johansson+Kokkinakis%2E+1999%2E+A+cascaded+finite+state+parser+for+syntactic+analysis+of+Swedish%2E+In+Proceedings+of+EACL%E2%80%9999%2E)
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](https://scholar.google.com/scholar?q=Koskenniemi%2C+Kimmo%2E+1990%2E+Finite%2Dstate+parsing+and+disambiguation%2E+In+Proceedings+of+the+13th+International+Conference+on+Computational+Linguistics+%28COLING%E2%80%9990%29%2C+pages+229%E2%80%93233%2E)
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](https://scholar.google.com/scholar?q=Koskenniemi%2C+Kimmo%2C+Pasi+Tapanainen%2C+and+Atro+Voutilainen%2E+1992%2E+Compiling+and+using+finite%2Dstate+syntactic+rules%2E+In+Proceedings+of+the+14th+International+Conference+on+Computational+Linguistics%2C+COL)
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](https://scholar.google.com/scholar?q=Lafferty%2C+John%2C+Daniel+Sleator%2C+and+Davy+Temperley%2E+1992%2E+Grammatical+trigrams%3A+A+probabilistic+model+of+link+grammars%2E+In+Proceedings+of+the+1992+AAAI+Fall+Symposium+on+Probablistic+Approaches+to+Nat)
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](https://scholar.google.com/scholar?q=Lai%2C+Bong+Yeung+Tom+and+Changning+Huang%2E+1994%2E+Dependency+grammar+and+the+parsing+of+Chinese+sentences%2E+In+Proceedings+of+the+1994+Joint+Conference+of+8th+ACLIC+and+2nd+PaFoCol%2E)
29. Lin, Dekang. 1995. A dependency-based method for evaluation of broad-coverage parsers. In Proceedings of IJCAI’95. [find](https://scholar.google.com/scholar?q=Lin%2C+Dekang%2E+1995%2E+A+dependency%2Dbased+method+for+evaluation+of+broad%2Dcoverage+parsers%2E+In+Proceedings+of+IJCAI%E2%80%9995%2E)
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](https://scholar.google.com/scholar?q=Lin%2C+Dekang%2E+1996%2E+On+the+structural+complexity+of+natural+language+sentences%2E+In+Proceedings+of+the+16th+International+Conference+on+Computational+Linguistics+%28COLING%2D96%29%2E)
31. Melčuk, Igor A. 1988. Dependency Syntax: Theory and Practice. State University of New York Press, Albany, NY. [find](https://scholar.google.com/scholar?q=Melc%CC%8Cuk%2C+Igor+A%2E+1988%2E+Dependency+Syntax%3A+Theory+and+Practice%2E+State+University+of+New+York+Press%2C+Albany%2C+NY%2E)
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](https://scholar.google.com/scholar?q=Mohri%2C+Mehryar%2C+Fernando+C%2E+N%2E+Pereira%2C+and+Michael+Riley%2E+1998%2E+A+rational+design+for+a+weighted+finite%2Dstate+transducer+library%2E+In+Derick+Wood+and+Sheng+Yu%2C+editors%2C+Proceedings+of+the+Second+Inter)
33. Nederhof, Mark-Jan. 1998. Context-free parsing through regular approximation. [find](https://scholar.google.com/scholar?q=Nederhof%2C+Mark%2DJan%2E+1998%2E+Context%2Dfree+parsing+through+regular+approximation%2E)
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](https://scholar.google.com/scholar?q=In+Lauri+Karttunen+and+Kemal+Oflazer%2C+editors%2C+Proceedings+of+International+Workshop+on+Finite+State+Methods+in+Natural+Language+Processing%2C+pages+13%E2%80%9324%2C+Ankara%2C+Turkey%2E)
35. Nederhof, Mark-Jan. 2000. Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1):17–44. [find](https://scholar.google.com/scholar?q=Nederhof%2C+Mark%2DJan%2E+2000%2E+Practical+experiments+with+regular+approximation+of+context%2Dfree+languages%2E+Computational+Linguistics%2C+26%281%29%3A17%E2%80%9344%2E)
36. Oflazer, Kemal. 1993. [Two-level description of Turkish morphology](https://md.research.elamur.ai/free/en/papers/oflazer-1993-two-level-description-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](https://scholar.google.com/scholar?q=Oflazer%2C+Kemal%2C+Bilge+Say%2C+Dilek+Zeynep+Hakkani%2DTu%CC%88r%2C+and+Go%CC%88khan+Tu%CC%88r%2E+2003%2E+Building+a+Turkish+treebank%2E+In+Anne+Abeille%CC%81%2C+editor%2C+Treebanks%2E+Kluwer+Academic+Publishers%2C+Dordrecht%2C+the+Netherlands%2E)
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](https://scholar.google.com/scholar?q=Pereira%2C+Fernando+C%2E+N%2E%2C+and+Rebecca+N%2E+Wright%2E+1997%2E+Finite+state+approximation+of+phrase+structure+grammars%2E+In+Emmanuel+Roche+and+Yves+Schabes%2C+editors%2C+Finite+State+Language+Processing%2E+MIT+Press%2C)
39. Robinson, Jane J. 1970. Dependency structures and transformational rules. Language, 46(2):259–284. [find](https://scholar.google.com/scholar?q=Robinson%2C+Jane+J%2E+1970%2E+Dependency+structures+and+transformational+rules%2E+Language%2C+46%282%29%3A259%E2%80%93284%2E)
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](https://scholar.google.com/scholar?q=Roche%2C+Emmanuel%2E+1997%2E+Parsing+with+finite+state+transducers%2E+In+Emmanuel+Roche+and+Yves+Schabes%2C+editors%2C+Finite%E2%80%93State+Language+Processing%2C+chap%2E+8%2E+MIT+Press%2C+Cambrigde%2C+MA%2E)
41. Roche, Emmanuel and Yves Schabes, editors. 1997. Finite State Language Processing. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Roche%2C+Emmanuel+and+Yves+Schabes%2C+editors%2E+1997%2E+Finite+State+Language+Processing%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
42. Sleator, Daniel and Davy Temperley. 1991. [Parsing English with a link grammar](https://md.research.elamur.ai/free/en/papers/sleator-1993-parsing-english-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](https://md.research.elamur.ai/free/en/papers/tapanainen-1997-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](https://scholar.google.com/scholar?q=Yu%CC%88ret%2C+Deniz%2E+1998%2E+Discovery+of+Linguistic+Relations+Using+Lexical+Attraction%2E+Ph%2ED%2E+thesis%2C+Department+of+Electrical+Engineering+and+Computer+Science%2C+Massachusetts+Institute+of+Technology%2C+Cambrid)

*Updated 30 October 2026*