No label defined (Q3341935)

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 3876636
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3876636

      Statements

      0 references
      1983
      0 references
      context-free languages
      0 references
      algorithm for the recognition of input driven languages
      0 references
      space complexity
      0 references
      pebbling complexity
      0 references
      [For the entire collection see Zbl 0513.00010.] In this paper we present a log n space algorithm for the recognition of input driven languages. Our algorithm uses a black and white pebbling strategy [\textit{S. A. Cook} and \textit{R. Sethi}, J. Comput. Syst. Sci. 13, 25-37 (1976; Zbl 0337.68031)] of the computation graphs. The pebbles are distributed on the graph in such a way that their position needs not to be stored but can be recomputed. In this way our algorithm uses O(log n) pebbles, where each pebble requires only bounded space. Our approach gives a simple prove for the space complexity of a great subclass of DCFLs. In terms of pebbling complexity the strategy is optimal.
      0 references

      Identifiers