A Tractable Extension of Linear Indexed Grammars
<|reference_start|>A Tractable Extension of Linear Indexed Grammars: It has been shown that Linear Indexed Grammars can be processed in polynomial time by exploiting constraints which make possible the extensive use of structure-sharing. This paper describes a formalism that is more powerful than Linear Indexed Grammar, but which can also be processed in polynomial time using similar techniques. The formalism, which we refer to as Partially Linear PATR manipulates feature structures rather than stacks.<|reference_end|>
@article{keller1995a,
    title={A Tractable Extension of Linear Indexed Grammars},
    author={Bill Keller and David Weir (School of Cognitive & Computing Sciences,
  University of Sussex, UK)},
    journal={arXiv preprint arXiv:cmp-lg/9502021},
    year={1995},
    archivePrefix={arXiv},
    eprint={cmp-lg/9502021},
    primaryClass={cmp-lg cs.CL}
}