Storage requirements for deterministic polynomial time recognizable languages

DOI10.1016/S0022-0000(76)80048-7zbMath0337.68031MaRDI QIDQ1230508

Ravi Sethi, Stephen A. Cook

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01)

Related Items

Cumulative Space in Black-White Pebbling and Resolution, Branching Programs for Tree Evaluation, Min Cut is NP-complete for edge weighted trees, White pebbles help, On iterative and cellular tree arrays, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, The space complexity of pebble games on trees, Space characterizations of complexity measures and size-space trade-offs in propositional proof systems, A comparison of two variations of a pebble game on graphs, Pebble games for studying storage sharing, On the power of white pebbles, Universal algebra and hardness results for constraint satisfaction problems, Unnamed Item, Characterizations and computational complexity of systolic trellis automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An observation on time-storage trade off
• Comparing complexity classes
• Characterization of flowchartable recursions
• Complete Register Allocation Problems
• Recognition and parsing of context-free languages in time n3