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
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
0.713112473487854
0 references
0.7119014859199524
0 references
0.7017852663993835
0 references
0.6888647675514221
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