Complexity of Recognition in Intermediate-Level Languages
Complexity of Recognition in Intermediate-Level Languages
复制标题
中级语言识别的复杂性
DOI：
10.1109/swat.1973.5
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
W. Rounds
中科院分区：
文献类型：
--
作者：
W. Rounds
句子识别的复杂性研究了单向堆栈语言，索引语言，树转换语言。在每种情况下，该问题是多项式完全的。形式化了一类自然语言文法，证明了尽管语言是上下文敏感的，但其识别问题是多项式困难的。证明给出了可满足命题公式集和命题重言式集的新的语言理论刻画。
Complexity of sentence recognition is studied for one-way stack languages, indexed languages, and tree transducer languages. The problem is shown to be polynomial-complete in each case. A class of naturallanguage grammars is formalized and the sentence-recognition problem is shown to be polynomial-hard although the languages are context-sensitive. The proofs give new language-theoretic characterizations of the set of satisfiable propositional formulas and the set of prepositional tautologies.