Back to home page

Publications

To appear

-

2017

M.-J. Nederhof and A. Yli-Jyrä. A Derivational Model of Discontinuous Parsing. In F. Drewes, C. Martín-Vide, and B. Truthe (eds.), Language and Automata Theory and Applications, 11th International Conference, Lecture Notes in Computer Science, volume 10168, pages 299-310, Umeå, Sweden, March, 2017. Springer-Verlag. [link]

M.-J. Nederhof. Free word order and MCFLs. In M. Wieling, M. Kroon, G. van Noord, and G. Bouma, editors, From Semantics to Dialectometry: Festschrift for John Nerbonne, Chapter 28, pages 273-282, College Publications, 2017. [pdf]

2016

M.-J. Nederhof, M. Teichmann, and H. Vogler. Non-Self-Embedding Linear Context-Free Tree Grammars Generate Regular Tree Languages. Journal of Automata, Languages and Combinatorics, 21(3):203-246, 2016. [link]

M.-J. Nederhof. A short proof that O2 is a MCFL. In Proceedings of the 54th Annual Meeting of the Annual Meeting of the Association for Computational Linguistics, pages 1117-1126, Berlin, August 2016. [link]

M.-J. Nederhof. Transition-based dependency parsing as latent-variable constituent parsing. In Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata, pages 21-31, Berlin, August 2016. [link]

M.-J. Nederhof, V. Rajan, J. Lang, S. Polis, S. Rosmorduc, T.S. Richter, I. Hafemann, S. Schweitzer. A system of control characters for Ancient Egyptian hieroglyphic text (updated version). Unicode Technical Committee (UTC) Document Register, L2/16-210R, 2017-01-25. [link]

2015

M.-J. Nederhof. OCR of handwritten transcriptions of Ancient Egyptian hieroglyphic text. In Altertumswissenschaften in a Digital Age: Egyptology, Papyrology and beyond, proceedings of a conference and workshop in Leipzig, November 4-6, 2015. [link]

M.-J. Nederhof and F. Rahman. A probabilistic model of Ancient Egyptian writing. In Proceedings of the 12th International Conference on Finite State Methods and Natural Language Processing, Düsseldorf, Germany, June 2015. [link]

Toni Dietze and M.-J. Nederhof. Count-Based State Merging for Probabilistic Regular Tree Grammars. In Proceedings of the 12th International Conference on Finite State Methods and Natural Language Processing, Düsseldorf, Germany, June 2015. [link]

2014

M.-J. Nederhof and H. Vogler. Hybrid Grammars for Discontinuous Parsing. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 1370-1381, Dublin, Ireland, August 2014. [link, code]

M.-J. Nederhof and M. McCaffery. Deterministic Parsing using PCFGs. In 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 338-347, Gothenburg, Sweden, April 2014. [link]

M. Büchse, M.-J. Nederhof, and H. Vogler. Tree Parsing for Tree-Adjoining Machine Translation. Journal of Logic and Computation, 24(2):351-373, 2014. [link]

M.-J. Nederhof and G. Satta. Prefix probabilities for linear context-free rewriting systems. Journal of Logic and Computation, 24(2):331-350, 2014. [link]

2013

Formal Grammar: 17th and 18th International Conferences, Opole, Poland (August 2012) and Düsseldorf, Germany (August 2013), G. Morrill and M.-J. Nederhof (eds). Lecture Notes in Artificial Intelligence, volume 8036, 2013. [link]

E. Bertsch, M.-J. Nederhof and S. Schmitz. On LR Parsing with Selective Delays. In R. Jhala and K. De Bosschere (eds.), 22nd International Conference on Compiler Construction, Lecture Notes in Computer Science, volume 7791, pages 244-263, Rome, Italy, March 2013. Springer-Verlag.

M.-J. Nederhof. Flexible use of text annotations and distance learning. In S. Polis and J. Winand, editors, Texts, Languages & Information Technology in Egyptology, pages 75-88. Presses Universitaires de Liège, 2013. [pdf]

M.-J. Nederhof. The Manuel de Codage encoding of hieroglyphs impedes development of corpora. In S. Polis and J. Winand, editors, Texts, Languages & Information Technology in Egyptology, pages 103-110. Presses Universitaires de Liège, 2013. [pdf]

2012

M.-J. Nederhof and H. Vogler. Synchronous Context-Free Tree Grammars. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms, pages 55-63, Paris, France, September 2012. [link]

M.-J. Nederhof. Review of "N. Francez and S. Wintner: Unification Grammars". Theory and Practice of Logic Programming, 2012. [link]

