Automata & Formal Grammar Models

← Back to Domain-Specific Families

Abstractions about formal models of computation and language generation, including automaton models such as the deterministic finite automaton and Turing machine, grammar and production systems like regular grammars and post canonical systems, and related structured proof or retrieval formalisms such as ludics and postings lists.

9 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Deterministic Finite Automaton — Recognize a regular language by starting in one of finitely many states, taking exactly one transition for each input symbol, and accepting according to the unique terminal state.
• Firing-Squad Synchronization Problem — Find one finite local rule that, from a single endpoint trigger, makes every cell in an arbitrarily long finite cellular-automaton line enter a firing state simultaneously for the first time.
• Ludics — Reconstruct logical propositions and proofs from address-based designs, polarized actions, and successful interaction, defining meaning extensionally through orthogonality rather than presupposed formulas.
• Pattern Language (Formal Languages) — The formal language generated from one constants-and-variables pattern by consistently replacing each variable with a nonempty terminal string while preserving every constant.
• Post Canonical System — A finite string-production formalism that derives words from finite axioms by matching whole-word antecedent patterns and reassembling their matched variables in consequents.
• Postings List — A postings list is the term-conditioned occurrence sequence in an inverted index, storing ordered document identifiers and optional frequencies, positions, offsets, impacts, or payloads so query operators can traverse only matching corpus regions.
• Profinite Word — An element of the all-finite-monoid completion of finite words over a finite alphabet, determined by its compatible images in every finite quotient.
• Regular Grammar — A regular grammar is a formal grammar whose productions keep at most one nonterminal consistently at one edge of the right-hand side, so derivation carries only finite-state memory and generates exactly a regular language under the declared right- or left-linear convention.
• Turing Machine — The canonical formal model of computation — finite control plus an unbounded read-write tape governed by a finite transition function — whose one unbounded resource is the tape, and against which computability and complexity are given exact, provable meaning.