scientific article; zbMATH DE number 3876636
[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.
- A new complete language for DSPACE(log n)
- Additive number theory via automata theory
- Weighted operator precedence languages
- Beyond operator-precedence grammars and languages
- Operator precedence temporal logic and model checking
- Trimming visibly pushdown automata
- The word problem for visibly pushdown languages described by grammars
- Operator precedence languages: their automata-theoretic and logic characterization
- Descriptional complexity of input-driven pushdown automata
- scientific article; zbMATH DE number 3885334 (Why is no real title available?)
- Sums of Palindromes: an Approach via Automata
- Temporal logic and model checking for operator precedence languages
- On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
- Sliding windows over context-free languages
- Higher-order operator precedence languages
- Input-driven double-head pushdown automata
- Weighted operator precedence languages
- Leaf languages and string compression
- Input-Driven Double-Head Pushdown Automata
- Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
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)