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
      0 references
      1977
      0 references
      recognition of nonregular context-free languages
      0 references
      lower bound
      0 references
      required space
      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

      Identifiers