15th and 16th International Conference on Formal Grammar, Copenhagen, Denmark (August 2010) and Lubljana, Slovenia (August 2011), P. de Groote and M.-J. Nederhof (eds). Lecture Notes in Artificial Intelligence, volume 7395, 2012. [link]

2011

M. Büchse, M.-J. Nederhof, and H. Vogler. Tree Parsing with Synchronous Tree-Adjoining Grammars. In IWPT 2011, pages 14-25, Dublin, Ireland, October 2011. [link]

M.-J. Nederhof and G. Satta. Prefix probabilities for Linear Context-Free Rewriting Systems. In IWPT 2011, pages 151-162, Dublin, Ireland, October 2011. [link]

M.-J. Nederhof and R. Sánchez-Sáez. Parsing of Partially Bracketed Structures for Parse Selection. In IWPT 2011, pages 231-240, Dublin, Ireland, October 2011. [link]

M.-J. Nederhof and G. Satta. Computation of Infix Probabilities for Probabilistic Context-Free Grammars. In EMNLP 2011, pages 1213-1221, Edinburgh, UK, July 2011. [pdf]

M.-J. Nederhof and G. Satta. Prefix Probability for Probabilistic Synchronous Context-Free Grammars. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 460-469, Portland, Oregon, June 2011. [pdf]

M.-J. Nederhof and G. Satta. Splittability of Bilexical Context-Free Grammars is Undecidable. Computational Linguistics, 37(4):867-879, December 2011. [link]

2010

M.-J. Nederhof. Transforming Lexica as Trees. In Workshop on Applications of Tree Automata in Natural Language Processing, pages 37-45, Uppsala, Sweden 2010. [pdf]

M.-J. Nederhof and G. Satta. Algorithmic aspects of natural language processing. In M.J. Atallah and M. Blanton, editors, Algorithms and Theory of Computation Handbook -- Special Topics and Techniques, Chapter 23. CRC Press, 2010. [pdf]

M.-J. Nederhof and G. Satta. Theory of Parsing. In A. Clark, C. Fox, and S. Lappin, editors, The Handbook of Computational Linguistics and Natural Language Processing, Chapter 4, pages 105-130, Blackwell Publishing Ltd, 2010.

2009

M.-J. Nederhof. Automatic Creation of Interlinear Text for Philological Purposes. Traitement Automatique des Langues, 50(2):237-255, 2009. [pdf]

M.-J. Nederhof. Weighted parsing of trees. In Proceedings of the 11th International Conference on Parsing Technologies, pages 13-24, Paris, France, October 2009. [pdf]

2008

