Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen (Q4151159)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3581613
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen |
scientific article; zbMATH DE number 3581613 |
Statements
Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen (English)
0 references
1977
0 references
recognition of nonregular context-free languages
0 references
lower bound
0 references
required space
0 references
0.7922807931900024
0 references
0.754677951335907
0 references
0.7486177682876587
0 references
0.7463588714599609
0 references
0.7439616918563843
0 references
As known, recognition of nonregular CF languages requires \(\log\log n\) space (and some can be recognized within this limit). The paper presents some classes of nonregular CF languages (e.g. deterministic, or so called strictly nonregular ones) for which the required space is \(\log n\). For the entire collection see [Zbl 0348.00019].
0 references