LOWER BOUNDS ON SPACE COMPLEXITY FOR CONTEXT-FREE RECOGNITION

被引：11

作者：

ALT, H

机构：

[1] Fachbereich 10, Universität des Saarlandes, Saarbrücken

来源：

ACTA INFORMATICA | 1979年 / 12卷 / 01期

关键词：

D O I：

10.1007/BF00264016

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Using methods from linear algebra and crossing-sequence arguments it is shown that logarithmic space is necessary for the recognition of all context-free nonregular subsets of {a1}* ... {an}*, where {a1,...,an} is some alphabet. It then follows that log n is a lower bound on the space complexity for the recognition of any bounded or deterministic non-regular context-free language. © 1979 Springer-Verlag.

引用

页码：33 / 61

页数：29