Storage requirements for deterministic polynomial time recognizable languages
From MaRDI portal
Publication:1230508
DOI10.1016/S0022-0000(76)80048-7zbMath0337.68031MaRDI QIDQ1230508
Publication date: 1976
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68N01: General topics in the theory of software
Related Items
Cumulative Space in Black-White Pebbling and Resolution, Unnamed Item, Space characterizations of complexity measures and size-space trade-offs in propositional proof systems, Characterizations and computational complexity of systolic trellis automata, Universal algebra and hardness results for constraint satisfaction problems, Min Cut is NP-complete for edge weighted trees, White pebbles help, On iterative and cellular tree arrays, The space complexity of pebble games on trees, A comparison of two variations of a pebble game on graphs, Pebble games for studying storage sharing, On the power of white pebbles, Branching Programs for Tree Evaluation, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
Cites Work