%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:43:03 +0100 GMT
%    
% Selection : Author: Mark-Jan_Nederhof
%




@Article{Alonso Pardo_et_al:2000,
      AUTHOR = {Alonso Pardo, Miguel and Nederhof, Mark-Jan and Villemonte de la Clergerie, Eric},
      TITLE = {Tabulation of Automata for Tree-Adjoining Languages},
      YEAR = {2000},
      JOURNAL = {Grammars},
      VOLUME = {3},
      PAGES = {89-110},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00c.ps.gz},
      ABSTRACT = {We propose a modular design of tabular parsing algorithms for tree-adjoining languages. The modularity is made possible by a separation of the parsing strategy from the mechanism of tabulation. The parsing strategy is expressed in terms of the construction of a nondeterministic automaton from a grammar; three distinct types of automaton will be discussed. The mechanism of tabulation leads to the simulation of these nondeterministic automata in polynomial time, independent of the parsing strategy. The proposed application of this work is the design of efficient parsing algorithms for tree-adjoining grammars and related formalisms.},
      ANNOTE = {COLIURL : Pardo:2000:TAT.pdf Pardo:2000:TAT.ps}
}

@Article{Bertsch_Nederhof:1999,
      AUTHOR = {Bertsch, Eberhard and Nederhof, Mark-Jan},
      TITLE = {On Failure of the Pruning Technique in Error Repair in Shift-Reduce Parsers},
      YEAR = {1999},
      JOURNAL = {ACM Transactions on Programming Languages and Systems (TOPLAS)},
      VOLUME = {21},
      NUMBER = {1},
      PAGES = {1-10},
      URL = {http://www.dfki.de/dfkibib/publications/docs/nederhof99d.ps.gz},
      ABSTRACT = {A previous article presented a technique to compute the least-cost error repair by incrementally generating congurations that result from inserting and deleting tokens in a syntactically incorrect input. An additional mechanism to improve the run-time efficiency of this algorithm by pruning some of the congurations was discussed as well. In this communication we show that the pruning mechanism may lead to suboptimal repairs or may block all repairs. Certain grammatical errors in a common construct of the Java programming language also lead to the above kind of failure.},
      ANNOTE = {COLIURL : Bertsch:1999:FPT.pdf Bertsch:1999:FPT.ps}
}

@Article{Bertsch_Nederhof:1999_1,
      AUTHOR = {Bertsch, Eberhard and Nederhof, Mark-Jan},
      TITLE = {Regular Closure of Deterministic Languages},
      YEAR = {1999},
      JOURNAL = {SIAM Journal on Computing},
      VOLUME = {29},
      NUMBER = {1},
      PAGES = {81-102},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99c.entry ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99c.ps.gz},
      ABSTRACT = {We recall the notion of regular closure of classes of languages. We present two important results. The first result is that all languages which are in the regular closure of the class of deterministic (context-free) languages can be recognized in linear time. This is a nontrivial result, since this closure contains many inherently ambiguous languages. The second result is that the class of deterministic languages is contained in the closure of the class of deterministic languages with the prefix property or, stated in an equivalent way, all LR(k) languages are in the regular closure of the class of LR(0) languages.},
      ANNOTE = {COLIURL : Bertsch:1999:RCD.pdf Bertsch:1999:RCD.ps}
}

@Article{Bertsch_Nederhof:2001,
      AUTHOR = {Bertsch, Eberhard and Nederhof, Mark-Jan},
      TITLE = {Size/ Lookahead Tradeoff for LL(k)-Grammars},
      YEAR = {2001},
      JOURNAL = {Information Processing Letters},
      VOLUME = {80},
      PAGES = {125-129},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01d.ps.gz},
      ABSTRACT = {For a family of languages a precise tradeoff relationship between the size of LL(k) grammars and the length k of lookahead is demonstrated.},
      ANNOTE = {COLIURL : Bertsch:2001:SLT.pdf Bertsch:2001:SLT.ps}
}

