Computing theory: vocabulary and definitions (195 words)

This page gathers the 195 dictionary entries belonging to the domain “Computing theory”, as labelled by Wiktionary. Each word leads to its full entry: definitions, etymology, pronunciation, examples. Page 1 of 2: from “2-3 tree” to “metacircularity”.

2-3 tree noun A tree data structure whose every node with children (internal node) has either two children and one data element, or three children and…
2-3-4 tree noun A tree data structure whose every node with children (internal node) has either two, three or four child nodes: a 2-node has one data…
acceptor noun A kind of finite-state machine whose binary output indicates whether or not a received input was accepted.
alpha conversion noun One of the three rewrite rules of lambda calculus, in which a bound variable of a lambda term is replaced by another variable across its…
alpha-beta pruning noun An algorithm for pruning a search tree by eliminating any branch that is demonstrably inferior to a branch previously encountered.
antimessage noun A message in a distributed system whose purpose is to cancel out another specific message sent previously.
application noun The substitution of a specific value for the parameter in the abstraction, in lambda calculus.
artificial language noun A formal language.
B+ tree noun An m-ary tree data structure with a variable but often large number of children per node. It can be viewed as a B-tree in which each node…
backjumping noun A form of backtracking that may move more than one level at a time, used to improve the efficiency of certain algorithms.
backpatch verb To update (partially compiled code) with jump addresses that were previously left as placeholders because they had not yet been encountered…
bandelet noun An orthonormal basis that is adapted to geometric boundaries, used in image processing.
beta reduction noun One of the three rewrite rules of the lambda calculus, which states that the application of a lambda abstraction (λx.t) to a term s yields…
big O notation noun A particular notation, useful in the analysis of algorithms, which describes the limiting behavior of a function when the argument tends…
binary search noun A search for a value within a sorted array by repeatedly comparing the target value with the middle element; if they are unequal, the half…
bitonic adj Having the property x_0≤⋯≤x_k≥⋯≥x_n-1 for some k,0≤k<n, or being a circular shift of such a sequence.
Bloom filter noun A space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are…
bogosort noun An intentionally poor sorting algorithm that operates by randomly permuting the elements repeatedly until they happen to fall into the…
Brzozowski derivative noun The set of all strings obtainable from a given set of strings by cutting off a prefix. For example, for the set { cat, cow, dog }, the…
Büchi automaton noun A type of ω-automaton that extends a finite automaton to infinite inputs. It accepts an infinite input sequence if there exists a run of…
bucket sort noun A sorting algorithm that partitions an array into a number of buckets (groups of elements) which are then individually sorted, either…
buddy block noun A block of memory associated with another block and able to be merged with it, in the system of buddy memory allocation.
buddy memory allocation noun A form of memory allocation that divides memory into partitions to try to satisfy a memory request as suitably as possible.
buddy system noun The use of buddy memory allocation.
bundle adjustment noun A process used in the reconstruction of a three-dimensional model from a set of photographs, simultaneously refining the coordinates…
Burrows-Wheeler transform noun An algorithm used in data compression that rearranges a character string into runs of similar characters.
busy beaver noun A Turing machine that attains the maximum number of steps performed, or number of non-blank symbols finally on the tape, among all Turing…
busy beaver function noun The mathematical function, denoted by Σ(n), that maps each positive integer n to the number of steps required for the busy beaver among…
Canadian traveller problem noun A generalization of the shortest path problem to graphs that are only partially observable (i.e. the graph is revealed while it is being…
cellular automaton noun An automaton consisting of cells arranged in a regular grid, in one or more dimensions. Each application of an associated rule creates a…
certificate noun The information needed in order to verify a positive answer to a problem.
CFG noun Initialism of context-free grammar.
choice machine noun A type of computing model where the next action is not entirely determined by its current state and the symbol it reads.
Chomsky Normal Form noun A context-free grammar in which the right hand side of any production rule consists of either one terminal symbol or two non-terminal…
co-recursively enumerable adj Describing a set for which there exists a deterministic algorithm that will list all items not in that set.
collisionless adj Without the possibility of data packets colliding on the network.
complete adj That is in a given complexity class and is such that every other problem in the class can be reduced to it (usually in polynomial time or…
complexity function noun A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;
computable adj Of a problem, solvable by a Turing machine or any thereto Turing-equivalent model; Turing-computable.
cone noun A set of formal languages with certain desirable closure properties, in particular those of the regular languages, the context-free…
context-free grammar noun A formal grammar in which every production rule is such that the left-hand side is exactly one non-terminal symbol and the right-hand side…
coobservable adj Of a behaviour in a distributed system: such that decisions can be made by each site based on what it observes, without the need for input…
crisp adj Not using fuzzy logic; based on a binary distinction between true and false.
cubesort noun A parallel sorting algorithm that builds a self-balancing multidimensional array from the keys to be sorted.
cycle sort noun A sorting algorithm based on the idea that the permutation to be sorted can be factored into cycles that can be rotated individually to…
dancing links noun A technique for reverting the deletion of a node from a circular doubly-linked list, particularly useful for efficiently implementing…
Dantzig-Wolfe decomposition noun An algorithm for solving linear programming problems with special structure, relying on delayed column generation for improving the…
decide verb Of a Turing machine: to return a correct answer (for some yes-or-no problem) on every possible input.
decision problem noun A question in some formal system with a yes-or-no answer, depending on the values of input parameters.
decommit verb To deactivate or decommission.
decommitment noun Deactivation or decommission.
deforestation noun A transformation to eliminate intermediate data structures within a program.
denormal adj Smaller than the smallest normal number but larger than zero, thus serving to fill the underflow gap.
denormalized adj Denormal.
double dabble noun An algorithm that converts binary numbers into binary-coded decimal notation by means of shift and add operations.
downpointer noun A pointer in a hierarchical data structure that points to the node that is down from the current node.
downtree adj Lower in a tree data structure.
eager adj Not employing lazy evaluation; calculating results immediately, rather than deferring calculation until they are required.
eta conversion noun One of the three rewrite rules of lambda calculus, which expresses a sort of tautology about function application. The rule says that a…
false sharing noun A performance-degrading usage pattern where the size of units in a cache means that the system may reload entire units even when it is not…
family tree noun A data structure that organizes resources or machines in a distributed system, consisting of nodes connected by edges, in which each node…
finger noun A leaf in a finger tree data structure.
finger tree noun A purely functional tree-like data structure offering amortized constant time access to its "fingers" (leaves), used for the efficient…
finite-state machine noun A formalism for describing computation, consisting of a finite set of states and a transition function describing when to move from one…
first-fit adj Of or relating to a fast but non-optimal algorithm for the Bin packing problem, placing each item into the first bin in which it will fit.
Fletcher's checksum noun A kind of position-dependent checksum intended to provide error-detection properties approaching those of a cyclic redundancy check but…
formal language noun A set of finite strings (called words) made of symbols (from a finite set of symbols, called an alphabet).
frame problem noun The problem of finding an adequate collection of axioms making up a viable description of the world for a robot or artificial intelligence.
functional adj Having semantics defined purely in terms of mathematical functions, without side-effects.
fuzzy adj Employing or relating to fuzzy logic.
grammar noun A formal system specifying the syntax of a language.
hash tree noun A tree (data structure) in which every non-leaf node is labelled with the hash of the labels of its children.
Hindley-Milner type system noun A classical type system for the lambda calculus with parametric polymorphism, notable for its completeness and its ability to infer the…
Hoare logic noun A formal system of rules for reasoning about the correctness of computer programs, based on Hoare triples, which describe the state of the…
Hoare triple noun A formal description of how the execution of a piece of code changes the state of the computation in Hoare logic, consisting of a command…
hoist verb To extract (code) from a loop construct as part of optimization.
Huffman coding noun An entropy-encoding algorithm used for lossless data compression, involving a variable-length code table derived from the estimated…
imperative adj Having semantics that incorporates mutable variables.
inorder adj Of a tree traversal, recursively visiting the root in between the left and right subtrees.
jump list noun A kind of sorted linked list with additional pointers to connect data items that are various distances apart.
Karatsuba algorithm noun A fast multiplication algorithm that reduces the multiplication of two n-digit numbers to at most n^(log ₂₃)≈n^(1.585) single-digit…
Karp reduction noun A polynomial-time algorithm for transforming inputs to one problem into inputs to another problem, such that the transformed problem has…
Kleene plus noun The plus symbol, +, used as an operator to concatenate one or more strings from a given set, widely used in regular expressions.
Kleene star noun The asterisk, *, used as an operator to concatenate zero or more strings from a given set, widely used in regular expressions.
Kolmogorov complexity noun The complexity of an information object—such as a book or an image—informally defined as the length of the shortest program that produces…
lambda abstraction noun A lambda term of the form (λx.t) where x is a variable and t another lambda term. Any free instance of x within t (considered by itself)…
lambda calculus noun Any of a family of functionally complete algebraic systems in which lambda expressions are evaluated according to a fixed set of rules to…
Lamport timestamp noun A timestamp generated by a certain algorithm used to determine the order of events in a distributed system.
lazy adj Employing lazy evaluation; not calculating results until they are immediately required.
leaf node noun A node, in a tree, that has no children.
leafwise adj In terms of the leaves of a tree or similar data structure.
leaky bucket noun A counter or variable that is incremented whenever an event of interest occurs, and also periodically decremented; used in algorithms to…
linear congruential generator noun An algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation.
linear time noun The time complexity, denoted O(n), of an algorithm whose running time increases at most linearly with the size of the input.
liveness noun A set of properties of a concurrent system that require the system to make progress despite the fact that its concurrently executing…
lock convoy noun The undesirable situation where multiple threads of equal priority contend repeatedly for the same lock.
lock-free adj Not requiring the acquisition of a mutex (or other kind of) lock for synchronizing with other threads.
Mealy machine noun A finite-state machine whose output values are determined by both its current state and its current inputs.
mem noun A memory access as part of processing.
metacircularity noun The property of an interpreter that is written in the same programming language that it interprets, and that exploits homoiconicity to…

All domains · Search for a word