The CGT SDK — reference

Call(name: 'str', args: 'Tuple[Any, ...]' = ()) -> None class

One occurrence of a move in an expression.

Cost(trace: 'bool' = False, word_bits: 'int' = 64) class

Mutable operation counter, optionally recording a trace.

CostModel(name: 'str' = 'unit', word_bits: 'int' = 64, weights: 'Tuple[Tuple[str, float], ...]' = ()) -> None class

Weights per category and the machine word size (bits).

DFA(states: 'Set[Hashable]', start: 'Hashable', accept: 'Set[Hashable]', delta: 'Dict[Tuple[Hashable, str], Hashable]', alphabet: 'FrozenSet[str]' = frozenset()) -> None class

Deterministic automaton with a *partial* transition function.

ExecutionResult(expression: 'str', syntax: 'SyntaxReport', defined: 'Optional[bool]' = None, undefined_at: 'Optional[int]' = None, reason: 'Optional[str]' = None, denoted: 'List[Any]' = <factory>, values: 'List[Any]' = <factory>, cost: 'Cost' = <factory>, adequate: 'Optional[bool]' = None) -> None class

Outcome of :meth:`OperationalGrammar.execute`, one field per layer.

Inadmissible class

Raised when a call is semantically undefined in the current state
(e.g. an index out of range, popping an empty stack, moving to a missing
child).  This is the *semantic* layer saying ⟦w⟧(x) = ∅.

Move(name: 'str', params: 'Tuple[str, ...]' = (), doc: 'str' = '', mutates: 'bool' = False) -> None class

One symbol of a move signature.

OperationalGrammar(structure: 'Structure', admissible: 'Optional[str | DFA]' = None) class

G = (Σ, 𝔄, ⟦·⟧, ℒ): moves, structure, semantics, admissibility.

Report(implementation: 'str', build: 'Dict[str, int]' = <factory>, query: 'Dict[str, int]' = <factory>, queries: 'int' = 0, space_words: 'Optional[int]' = None, wall_seconds: 'Optional[float]' = None, correct: 'Optional[bool]' = None) -> None class

A cost profile row (CGT-DEF-005) for one implementation on one workload.

Structure() class

Base class for a computational structure with an operational grammar.

Subclasses provide:

* ``SIGNATURE``: the move signature (tuple of :class:`Move`);
* ``abstract()``: the abstract value the representation stands for;
* ``denote(state, call)``: pure reference semantics, returning
  ``(new_state, value)`` or raising :class:`Inadmissible`;
* ``apply(call, cost)``: execute on the representation, counting cost.

break_even(build_a: 'float', per_query_a: 'float', per_query_b: 'float') -> 'float' function

Queries after which scheme A (build cost, cheaper queries) beats B
(no build).  CGT-PROP-005 with a single epoch.  inf if A never wins.

compile_regex(src: 'str', alphabet: 'Optional[Iterable[str]]' = None, minimal: 'bool' = True) -> 'DFA' function

Compile a symbol-level regular expression to a DFA.

parse_expression(src: 'str') -> 'List[Call]' function

Parse ``"get(2); set(0, 9) L R"`` into calls.  Arguments are Python
literals (ints, floats, strings, tuples).  Raises SyntaxError.

SyntaxReport(ok: 'bool', calls: 'List[Call]' = <factory>, error: 'Optional[str]' = None) -> None class

SyntaxReport(ok: 'bool', calls: 'List[Call]' = <factory>, error: 'Optional[str]' = None)

null_cost() -> 'Cost' function

A counter for callers that do not care about cost.

ArrayStructure(values=(), capacity: 'Optional[int]' = None) class

Dynamic array: contiguous block of ``capacity`` cells holding ``n``
elements.  ``append`` doubles the capacity when full (amortised O(1)).

Layout: ``capacity`` element words + 3 header words (base, n, capacity).

Move signature: get(i) set(i, x) len append(x) pop insert(i, x) delete(i)

