An observation on time-storage trade off
From MaRDI portal
Publication:1217591
DOI10.1016/S0022-0000(74)80046-2zbMath0306.68026OpenAlexW2061739322MaRDI QIDQ1217591
Publication date: 1974
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(74)80046-2
Related Items
An introduction to parallelism in combinatorial optimization, On the Average Case Complexity of Some P-complete Problems, Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies, The incremental maintenance of a depth-first-search tree in directed acyclic graphs, Linearisability on Datalog programs, Generalized quantifiers and pebble games on finite structures, Branching Programs for Tree Evaluation, Parallel complexity of logical query programs, Communication Lower Bounds via Critical Block Sensitivity, A topological approach to dynamic graph connectivity, Unnamed Item, White pebbles help, Alternating multihead finite automata, Bounded arity Datalog \((\neq)\) queries on graphs, Can datalog be approximated?, On iterative and cellular tree arrays, Frontiers of tractability for typechecking simple XML transformations, On the minimization of XML schemas and tree automata for unranked trees, A space efficient algorithm for the monotone planar circuit value problem, The space complexity of pebble games on trees, \(\varepsilon\)-productions in context-free grammars, A comparison of two variations of a pebble game on graphs, The size and depth of layered Boolean circuits, Classifying the computational complexity of problems, Pebble games for studying storage sharing, Upper and lower I/O bounds for pebbling \(r\)-pyramids, The maximum flow problem is log space complete for P, Definability by programs in first-order structures, Incremental branching programs, On the cost of recomputing: tight bounds on pebbling with faults, Typechecking top-down XML transformations: Fixed input or output schemas, Upper and Lower I/O Bounds for Pebbling r-Pyramids, Pebbling dynamic graphs in minimal space, Oracle branching programs and Logspace versus \(P^*\), Directed hypergraphs: introduction and fundamental algorithms -- a survey, Infinitary logics and 0-1 laws, Why a single parallelization strategy is not enough in knowledge bases, Producing and verifying extremely large propositional refutations, On the complexity of typechecking top-down XML transformations, Storage requirements for deterministic polynomial time recognizable languages, A characterization of the power of vector machines, Two dynamic programming algorithms for which interpreted pebbling helps, Complete problems for deterministic polynomial time, Bracket-languages are recognizable in logarithmic space, Infinitary logic for computer science, Nullstellensatz size-degree trade-offs from reversible pebbling, Using Fifth Generation Tools for Solving the Clique Number Problem, Positive versions of polynomial time, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, On the cost of recomputing: Tight bounds on pebbling with faults, Bandwidth and pebbling, Nullstellensatz size-degree trade-offs from reversible pebbling, Bandwidth constraints on problems complete for polynomial time, Characterizations and computational complexity of systolic trellis automata, Depth-first search is inherently sequential, Program schemes, arrays, Lindström quantifiers and zero-one laws, Context-sensitive transitive closure operators, MaxSAT Resolution and Subcube Sums
Cites Work
