Automata theory 2026-11-05
Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.
For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per and pop once per . These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.
Deterministic algorithm 2026-11-05
A deterministic algorithm has one prescribed next step for each permitted input and current computational state. Thus the same input and initial state give the same execution trace and, if execution terminates, the same output. This is a statement about the abstract transition rules, not about identical elapsed time on different computers.
Binary search with a fixed midpoint rule is deterministic: every comparison determines which remaining interval is searched next. Quicksort with a fixed pivot-selection rule is also deterministic, even though different inputs can produce very different running times. Determinism therefore does not imply a constant or small time complexity.
A randomized algorithm additionally receives random choices. Fixing its entire random-choice sequence makes its subsequent execution deterministic, but averaging over those choices is essential to its randomized guarantees. A Nondeterministic Turing machine is a different mathematical model: its branches describe possible computation paths, rather than a probability distribution supplied by an implementation.
John Hopcroft 2026-11-05
John Hopcroft gave a 1971 algorithm for minimizing deterministic finite automata with running time for states and alphabet . It refines partitions of states until states in the same block accept exactly the same continuation strings.[ref]
An n log n Algorithm for Minimizing States in a Finite Automaton by John Hopcroft. Introduction and Analysis of the running time
The key accounting idea is to organize refinement around smaller splitters. A transition can then be charged to only logarithmically many successively smaller blocks, instead of rescanning every state in every refinement round. DFA minimization preserves the recognized language while merging observationally equivalent states, making representation size and equivalence checking algorithmic questions.
John Hopcroft, portrait published by Cornell University
. Model of computation 2026-11-05
A model of computation specifies how inputs are represented, which states and operations are available, how execution proceeds and what counts as its output and resource cost. Examples include Turing machines, random-access machines, Boolean circuits and the lambda calculus. A mathematical algorithmic claim is interpreted within such a model, even when the model is left implicit.
For example, adding two integers is one instruction in a unit-cost machine model. In a bit-cost model, operating on arbitrarily long integers requires time depending on their encoded lengths. A bound counting arithmetic operations therefore need not be a bound on bit complexity. Likewise, a circuit family can supply separate hardware for each input length, while a uniformity requirement asks one algorithm to generate those circuits. Stating the model makes efficiency comparisons meaningful and separates questions of computability from the cost of a chosen representation.
State-space search 2026-11-05
A state-space search solves a problem by exploring a transition system: a state records the current situation, a transition relation specifies legal moves, and a goal state specifies success. The answer is usually a path in a transition system, rather than just the final configuration. This separates modeling the problem from choosing the search algorithm.
For a sliding-tile puzzle, the state is the arrangement of tiles and the empty square; one move slides a neighboring tile into that square. Breadth-first search finds a solution using the fewest moves when all moves have equal cost. Depth-first search can use less working storage but need not find a shortest solution. Remembering visited configurations prevents repeatedly exploring a cycle. The same formulation applies to route finding and automated planning.[ref]
Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig. Chapter 3, problem formulation and search strategies
Symbolic model checking 2026-11-05
Symbolic model checking verifies a Transition system by representing sets of states and transitions as formulas or decision structures rather than enumerating each state separately. Encode a current state by bits and its successor by bits . A formula describes the transition relation. If denotes currently reachable states, the next reachable set isIterating from the initial-state formula reaches a fixed point in a finite system. Intersecting that set with a bad-state formula checks a safety property.
Binary decision diagrams can make these operations compact when the represented Boolean structure is favorable. A system with Boolean state components has up to states, so sharing structure can be decisive. The representation can nevertheless become exponentially large, and variable ordering strongly affects a decision diagram's size. Symbolic representation mitigates state-space explosion; it does not abolish it.