AutomatonStructure(dfa: 'DFA') class

A DFA viewed as a structure: elements are states, moves are letters,
the cursor is the current state.  ``accepting()`` queries acceptance.

BSTStructure(keys=(), balance: 'str' = 'none') class

Binary search tree over distinct comparable keys, optionally AVL
balanced (Adelson-Velsky & Landis 1962).  Abstract value: the sorted
tuple of keys.  Cost: one ``compare`` per key comparison, one ``pointer``
per edge followed, ``write`` per pointer/height update.

Move signature: insert(k) contains(k) delete(k) min

BinaryTreeStructure(labels: 'Dict[str, Any]', representation: 'str' = 'pointer') class

Base class for a computational structure with an operational grammar.

Subclasses provide:

* ``SIGNATURE``: the move signature (tuple of :class:`Move`);
* ``abstract()``: the abstract value the representation stands for;
* ``denote(state, call)``: pure reference semantics, returning
  ``(new_state, value)`` or raising :class:`Inadmissible`;
* ``apply(call, cost)``: execute on the representation, counting cost.

Move signature: L R U root goto(addr) read here

DequeStructure(values=(), capacity: 'int' = 4) class

Circular-buffer double-ended queue.

Move signature: push_back(x) push_front(x) pop_back pop_front len

GraphStructure(n: 'int', edges: 'Iterable[Tuple[int, str, int]]' = ()) class

Base class for a computational structure with an operational grammar.

Subclasses provide:

* ``SIGNATURE``: the move signature (tuple of :class:`Move`);
* ``abstract()``: the abstract value the representation stands for;
* ``denote(state, call)``: pure reference semantics, returning
  ``(new_state, value)`` or raising :class:`Inadmissible`;
* ``apply(call, cost)``: execute on the representation, counting cost.

HashTableStructure(items=(), capacity: 'int' = 8, hash_fn=<function stable_hash at 0x7f42b24114e0>) class

Open addressing with linear probing; resize ×2 when load > 1/2.

Layout: 2 words per slot (key, value) + 3 header words.  ``hash_fn`` may
be replaced (e.g. by a constant function) to study adversarial inputs.

Move signature: put(k, v) get(k) contains(k) delete(k) len

HeapStructure(values=()) class

Binary min-heap in an array (Williams 1964).  The parent of slot i is
(i-1)//2 and its children are 2i+1, 2i+2: the heap numeration of
CGT-THM-003, shifted to start at 0.  Abstract value: the sorted multiset.

Move signature: push(x) pop_min peek len

LinkedListStructure(values=()) class

Singly linked list with a head pointer and a stored length.

Layout: 2 words per node (value, next) + 2 header words (head, n).
The same signature as :class:`ArrayStructure` minus ``append``/``pop``
(replaced by ``push_front``/``pop_front``), so the two can be compared
on identical workloads.

Move signature: get(i) set(i, x) len push_front(x) pop_front insert(i, x) delete(i)

QueueStructure(values=(), capacity: 'int' = 4) class

Circular-buffer FIFO queue (doubling when full).  Layout: capacity
words + 3 header words (head, n, capacity).

Move signature: enqueue(x) dequeue front len

StackStructure(values=()) class