@InProceedings{Bertsch_Nederhof:2001_1,
      AUTHOR = {Bertsch, Eberhard and Nederhof, Mark-Jan},
      TITLE = {On the Complexity of some Extensions of RCG Parsing},
      YEAR = {2001},
      BOOKTITLE = {Proceedings of the 7th International Workshop on Parsing Technologies (IWPT'01), October 17-19},
      PAGES = {66-77},
      ADDRESS = {Beijing, China},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01c.ps.gz},
      ABSTRACT = {We consider the parsing problem for range concatenation grammars (RCGs). Two new applications of RCG parsing are studied. The first is the parsing of finite automata, the second is string-to-string transduction, with an extension of RCGs. We show that these problems are undecidable in general, but become tractable for subclasses of the formalism.},
      ANNOTE = {COLIURL : Bertsch:2001:CSE.pdf Bertsch:2001:CSE.ps}
}

@InCollection{Kiefer_et_al:2000,
      AUTHOR = {Kiefer, Bernd and Krieger, Hans-Ulrich and Nederhof, Mark-Jan},
      TITLE = {Efficient and Robust Parsing of Word Hypotheses Graphs},
      YEAR = {2000},
      BOOKTITLE = {Verbmobil: Foundations of Speech-to-Speech Translation},
      PAGES = {280-295},
      EDITOR = {Wahlster, Wolfgang},
      ADDRESS = {Berlin},
      PUBLISHER = {Springer},
      ABSTRACT = {This paper describes new and improved techniques which help a unification-based parser to process input efficiently and robustly. In combination these methods result in a speed-up in parsing time of more than an order of magnitude. The methods are correct in the sense that none of them rule out legal rule applications.}
}

@InCollection{Mohri_Nederhof:2001,
      AUTHOR = {Mohri, Mehryar and Nederhof, Mark-Jan},
      TITLE = {Regular Approximation of Context-Free Grammars through Transformation},
      YEAR = {2001},
      BOOKTITLE = {Robustness in Language and Speech Technology},
      PAGES = {153--163},
      EDITOR = {Junqua, Jean-Claude and van Noord, Gertjan},
      ADDRESS = {Dordrecht},
      PUBLISHER = {Kluwer Academic Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01b.ps.gz},
      ABSTRACT = {We present an algorithm for approximating context-free languages with regular languages. The algorithm is based on a simple transformation that applies to any context-free grammar and guarantees that the result can be compiled into a finite automaton. The resulting grammar contains at most one new nonterminal for any nonterminal symbol of the input grammar. The result thus remains readable and if necessary modifiable. We extend the approximation algorithm to the case of weighted context-free grammars. We also report experiments with several grammars showing that the size of the minimal deterministic automata accepting the resulting approximations is of practical use for applications such as speech recognition.},
      ANNOTE = {COLIURL : Mohri:2001:RAC.pdf Mohri:2001:RAC.ps}
}

@InProceedings{Nederhof:1997,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Regular Approximations of CFLs: A Grammatical View},
      YEAR = {1997},
      BOOKTITLE = {International Workshop on Parsing Technologies (IWPT '97), September 17-20},
      ADDRESS = {Boston, USA}
}

@InProceedings{Nederhof:1998,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {An Alternative LR Algorithm for TAGs},
      YEAR = {1998},
      BOOKTITLE = {17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association for Computational Linguistics (COLING-ACL '98), August 10-14},
      VOLUME = {2},
      PAGES = {946-952},
      EDITOR = {ACL},
      ADDRESS = {Montréal, Québec, Canada},
      PUBLISHER = {Morgan Kaufmann Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98b.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98b.entry},
      ANNOTE = {COLIURL : Nederhof:1998:ALA.pdf Nederhof:1998:ALA.ps}
}

@InProceedings{Nederhof:1998_1,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Linear Indexed Automata and Tabulation of TAG Parsing},
      YEAR = {1998},
      BOOKTITLE = {Premières Journées sur la Tabulation en Analyse Syntaxique et Déduction/ 1st Workshop on Tabulation in Parsing and Deduction (TAPD '98), April 2-3},
      PAGES = {1-9},
      ADDRESS = {Paris, France},
      URL = {http://www.dfki.de/dfkibib/publications/docs/nederhof98e.ps.gz},
      ANNOTE = {COLIURL : Nederhof:1998:LIA.pdf Nederhof:1998:LIA.ps}
}

@InProceedings{Nederhof:1998_2,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Context-Free Parsing Through Regular Approximation},
      YEAR = {1998},
      BOOKTITLE = {1st International Workshop on Finite State Methods in Natural Language Processing (FSMNLP '98), June 29 - July 1},
      PAGES = {13-24},
      ADDRESS = {Bilkent University, Ankara, Turkey},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98a.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98a.entry},
      ANNOTE = {COLIURL : Nederhof:1998:CFP.pdf Nederhof:1998:CFP.ps}
}

@InProceedings{Nederhof:1999,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Models of Tabulation for TAG Parsing},
      YEAR = {1999},
      BOOKTITLE = {Proceedings of the 6th Meeting on Mathematics of Language (MOL6), July 23-25},
      PAGES = {143-158},
      ADDRESS = {Orlando, Florida, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/mol99.ps ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/mol99.entry},
      ANNOTE = {COLIURL : Nederhof:1999:MTT.pdf Nederhof:1999:MTT.ps}
}

@Article{Nederhof:1999_1,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {The Computational Complexity of the Correct-Prefix Property for TAGs},
      YEAR = {1999},
      JOURNAL = {Computational Linguistics},
      VOLUME = {25},
      NUMBER = {3},
      PAGES = {345-360},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99b.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99b.entry},
      ANNOTE = {COLIURL : Nederhof:1999:CCC.pdf Nederhof:1999:CCC.ps}
}

@InCollection{Nederhof:1999_2,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Efficient Generation of Random Sentences},
      YEAR = {1999},
      BOOKTITLE = {An Encyclopedia of Computer Science and Technology},
      VOLUME = {41},
      PAGES = {45-65},
      PUBLISHER = {Marcel Dekker Verlag},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99a.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof99a.entry},
      ANNOTE = {COLIURL : Nederhof:1999:EGR.pdf Nederhof:1999:EGR.ps}
}

@Article{Nederhof:2000,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Practical Experiments with Regular Approximation of Context-Free Languages},
      YEAR = {2000},
      JOURNAL = {Computational Linguistics},
      VOLUME = {26},
      NUMBER = {1},
      PAGES = {17-44},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00.entry},
      ANNOTE = {COLIURL : Nederhof:2000:PER.pdf Nederhof:2000:PER.ps}
}

