@inproceedings{boullier-1995-yet,
    title = "Yet Another $0(n^6)$ Recognition Algorithm for Mildly Context-Sensitive Languages",
    author = "Boullier, Pierre",
    editor = "Hajicova, Eva  and
      Lang, Bernard  and
      Berwick, Robert  and
      Bunt, Harry  and
      Carpenter, Bob  and
      Church, Ken  and
      Joshi, Aravind  and
      Kaplan, Ronald  and
      Kay, Martin  and
      Nagao, Makoto  and
      Nijholt, Anton  and
      Steedman, Mark  and
      Thompson, Henry  and
      Tomita, Masaru  and
      Vijay-Shanker, K.  and
      Wilks, Yorick  and
      Wittenburg, Kent",
    booktitle = "Proceedings of the Fourth International Workshop on Parsing Technologies",
    month = sep # " 20-24",
    year = "1995",
    address = "Prague and Karlovy Vary, Czech Republic",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/add-emnlp-2024-awards/1995.iwpt-1.7/",
    pages = "34--47",
    abstract = "Vijay-Shanker and Weir have shown in [17] that Tree Adjoining Grammars and Combinatory Categorial Grammars can be transformed into equivalent Linear Indexed Grammars (LIGs) which can be recognized in $0(n^6)$ time using a Cocke-Kasami-Younger style algorithm. This paper exhibits another recognition algorithm for LIGs, with the same upper-bound complexity, but whose average case behaves much better. This algorithm works in two steps: first a general context-free parsing algorithm (using the underlying context-free grammar) builds a shared parse forest, and second, the LIG properties are checked on this forest. This check is based upon the composition of simple relations and does not require any computation of symbol stacks."
}