scientific article; zbMATH DE number 3876636

From MaRDI portal
Publication:3341935





[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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3341935)