Paper Info
Title
A Tractable Extension of Linear Indexed Grammars
Abstract
Vijay-Shanker and Weir (1993) show that Linear Indexed Grammars (LIG) can be processed in polynomial time by exploit- ing constraints which make possible the extensive use of structure-sharing. This paper describes a formalism that is more powerful than LIG, but which can also be processed in polynomial time using similar techniques. The formalism, which we re- fer to as Partially Linear PATR (PLPATR) manipulates feature structures rather than stacks.
Year
DOI
Venue
1995
10.3115/976973.976985
conference of the european chapter of the association for computational linguistics
Keywords
Field
DocType
extensive use,similar technique,linear indexed grammars,tractable extension,polynomial time,feature structure,partially linear patr
Programming language,Computer science,Indexed grammar,Theoretical computer science,Artificial intelligence,Natural language processing,Formalism (philosophy),Time complexity,Machine learning
Journal
Volume
Citations 
PageRank 
cmp-lg/950
7
0.70
References 
Authors
12
2
Name
Order
Citations
PageRank
Bill Keller1876.26
David J. Weir284083.84