@InProceedings{Nederhof:2000_1,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Preprocessing for Unification Parsing of Spoken Language},
      YEAR = {2000},
      BOOKTITLE = {Proceedings of the Natural Language Processing - NLP 2000, June 2-4},
      NUMBER = {1835},
      PAGES = {118-129},
      EDITOR = {Christodoulakis, Dimitris},
      SERIES = {Lecture Notes in Artificial Intelligence},
      ADDRESS = {Patras, Greece},
      PUBLISHER = {Springer},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00a.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00a.entry},
      ANNOTE = {COLIURL : Nederhof:2000:PUP.pdf Nederhof:2000:PUP.ps}
}

@InProceedings{Nederhof:2000_2,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Preprocessing for Unification Parsing of Spoken Language},
      YEAR = {2000},
      BOOKTITLE = {Proceedings of the Natural Language Processing - NLP 2000, June 2-4},
      NUMBER = {1835},
      PAGES = {118-129},
      EDITOR = {Christodoulakis, Dimitris},
      SERIES = {Lecture Notes in Artificial Intelligence},
      ADDRESS = {Patras, Greece},
      PUBLISHER = {Springer},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00a.ps.gz},
      ABSTRACT = {Wordgraphs are structures that may be output by speech recognizers. We discuss various methods for turning wordgraphs into smaller structures. One of these methods is novel; this method relies on a new kind of determinization of acyclic weighted finite automata that is language-preserving but not fully weight-preserving, and results in smaller automata than in the case of traditional determinization of weighted finite automata. We present empirical data comparing the respective methods. The methods are relevant for systems in which wordgraphs form the input to kinds of syntactic analysis that are very time consuming, such as unification parsing.},
      ANNOTE = {COLIURL : Nederhof:2000:PUPa.pdf Nederhof:2000:PUPa.ps}
}

@InCollection{Nederhof:2000_3,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Regular Approximation of CFLs: A Grammatical View},
      YEAR = {2000},
      BOOKTITLE = {Advances in Probabilistic and other Parsing Technologies},
      PAGES = {221-241},
      EDITOR = {Bunt, Harry and Nijholt, Anton},
      PUBLISHER = {Kluwer Academic Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00b.ps.gz},
      ABSTRACT = {We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from some existing methods of approximation in that use of a pushdown automaton is avoided. This allows better insight into how the generated language is affected.},
      ANNOTE = {COLIURL : Nederhof:2000:RACa.pdf Nederhof:2000:RACa.ps}
}

@InProceedings{Nederhof:2001,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Approximating Context-Free by Rational Transduction for Example-Based MT},
      YEAR = {2001},
      BOOKTITLE = {Proceedings of the 39th Annual Meeting and 10th Conference of the European Chapter, Workshop proceedings: Data-Driven Machine Translation, July 5-11},
      PAGES = {25-32},
      ADDRESS = {Toulouse, France},
      PUBLISHER = {Morgan Kaufmann Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01.ps.gz},
      ABSTRACT = {Existing studies show that a weighted context-free transduction of reasonable quality can be effectively learned from examples. This paper investigates the approximation of such transduction by means of weighted rational transduction. The advantage is increased processing speed, which benefits real-time applications involving spoken language.},
      ANNOTE = {COLIURL : Nederhof:2001:ACFa.pdf Nederhof:2001:ACFa.ps}
}

