Membership for growing context-sensitive grammars is polynomial
作者:
Highlights:
•
摘要
A context-sensitive grammar is a growing context-sensitive grammar, if the right-hand side of every production is strictly longer than the left-hand side. We show that for any fixed growing context sensitive grammar, the membership problem for the corresponding language is polynomial.
论文关键词:
论文评审过程:Received 1 July 1985, Revised 10 March 1986, Available online 4 December 2003.
论文官网地址:https://doi.org/10.1016/0022-0000(86)90062-0