M.-J. Nederhof. Automatic alignment of hieroglyphs and transliteration. In N. Strudwick, editor, Information Technology and Egyptology in 2008, Proceedings of the meeting of the Computer Working Group of the International Association of Egyptologists, pages 71-92, Vienna, July 2008. Gorgias Press. [pdf of article; pdf of book's front matter]

M.-J. Nederhof and G. Satta. Computing Partition Functions of PCFGs. Research on Language and Computation, 6(2):139-162, 2008. [pdf]

M.-J. Nederhof and G. Satta. Probabilistic Parsing. In G. Bel-Enguix, M. Dolores Jiménez-López, and C. Martín-Vide, editors, New Developments in Formal Languages and Applications, Studies in Computational Intelligence 113, pages 229-258. Springer, 2008. [pdf]

M.-J. Nederhof and G. Satta. Computation of distances for regular and context-free probabilistic languages. Theoretical Computer Science, 395:235-254, 2008. [pdf]

2007

E. Bertsch and M.-J. Nederhof. Some observations on LR-like parsing with delayed reduction. Information processing letters, 104:195-199, 2007. [pdf]

2006

M.-J. Nederhof and G. Satta. Probabilistic parsing strategies. Journal of the ACM, 53(3):406-436, 2006. [pdf]

M.-J. Nederhof and G. Satta. Estimation of Consistent Probabilistic Context-free Grammars. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 343-350, New York, June 2006. [pdf]

M. Kemps-Snijders, M.-J. Nederhof, and P. Wittenburg. LEXUS, a web-based tool for manipulating lexical resources. In LREC 2006: Fifth International Conference on Language Resources and Evaluation, pages 1862-1865, Genoa, Italy, May 2006. [pdf]

2005

E. Bertsch and M.-J. Nederhof. Gap parsing with LL(1) grammars. Grammars, 8:1-16, 2005. [link]

M.-J. Nederhof. A general technique to train language models on language models. Computational Linguistics, 31(2):173-185, June 2005. [pdf]

2004

M.-J. Nederhof and G. Satta. IDL-expressions: A formalism for representing and parsing finite languages in natural language processing. Journal of Artificial Intelligence Research, 21:287-317, 2004. [link]

M.-J. Nederhof and G. Satta. Tabular Parsing. In C. Martín-Vide, V. Mitrana, and G. Paun, editors, Formal Languages and Applications, Studies in Fuzziness and Soft Computing 148, pages 529-549. Springer, 2004. [link]

M.-J. Nederhof and G. Satta. The language intersection problem for non-recursive context-free grammars, Information and Computation, 192(2):172-184, 2004. [ps]

M.-J. Nederhof and G. Satta. Probabilistic Parsing Strategies. In 42nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 543-550, Barcelona, Spain, July 2004. [pdf]

M.-J. Nederhof and G. Satta. An alternative method of training probabilistic LR parsers. In 42nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 551-558, Barcelona, Spain, July 2004. [pdf]

M.-J. Nederhof and G. Satta. Kullback-Leibler distance between probabilistic context-free grammars and probabilistic finite automata. In 20th International Conference on Computational Linguistics Proceedings of the Conference, volume 1, pages 71-77, Geneva, Switzerland, August 2004. [pdf]

E. Bertsch and M.-J. Nederhof. Fast parallel recognition of LR language suffixes. In Information Processing Letters, 92:225-229, 2004. [pdf]

2003

M.-J. Nederhof. Weighted deductive parsing and Knuth's algorithm. Computational Linguistics, 29(1):135-143, March 2003. [ps]

M.-J. Nederhof and G. Satta. Probabilistic parsing as intersection. In 8th International Workshop on Parsing Technologies, pages 137-148, Nancy, France, April 2003. [pdf]

M.-J. Nederhof, G. Satta, and S. Shieber. Partially ordered multiset context-free grammars and free-word-order parsing. In 8th International Workshop on Parsing Technologies, pages 171-182, Nancy, France, April 2003. [pdf]

M.-J. Nederhof and G. Satta. Probabilistic parsing strategies. In Proceedings of the 3rd AMAST Workshop on Algebraic Methods in Language Processing (AMiLP 2003), pages 19-32, Verona, Italy, 2003. [ps]

2002

M.-J. Nederhof and G. Satta. Parsing non-recursive context-free grammars. In 40th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 112-119, Philadelphia, Pennsylvania, USA, July 2002. [pdf]

M.-J. Nederhof and G. Satta. Probabilistic parsing strategies. In J. Dassow et al., editors, Descriptional Complexity of Formal Systems (DCFS), Pre-Proceedings of a Workshop, pages 216-230, London, Canada, August 2002. [pdf]

M.-J. Nederhof and G. Satta. IDL-expressions: a compact representation for finite languages in generation systems. In Proceedings of FG Trento, The 7th Conference on Formal Grammar, pages 125-136, Trento, Italy, 2002. [ps]

M.-J. Nederhof. Alignment of resources on Egyptian texts based on XML. In Proceedings of the 14th Table Ronde Informatique et Égyptologie, Pisa, Italy, July 2002. Available only on CD-ROM. [pdf]

M.-J. Nederhof. A revised encoding scheme for hieroglyphic. In Proceedings of the 14th Table Ronde Informatique et Égyptologie, Pisa, Italy, July 2002. Available only on CD-ROM. [pdf]

2001

M. Mohri and M.-J. Nederhof. Regular approximation of context-free grammars through transformation. In J.-C. Junqua and G. van Noord, editors, Robustness in Language and Speech Technology, pages 153-163. Kluwer Academic Publishers, 2001. [pdf]

M.-J. Nederhof. Approximating context-free by rational transduction for example-based MT. In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Workshop proceedings: Data-driven Machine Translation, pages 25-32, Toulouse, France, July 2001. [pdf]

M.-J. Nederhof. Letter to the editor. Skeptical Inquirer, 25(4):74, 2001.

E. Bertsch and M.-J. Nederhof. On the complexity of some extensions of RCG parsing. In Proceedings of the Seventh International Workshop on Parsing Technologies, pages 66-77, Beijing, China, October 2001. [pdf]

E. Bertsch and M.-J. Nederhof. Size/lookahead tradeoff for LL(k)-grammars. Information Processing Letters, 80:125-129, 2001. [pdf]

2000

M.-J. Nederhof. Practical experiments with regular approximation of context-free languages. Computational Linguistics, 26(1):17-44, March 2000. [pdf]

M.-J. Nederhof and G. Satta. Left-to-right parsing and bilexical context-free grammars. In 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics, Section 2, pages 272-279, Seattle, Washington, USA, April/May 2000. [pdf]

M.-J. Nederhof. Preprocessing for unification parsing of spoken language. In Natural Language Processing - NLP 2000, Lecture Notes in Artificial Intelligence, volume 1835, pages 118-129, Patras, Greece, June 2000. Springer-Verlag. [pdf]

M.-J. Nederhof. Regular approximation of CFLs: a grammatical view. In H. Bunt and A. Nijholt, editors, Advances in Probabilistic and other Parsing Technologies, chapter 12, pages 221-241. Kluwer Academic Publishers, 2000. [pdf]

B. Kiefer, H.-U. Krieger, and M.-J. Nederhof. Efficient and robust parsing of word hypotheses graphs. In W. Wahlster, editor, Verbmobil: Foundations of Speech-to-Speech Translation, pages 280-295. Springer-Verlag, 2000.

M. A. Alonso Pardo, M.-J. Nederhof, and E. Villemonte de la Clergerie. Tabulation of automata for tree-adjoining languages. Grammars, 3:89-110, 2000. [ps]

1999

E. Bertsch and M.-J. Nederhof. On failure of the pruning technique in ``Error Repair in Shift-Reduce Parsers''. ACM Transactions on Programming Languages and Systems, 21(1):1-10, January 1999. [pdf]

M.-J. Nederhof. Models of tabulation for TAG parsing. In Sixth Meeting on Mathematics of Language, pages 143-158, University of Central Florida, Orlando, Florida USA, July 1999. [pdf]

M.-J. Nederhof. Efficient generation of random sentences. In Encyclopedia of Computer Science and Technology, volume 41, pages 45-65. Marcel Dekker, 1999. [pdf]

M.-J. Nederhof. The computational complexity of the correct-prefix property for TAGs. Computational Linguistics, 25(3):345-360, September 1999. [pdf]

E. Bertsch and M.-J. Nederhof. Regular closure of deterministic languages. SIAM Journal on Computing, 29(1):81-102, 1999. [pdf]

M.-J. Nederhof and E. Bertsch. An innovative finite state concept for recognition and parsing of context free languages. In A. Kornai, editor, Extended finite state models of language, chapter 18, pages 226-243. Cambridge University Press, 1999. [pdf]

G. van Noord, G. Bouma, R. Koeling, and M.-J. Nederhof. Robust grammatical analysis for spoken dialogue systems. Natural Language Engineering, 5(1):45-93, 1999.

1998

M.-J. Nederhof. Linear indexed automata and tabulation of TAG parsing. In Actes des premières journées sur la Tabulation en Analyse Syntaxique et Déduction (Tabulation in Parsing and Deduction), pages 1-9, Paris, France, April 1998. [pdf]

M.-J. Nederhof. Context-free parsing through regular approximation. In Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pages 13-24, Ankara, Turkey, June/July 1998. [pdf]

M.-J. Nederhof. An alternative LR algorithm for TAGs. In 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, volume 2, pages 946-952, Montreal, Quebec, Canada, August 1998. [pdf]

M.-J. Nederhof, A. Sarkar and G. Satta. Prefix Probabilities from Stochastic Tree Adjoining Grammar. In 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, volume 2, pages 953-959, Montreal, Quebec, Canada, August 1998. [pdf]

M.-J. Nederhof, A. Sarkar and G. Satta. Prefix Probabilities for Linear Indexed Grammars. In Fourth International Workshop on Tree Adjoining Grammars and Related Frameworks, pages 116-119. Institute for Research in Cognitive Science, University of Pennsylvania, August 1998. IRCS Report 98-12. [pdf]

1997

M.J. Nederhof, G. Bouma, R. Koeling, and G. van Noord. Grammatical analysis in the OVIS spoken-dialogue system. In Interactive Spoken Dialog Systems: Bringing Speech and NLP Together in Real Applications, Proceedings of a Workshop Sponsored by the Association for Computational Linguistics, pages 66-73, Madrid, Spain, July 1997. [link]

M.-J. Nederhof and G. Satta. A variant of Earley parsing. In AI*IA 97: Advances in Artificial Intelligence, 5th Congress of the Italian Association for Artificial Intelligence, Lecture Notes in Artificial Intelligence, volume 1321, pages 84-95, Rome, Italy, September 1997. Springer-Verlag. [link]

1996

G. Bouma, R. Koeling, M.J. Nederhof, and G. van Noord. Grammatical analysis in a spoken dialogue system. In R. Jonkers, E. Kaan, and A. Wiegel, editors, Language and Cognition 5, Yearbook 1995 of the research group for Theoretical and Experimental Linguistics of the University of Groningen, pages 27-44. 1996.

M.-J. Nederhof and J.J. Sarbo. Increasing the applicability of LR parsing. In H. Bunt and M. Tomita, editors, Recent Advances in Parsing Technology, chapter 3, pages 35-57. Kluwer Academic Publishers, 1996. [pdf]

M.-J. Nederhof and G. Satta. Efficient tabular LR parsing. In 34th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 239-246, Santa Cruz, California, USA, June 1996. [link]

M.-J. Nederhof. Introduction to finite-state techniques. In Lecture notes to master class: Finite-State Techniques in NLP, pages 1-19, University of Groningen, July 1996.

M.-J. Nederhof and E. Bertsch. Linear-time suffix parsing for deterministic languages. Journal of the ACM, 43(3):524-554, 1996.

M.-J. Nederhof. On the borderline between finite and infinite argument domains. In C.H.A. Koster and E. Oltmans, editors, Proceedings of the first AGFL Workshop, Technical Report CSI-R9604, Computing Science Institute, pages 17-43, University of Nijmegen, January 1996.

M.-J. Nederhof. Reversible pushdown automata and bidirectional parsing. In J. Dassow, G. Rozenberg, and A. Salomaa, editors, Developments in Language Theory II, pages 472-481. World Scientific, Singapore, 1996. [pdf]

M.-J. Nederhof. Efficient generation of random sentences. Natural Language Engineering, 2(1):1-13, 1996.

M.J. Nederhof and E. Bertsch. An innovative finite state concept for recognition and parsing of context-free languages. Natural Language Engineering, 2(4):381-382, 1996.

1994

M.-J. Nederhof. An optimal tabular parsing algorithm. In 32nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 117-124, Las Cruces, New Mexico, USA, June 1994. [link]

M.-J. Nederhof and G. Satta. An extended theory of head-driven parsing. In 32nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 210-217, Las Cruces, New Mexico, USA, June 1994. [link]

M.J. Nederhof. Linguistic Parsing and Program Transformations. PhD thesis, University of Nijmegen, 1994. [pdf]

1993

M.-J. Nederhof and J.J. Sarbo. Efficient decoration of parse forests. In H. Trost, editor, Feature Formalisms and Linguistic Ambiguity, pages 53-78. Ellis Horwood, 1993.

M.-J. Nederhof. Generalized left-corner parsing. In Sixth Conference of the European Chapter of the Association for Computational Linguistics, Proceedings of the Conference, pages 305-314, Utrecht, The Netherlands, April 1993. [pdf]

M.-J. Nederhof and J.J. Sarbo. Partial evaluation grammars. Computer Languages, 18(2):137-151, 1993.

M.-J. Nederhof. A new top-down parsing algorithm for left-recursive DCGs. In Programming Language Implementation and Logic Programming, 5th International Symposium, Lecture Notes in Computer Science, volume 714, pages 108-122, Tallinn, Estonia, August 1993. Springer-Verlag.

1992

C. Dekkers, C.H.A. Koster, M.-J. Nederhof, and A. van Zwol. Manual for the Grammar WorkBench Version 1.5. Technical Report no. 92-14, University of Nijmegen, Department of Computer Science, July 1992.

M.-J. Nederhof, C.H.A. Koster, C. Dekkers, and A. van Zwol. The Grammar Workbench: A first step towards lingware engineering. In W. ter Stal, A. Nijholt, and H.J. op den Akker, editors, Linguistic Engineering: Tools and Products, Proc. of the second Twente Workshop on Language Technology, pages 103-115. University of Twente, April 1992. Memoranda Informatica 92-29.

M.-J. Nederhof and K. Koster. A customized grammar workbench. In J. Aarts, P. de Haan, and N. Oostdijk, editors, English Language Corpora: Design, Analysis and Exploitation, Papers from the thirteenth International Conference on English Language Research on Computerized Corpora, pages 163-179, Nijmegen, 1992. Rodopi.

C. Dekkers, M.-J. Nederhof, and J.J. Sarbo. Coping with ambiguity in decorated parse forests. In Coping with Linguistic Ambiguity in Typed Feature Formalisms, Proceedings of a Workshop held at ECAI 92, pages 11-19, Vienna, Austria, August 1992.

1991

H. Geuvers and M.-J. Nederhof. Modular proof of strong normalization for the calculus of constructions. Journal of Functional Programming, 1(2):155-189, April 1991.