@InCollection{Nederhof:2000_4,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Regular Approximation of CFLs: A Grammatical View},
      YEAR = {2000},
      BOOKTITLE = {Advances in Probabilistic and other Parsing Technologies},
      PAGES = {221-241},
      EDITOR = {Bunt, Harry and Nijholt, Anton},
      PUBLISHER = {Kluwer Academic Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00b.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof00b.entry},
      ANNOTE = {COLIURL : Nederhof:2000:RAC.pdf Nederhof:2000:RAC.ps}
}

@InProceedings{Nederhof:2001_1,
      AUTHOR = {Nederhof, Mark-Jan},
      TITLE = {Approximating Context-Free by Rational Transduction for Example-Based MT},
      YEAR = {2001},
      BOOKTITLE = {Proceedings of the 39th Annual Meeting and 10th Conference of the European Chapter, Workshop proceedings: Data-Driven Machine Translation, July 5-11},
      PAGES = {25-32},
      EDITOR = {ACL},
      ADDRESS = {Toulouse, France},
      PUBLISHER = {Morgan Kaufmann Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof01.entry},
      ANNOTE = {COLIURL : Nederhof:2001:ACF.pdf Nederhof:2001:ACF.ps}
}

@InProceedings{Nederhof_et_al:1998,
      AUTHOR = {Nederhof, Mark-Jan and Sarkar, Anoop and Satta, Giorgio},
      TITLE = {Prefix Probabilities for Linear Indexed Grammars},
      YEAR = {1998},
      BOOKTITLE = {4th International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+4), August 1-3},
      NUMBER = {98-12},
      PAGES = {116-119},
      SERIES = {IRCS Report},
      ADDRESS = {University of Pennsylvania, Philadelphia, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98d.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98d.entry},
      ANNOTE = {COLIURL : Nederhof:1998:PPL.pdf Nederhof:1998:PPL.ps}
}

