Lower bounds on space complexity for contextfree recognition |
| |
Authors: | Helmut Alt |
| |
Affiliation: | 1. Fachbereich 10, Universit?t des Saarlandes, D-6600, Saarbrücken, Germany (Fed. Rep.)
|
| |
Abstract: | Summary 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|