Storage requirements for deterministic polynomial time recognizable languages

DOI10.1016/S0022-0000(76)80048-7MaRDI QIDQ1230508zbMATH OpenFDO

Authors Ravi Sethi, Stephen Cook

Publication date 1976

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

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3586493 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• An observation on time-storage trade off
• Characterization of flowchartable recursions
• Comparing complexity classes
• Complete Register Allocation Problems
• Recognition and parsing of context-free languages in time n3

Cited in

(14)

• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Characterizations and computational complexity of systolic trellis automata
• An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
• White pebbles help
• A comparison of two variations of a pebble game on graphs
• Min Cut is NP-complete for edge weighted trees
• On iterative and cellular tree arrays
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Cumulative space in black-white pebbling and resolution
• Branching Programs for Tree Evaluation
• On the power of white pebbles
• Pebble games for studying storage sharing
• Universal algebra and hardness results for constraint satisfaction problems
• The space complexity of pebble games on trees

This page was built for publication: Storage requirements for deterministic polynomial time recognizable languages

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