@InProceedings{Nederhof_Satta:2000,
      AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
      TITLE = {Left-To-Right Parsing and Bilexical Context-Free Grammars},
      YEAR = {2000},
      BOOKTITLE = {Proceedings of the 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics (ANLP-NAACL '00), April 29 - May 3},
      PAGES = {272-279},
      EDITOR = {Nirenburg, Sergei and Appelt, Douglas and Ciravegna, Fabio and Dale, Robert},
      ADDRESS = {Seattle, Washington, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof-satta00.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof-satta00.entry},
      ANNOTE = {COLIURL : Nederhof:2000:LRP.pdf Nederhof:2000:LRP.ps}
}

@InCollection{Nederhof_Bertsch:1999,
      AUTHOR = {Nederhof, Mark-Jan and Bertsch, Eberhard},
      TITLE = {An Innovative Finite State Concept for Recognition and Parsing of Context-Free Languages},
      YEAR = {1999},
      BOOKTITLE = {Extended Finite State Models of Language},
      PAGES = {226-243},
      EDITOR = {Kornai, A.},
      ADDRESS = {Stanford},
      PUBLISHER = {Cambridge University Press},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nebe99.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nebe99.entry},
      ANNOTE = {COLIURL : Nederhof:1999:IFS.pdf Nederhof:1999:IFS.ps}
}

@InProceedings{Nederhof_et_al:1998_1,
      AUTHOR = {Nederhof, Mark-Jan and Sarkar, Anoop and Satta, Giorgio},
      TITLE = {Prefix Probabilities from Stochastic Tree Adjoining Grammar},
      YEAR = {1998},
      BOOKTITLE = {Proceedings of the 17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association on Computational Linguistics (COLING-ACL '98), August 10-14},
      VOLUME = {2},
      PAGES = {953-959},
      EDITOR = {ACL},
      ADDRESS = {Montréal, Québec, Canada},
      PUBLISHER = {Morgan Kaufmann Publishers},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98c.ps.gz ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98c.entry},
      ANNOTE = {COLIURL : Nederhof:1998:PPS.pdf Nederhof:1998:PPS.ps}
}

@InProceedings{Nederhof_et_al:1998_2,
      AUTHOR = {Nederhof, Mark-Jan and Sarkar, Anoop and Satta, Giorgio},
      TITLE = {Prefix Probabilities for Linear Indexed Grammars},
      YEAR = {1998},
      BOOKTITLE = {Proceedings of the 4th International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+4), August 1-3},
      NUMBER = {98-12},
      PAGES = {116-119},
      SERIES = {IRCS Report},
      ADDRESS = {University of Pennsylvania, Philadelphia, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof98d.ps.gz},
      ABSTRACT = {We show how prefix probabilities can be computed for stochastic linear indexed grammars (SLIGs). Our results apply as well to stochastic tree-adjoining grammars (STAGs), due to their equivalence to SLIGs.},
      ANNOTE = {COLIURL : Nederhof:1998:PPLb.pdf Nederhof:1998:PPLb.ps}
}

@InProceedings{Nederhof_Satta:1997,
      AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
      TITLE = {A Variant of Earley Parsing},
      YEAR = {1997},
      BOOKTITLE = {Advances in Artificial Intelligence. 5th Conference of the Italian Association for Artificial Intelligence (AI*IA 97), September 17-19},
      NUMBER = {1321},
      PAGES = {84-95},
      EDITOR = {Lenzerini, Maurizio},
      SERIES = {Lecture Notes in Artificial Intelligence},
      ADDRESS = {Rome, Italy},
      PUBLISHER = {Springer Verlag},
      URL = {http://lanl.arxiv.org/PS_cache/cmp-lg/pdf/9808/9808017.pdf},
      ANNOTE = {COLIURL : Nederhof:1997:VEP.pdf}
}

@InProceedings{Nederhof_Satta:2000_1,
      AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
      TITLE = {Left-To-Right Parsing and Bilexical Context-Free Grammars},
      YEAR = {2000},
      BOOKTITLE = {Proceedings of the 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics (ANLP-NAACL'00), April 29 - May 3},
      PAGES = {272-279},
      EDITOR = {Nirenburg, Sergei and Appelt, Douglas and Ciravegna, Fabio and Dale, Robert},
      ADDRESS = {Seattle, Washington, USA},
      URL = {ftp://lt-ftp.dfki.uni-sb.de/pub/papers/local/nederhof-satta00.ps.gz},
      ABSTRACT = {We compare the asymptotic time complexity of left-to-right and bidirectional parsing techniques for bilexical context-free grammars, a grammar formalism that is an abstraction of language models used in several state-of-the-art real-world parsers. We provide evidence that left-to-right parsing cannot be realised within acceptable time-bounds if the so called correct-prefix property is to be ensured. Our evidence is based on complexity results for the representation of regular languages.},
      ANNOTE = {COLIURL : Nederhof:2000:LRPb.pdf Nederhof:2000:LRPb.ps}
}

@InProceedings{Nederhof_Satta:2002,
      AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
      TITLE = {Parsing Non-Recursive Context-Free Grammars},
      YEAR = {2002},
      BOOKTITLE = {Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL ANNUAL'02), July 7-12},
      PAGES = {112-119},
      ADDRESS = {Philadelphia, Pennsylvania, USA},
      URL = {http://www.dfki.de/dfkibib/publications/docs/nederhof02d.ps},
      ABSTRACT = {We consider the problem of parsing nonrecursive contextfree grammars, i.e., contextfree grammars that generate finite languages. In natural language processing, this problem arises in several areas of application, including natural language generation, speech recognition and machine translation. We present two tabular algorithms for parsing of nonrecursive contextfree grammars, and show that they perform well in practical settings, despite the fact that this problem is PSPACE complete.},
      ANNOTE = {COLIURL : Nederhof:2002:PNR.pdf Nederhof:2002:PNR.ps}
}

@Article{van Noord_et_al:1999,
      AUTHOR = {van Noord, Gertjan and Bouma, Gosse and Koeling, Rob and Nederhof, Mark-Jan},
      TITLE = {Robust Grammatical Analysis for Spoken Dialogue Systems},
      YEAR = {1999},
      JOURNAL = {Natural Language Engineering},
      VOLUME = {5},
      NUMBER = {1},
      PAGES = {45-93},
      URL = {http://odur.let.rug.nl/~vannoord/papers/nle/},
      ABSTRACT = {We argue that grammatical analysis is a viable alternative to concept spotting for processing spoken input in a practical spoken dialogue system. We discuss the structure of the grammar, and a model for robust parsing which combines linguistic sources of information and statistical sources of information. We discuss test results suggesting that grammatical processing allows fast and accurate processing of spoken input.}
}