Array-backed stack.  The set of move words that are *defined* when
started on an empty stack is { w : every prefix has #push ≥ #pop } --
a context-free, non-regular language (book Chapter 3).

Move signature: push(x) pop top empty

TrieStructure(words=()) class

Character trie over strings.  Each step of a lookup is one move
labelled by the next character: the trie *is* the minimal-prefix DFA of
its key set (without suffix sharing; cf. DAWGs).

Move signature: insert(w) contains(w) count_prefix(p)

stable_hash(key: 'Any') -> 'int' function

Deterministic 64-bit hash: FNV-1a over a canonical byte encoding.

EulerLCA(parent: 'Sequence[int]', cost: 'Optional[Cost]' = None) class

Euler tour + sparse table: O(n log n) build, O(1) query (the simple
variant of Bender & Farach-Colton 2000).

Fenwick(values: 'Sequence[float]', cost: 'Optional[Cost]' = None) class

Prefix sums with point updates, both O(log n); 1-based internally.

NaiveLCA(parent: 'Sequence[int]', cost: 'Optional[Cost]' = None) class

Walk up with parent pointers: O(n) build (depths), O(h) query.

PageRankResult(scores: 'List[float]', iterations: 'int', residuals: 'List[float]' = <factory>, converged: 'bool' = True, _bound: 'float' = nan) -> None class

PageRankResult(scores: 'List[float]', iterations: 'int', residuals: 'List[float]' = <factory>, converged: 'bool' = True, _bound: 'float' = nan)

SegmentTree(values: 'Sequence[float]', op: 'Callable' = <function SegmentTree.<lambda> at 0x7f42b25f7ec0>, identity: 'float' = 0, cost: 'Optional[Cost]' = None) class

Iterative segment tree for an associative operation (default: sum)
with point assignment.  Leaves at n..2n-1: again a heap numeration.

SparseTable(values: 'Sequence', key: 'Callable' = <function SparseTable.<lambda> at 0x7f42b2410180>, cost: 'Optional[Cost]' = None) class

Idempotent range queries (min) in O(1) after O(n log n) build.

UnionFind(n: 'int', cost: 'Optional[Cost]' = None) class

Disjoint sets with union by rank and path compression (Tarjan 1975):
amortised O(α(n)) per operation.

bellman_ford(wadj, s: 'int', cost: 'Optional[Cost]' = None) -> 'Optional[List[float]]' function

Bellman (1958) / Ford (1956).  O(nm).  Returns None if a negative
cycle is reachable from s.

bfs(adj: 'Sequence[Sequence[int]]', s: 'int', cost: 'Optional[Cost]' = None) -> 'List[float]' function

Hop distances from s (inf if unreachable).  Θ(n + m).

bfs_path(adj, s: 'int', t: 'int', cost: 'Optional[Cost]' = None) -> 'Optional[List[int]]' function

A shortest (fewest-edges) path s→t, or None.  Witness retrieval.

binary_search(a: 'Sequence[Any]', x: 'Any', cost: 'Optional[Cost]' = None) -> 'int' function

Leftmost index i with a[i] == x in a sorted sequence, or -1.
Invariant: a[lo-1] < x <= a[hi] (with sentinels).  ⌈log₂(n+1)⌉ + 1
three-way compares at most.

brute_force_count(nvars: 'int', clauses) -> 'int' function

constrained_pagerank(n: 'int', edges: 'Sequence[Tuple[int, str, int]]', dfa: 'DFA', alpha: 'float' = 0.85, tol: 'float' = 1e-10, max_iter: 'int' = 10000, cost: 'Optional[Cost]' = None) -> 'Tuple[List[float], PageRankResult, int]' function

Grammar-constrained random surfer (CGT proposal; CGT-PROP-010).

The surfer carries the state q of a DFA over edge labels.  From (u, q)
it may follow only edges (u, a, w) with δ(q, a) defined, uniformly among
those, moving to (w, δ(q, a)); if none exists, (u, q) is dangling.  Every
teleport (and every dangling jump) lands in (w, q₀) with w uniform.
The vertex score is the marginal Σ_q π(w, q).

Returns (vertex scores, product-chain result, number of product states).
With the 1-state universal DFA this is exactly ordinary PageRank on the
unlabelled graph (tested).  Only product states reachable from V × {q₀}
are materialised; their number is ≤ |Q|·n (cf. THM-001).

counting_sort(a: 'Sequence[int]', key_range: 'int', cost: 'Optional[Cost]' = None) -> 'List[int]' function

Stable sort of integers in [0, key_range) with NO comparisons: each key
is used as an *address* into a count array (arithmetic addressing).
Θ(n + key_range) time and space -- linear when key_range = O(n), useless
when the key range is large and sparse (the density condition again).

dfs_order(adj, cost: 'Optional[Cost]' = None) -> 'Tuple[List[int], List[int]]' function

Iterative DFS over all vertices: (discovery order, finish order).

dijkstra(wadj, s: 'int', cost: 'Optional[Cost]' = None) -> 'List[float]' function

Dijkstra (1959) with a binary heap; non-negative weights required.
O((n + m) log n).

edit_distance(x: 'Sequence[Any]', y: 'Sequence[Any]', cost: 'Optional[Cost]' = None) -> 'int' function

Levenshtein distance (unit insert/delete/substitute); Θ(|x||y|).

floyd_warshall(n: 'int', wedges, cost: 'Optional[Cost]' = None) -> 'List[List[float]]' function

All-pairs shortest paths, Θ(n³): the closed-semiring instance of the
path grammar P → E | P P evaluated by dynamic programming over the
allowed intermediate vertices.

heap_lca(a: 'int', b: 'int', cost: 'Optional[Cost]' = None, word_bits: 'int' = 64) -> 'int' function

LCA of heap numerals a, b ≥ 1 (CGT-THM-003): align depths, XOR,
shift.  Charged ⌈bits/w⌉ per arithmetic operation.

heapsort(a: 'Sequence[Any]', cost: 'Optional[Cost]' = None) -> 'List[Any]' function

In-place heapsort (Williams 1964 / Floyd's bottom-up heap
construction); O(n log n) compares, not stable.

insertion_sort(a: 'Sequence[Any]', cost: 'Optional[Cost]' = None) -> 'List[Any]' function

Stable; Θ(n²) compares worst case, n-1 on sorted input.

kmp_find_all(text: 'str', pat: 'str', cost: 'Optional[Cost]' = None) -> 'List[int]' function

Knuth–Morris–Pratt (1977): at most 2n compares after O(m)
preprocessing.  The failure function is the transition structure of the
pattern's string-matching automaton.

knapsack_01(weights: 'Sequence[int]', values: 'Sequence[int]', capacity: 'int', cost: 'Optional[Cost]' = None) -> 'int' function

Maximum value of a subset with total weight ≤ capacity; Θ(nW) cells
(pseudo-polynomial: W is a number, not an input length).

kruskal(n: 'int', edges: 'Sequence[Tuple[float, int, int]]', cost: 'Optional[Cost]' = None) function

Kruskal (1956): minimum spanning forest of an undirected graph given
as (w, u, v) triples.  Returns (total weight, chosen edges).

lcs_length(x: 'Sequence[Any]', y: 'Sequence[Any]', cost: 'Optional[Cost]' = None) -> 'int' function

Longest common subsequence length; Θ(|x||y|) table cells.

linear_search(a: 'Sequence[Any]', x: 'Any', cost: 'Optional[Cost]' = None) -> 'int' function

Index of the first occurrence of x, or -1.  Θ(n) compares worst case.

merge_sort(a: 'Sequence[Any]', cost: 'Optional[Cost]' = None) -> 'List[Any]' function

Stable; at most n⌈log₂ n⌉ compares.

naive_find_all(text: 'str', pat: 'str', cost: 'Optional[Cost]' = None) -> 'List[int]' function

All occurrences by direct comparison; Θ(nm) compares worst case.

pagerank_exact(adj: 'Sequence[Sequence[int]]', alpha: 'float' = 0.85, v: 'Optional[Sequence[float]]' = None) -> 'List[float]' function

Direct solve of (I − αM) x = (1 − α) v by Gaussian elimination with
partial pivoting.  Θ(n³); a validation oracle for small n only.

pagerank_gauss_seidel(adj: 'Sequence[Sequence[int]]', alpha: 'float' = 0.85, v: 'Optional[Sequence[float]]' = None, tol: 'float' = 1e-10, max_iter: 'int' = 10000, cost: 'Optional[Cost]' = None) -> 'PageRankResult' function

Gauss–Seidel sweeps on the linear system (I − αM) x = (1 − α) v,
M = Pᵀ + v·1_Dᵀ.  Uses updated values within a sweep; typically fewer
sweeps than power iteration.  Stops on ‖x_k − x_{k−1}‖₁ ≤ tol (no
contraction-based guarantee is claimed for this stopping rule).

pagerank_power(adj: 'Sequence[Sequence[int]]', alpha: 'float' = 0.85, v: 'Optional[Sequence[float]]' = None, tol: 'float' = 1e-10, max_iter: 'int' = 10000, x0: 'Optional[Sequence[float]]' = None, cost: 'Optional[Cost]' = None) -> 'PageRankResult' function

Power iteration with dangling mass redistributed by v.  Stops when the
a-posteriori bound α/(1−α)·‖x_k − x_{k−1}‖₁ ≤ tol.  Cost: one ``edge``
per edge per iteration plus ``arith`` per vertex.

path_grammar_closure(adj, shape: 'str' = 'linear', cost: 'Optional[Cost]' = None) -> 'List[Set[int]]' function

Semi-naive bottom-up evaluation of a path grammar for P⁺.

``linear``:   P → E | E P     — rule attempts = m + Σ_{(w,v)∈P⁺} indeg(w)  (THM-004a)
``doubling``: P → E | P P     — O(n·|P⁺|) attempts, O(log ℓ) parallel depth

prim(n: 'int', edges: 'Sequence[Tuple[float, int, int]]', cost: 'Optional[Cost]' = None) function

Prim (1957) / Jarník: minimum spanning forest with a binary heap.

product_reach(g: "'GraphStructure'", x: 'int', dfa: 'DFA', cost: 'Optional[Cost]' = None, return_explored: 'bool' = False) function

{ y : some walk x ⇝ y has its label word in ℒ(dfa) } by BFS on the
product A × Q.  Explores ≤ |Q|·n states; THM-001(b) shows this bound is
attained, THM-001(c) that it can also prune almost everything.

quicksort(a: 'Sequence[Any]', cost: 'Optional[Cost]' = None, seed: 'int' = 0) -> 'List[Any]' function

Randomised quicksort with 3-way partition (Hoare 1962 idea; seeded
pivot choice for reproducibility).  Expected O(n log n) compares;
worst case Θ(n²).

satisfies(assign: 'Sequence[bool]', clauses) -> 'bool' function

solution_automaton(nvars: 'int', clauses, cap: 'int' = 2000000, cost: 'Optional[Cost]' = None) function

Layer widths, number of models (None if the cap was hit) and total nodes.

tarjan_scc(adj, cost: 'Optional[Cost]' = None) -> 'Tuple[List[int], int]' function

Tarjan (1972).  Returns (comp, k): comp[v] in 0..k-1, numbered in
*reverse topological* order of the condensation (comp 0 is a sink).

topological_sort(adj, cost: 'Optional[Cost]' = None) -> 'Optional[List[int]]' function

Kahn (1962).  Returns an order, or None if the graph has a cycle.

transitive_closure(adj, cost: 'Optional[Cost]' = None, word_bits: 'int' = 64) -> 'List[int]' function

Reachability rows as Python-int bitsets (bit t of row s ⇔ s ⇝ t,
reflexive).  SCC condensation + reverse-topological OR; each OR of
n-bit rows is charged ⌈n/word_bits⌉ word operations.

two_sat(nvars: 'int', clauses: 'Sequence[Tuple[int, int]]', cost: 'Optional[Cost]' = None) function

Return a satisfying assignment (list of bools, index i-1 for x_i) or None.

AffineMod(a: 'int', b: 'int', N: 'int') -> None class

AffineMod(a: 'int', b: 'int', N: 'int')

BoxTranslation(dims: 'Tuple[int, ...]', t: 'Tuple[int, ...]', lo: 'Tuple[int, ...]', hi: 'Tuple[int, ...]') -> None class

Translation by t (a d-vector) on the box Π[0, dims_i), defined at x iff
every prefix of the compiled word stays inside: x_i + lo_i ≥ 0 and
x_i + hi_i < dims_i, where lo/hi are the min/max prefix displacements.

HeapWord(n: 'int', k: 'int', j: 'int', c: 'int', lo: 'int', hi: 'int') -> None class

Compiled form of a word over {L, R, U} on the heap-shaped binary tree
whose nodes are exactly the numerals 1..n (CGT-THM-006).

Semantics of the original word at x: follow the moves one by one; the
word is defined iff every visited numeral lies in [1, n].  Compiled form:
f(x) = ((x >> k) << j) | c, defined iff lo ≤ x ≤ hi.

XorMask(c: 'int') -> None class

XorMask(c: 'int')

compile_word(moves: 'dict', word: 'Iterable[str]', identity, cost: 'Optional[Cost]' = None) function

debruijn_moves(k: 'int', m: 'int') function

Vertices = words of length m over [k] read as base-k numerals; move
``s{a}`` shifts in letter a: x ↦ (k x + a) mod k^m.

grid_moves(dims: 'Sequence[int]') function

heap_walk(word: 'Iterable[str]', x: 'int', n: 'int', cost: 'Optional[Cost]' = None) -> 'Optional[int]' function

Reference semantics: step-by-step evaluation, Θ(|word|).

hypercube_moves(d: 'int') function

row_major(x: 'Sequence[int]', dims: 'Sequence[int]') -> 'int' function

The dense numeration of a grid point: density exactly 1.

ExperimentRecord(experiment: 'str', hypothesis: 'str', seed: 'int', parameters: 'Dict[str, Any]', results: 'List[Dict[str, Any]]' = <factory>, falsification: 'str' = '', environment: 'Dict[str, str]' = <factory>) -> None class

Serialisable record: what ran, on what, with which seed, and results.

compare_functions(impls: 'Dict[str, Callable[..., Any]]', inputs: 'Sequence[Tuple]', oracle: 'Callable[..., Any]', builds: 'Optional[Dict[str, Callable]]' = None) -> 'List[Report]' function

Compare algorithm implementations ``f(*args, cost=...)`` on the same
inputs against an independent oracle.  ``builds`` optionally maps a name
to a preprocessing function ``b(cost) -> f`` whose cost is reported
separately as build cost.

compare_structures(classes: 'Sequence[type]', values: 'Iterable[Any]', expressions: 'Sequence[str]', baseline: 'Optional[type]' = None) -> 'List[Report]' function

Run the same expressions on a fresh instance of each structure class.
Correctness: each implementation's values must equal the reference
semantics (adequacy) *and* the baseline implementation's values.

format_table(rows: 'Sequence[Report]') -> 'str' function

random_digraph(n: 'int', avg_deg: 'float', seed: 'int' = 0, dag: 'bool' = False) -> 'List[List[int]]' function

random_index_workload(n: 'int', queries: 'int', seed: 'int' = 0, op: 'str' = 'get') -> 'List[str]' function

random_labelled_graph(n: 'int', avg_deg: 'float', labels: 'Sequence[str]', seed: 'int' = 0) function

random_parent_array(n: 'int', seed: 'int' = 0, shape: 'str' = 'random') -> 'List[int]' function

Rooted tree on 0..n-1 with root 0.  shape: random | path | star | complete.

random_weighted(adj: 'Sequence[Sequence[int]]', seed: 'int' = 0, lo: 'int' = 1, hi: 'int' = 20) function

Client(url: str = '') class

Tiny client.  ``Client()`` calls the contract in-process; pass a URL to
talk to a server instead.  Both return the same JSON.

capabilities() -> 'Dict[str, Any]' function

handle(req: 'Any') -> 'Dict[str, Any]' function

Evaluate one request; never raises.