Theoretical Computer Science

← Back to Domain-Specific Abstractions by Domain

20 domain-specific abstractions whose origin domain is Theoretical Computer Science.

• Approximation Algorithm — A polynomial-time optimization algorithm that always returns a feasible solution with a proved worst-case quality bound relative to the optimum.
• Cell-Probe Model — A data-structure computation model that charges only for reading or writing fixed-width memory cells while treating all computation between probes as free, so lower bounds isolate unavoidable information-transfer cost.
• Computational complexity theory — The theory classifying computational problems by resource requirements and reductions under explicit models of computation.
• Computational problem — A formally specified relation between encoded instances and acceptable solutions sought by an algorithm.
• Enumeration Algorithm — Given an input and a declared solution relation, generate every associated solution without repetition, with performance evaluated by preprocessing, inter-output delay, incremental time, total output-sensitive time, and space.
• Formula Game — Evaluate a closed quantified Boolean formula as a perfect-information contest in which Existential and Universal assign their variables in prefix order and truth is equivalent to Existential having a winning strategy.
• Graph rewriting — Rule-based transformation of a host graph by matching a left-hand pattern and replacing or relinking it according to a right-hand graph.
• Isolation lemma — Assign independent random weights to elements of a finite set system so that, with a controlled positive probability, a nonempty family has a unique minimum-weight member.
• L-Reduction — Transfer approximation guarantees and hardness between optimization problems through polynomial instance and solution maps whose two fixed-constant inequalities control optimum scale and solution-error distortion.
• Left Recursion — A grammar nonterminal can derive itself again as the leftmost symbol before consuming input, a useful associativity idiom that naive top-down parsers cannot terminate on without transformation or special handling.
• LL Grammar — A context-free grammar whose next production in a leftmost derivation is uniquely determined while scanning input left-to-right with a fixed amount of lookahead.
• Markov algorithm — A deterministic ordered string-rewriting procedure that repeatedly applies the first applicable production, halting when no rule applies or a designated terminal rule fires.
• Random-Access Machine — Analyze algorithms on an abstract sequential computer with numbered registers and indirect addressing, making instruction set, word size, and operation-cost assumptions explicit.
• Randomized Rounding — Map a tractable fractional or convex relaxation into a distribution over discrete candidates whose marginals, correlations, and geometry retain enough of the relaxation to prove feasibility and approximation quality probabilistically.
• Small-bias sample space — A compact distribution on binary strings whose parity over every nonempty coordinate subset differs from uniform by at most ε, providing pseudorandomness against linear tests.
• Solomonoff Induction — Predict a continuation by Bayesianly mixing every computable generative hypothesis, giving shorter programs greater prior weight, with universality and convergence purchased at the cost of incomputability.
• Space Hierarchy Theorem — A complexity separation theorem showing that sufficiently larger constructible workspace bounds decide strictly more languages, in deterministic and nondeterministic forms.
• Subgraph Isomorphism Problem — Determine whether a target graph contains a structure-preserving copy of a pattern graph by finding an injective vertex mapping that preserves required adjacency, optionally also non-adjacency.
• Turmite — A two-dimensional Turing-machine model whose oriented finite-state agent reads and rewrites grid cells while turning and moving locally.
• Vector Addition System — An infinite-state transition system whose configurations are nonnegative integer counter vectors and whose finitely specified steps add integer displacement vectors only when no counter would become negative.