Admissibility Languages and the Product Construction

8.1 From expression to automaton

An admissibility language is written as a regular expression over move symbols, such as (a b)* (a | ε) or (L | R)* U. The SDK compiles it by the classical three-stage pipeline:

1. Thompson’s construction turns the expression into a nondeterministic automaton with $\varepsilon$-moves, with $\Oh(r)$ states for an expression of length $r$.
2. The subset construction turns it into a deterministic automaton whose states are sets of NFA states; in the worst case this is exponential in $r$.
3. Moore’s partition refinement merges states with the same future, giving the minimal DFA — unique up to renaming (Myhill–Nerode).

The SDK’s tests check the size $8$ for $k = 3$ and check acceptance of every word up to length six against Python’s own regular-expression engine for a set of expressions:

from cgtsdk import compile_regex

for rx in ["a*", "(a b)* (a | ε)", "(L | R)* U", "(a | b)* a (a | b) (a | b)", "(a | b)* a (a | b) (a | b) (a | b) (a | b)"]:
    d = compile_regex(rx)
    print(f"{rx:44s} minimal DFA states = {d.size:3d}   accepts 'a b a': {d.accepts('a b a'.split())}")

a*                                           minimal DFA states =   1   accepts 'a b a': False
(a b)* (a | ε)                               minimal DFA states =   2   accepts 'a b a': True
(L | R)* U                                   minimal DFA states =   2   accepts 'a b a': False
(a | b)* a (a | b) (a | b)                   minimal DFA states =   8   accepts 'a b a': True
(a | b)* a (a | b) (a | b) (a | b) (a | b)   minimal DFA states =  32   accepts 'a b a': False

(The automata are partial: a missing transition means the word can no longer be accepted, so no “dead” state is counted.) The size $|Q|$ of the minimal DFA is the grammar parameter that governs everything below.

8.2 Searching under a constraint

Let $G = (\Sigma, \Str, \sem{\cdot}, \Lang)$ with $\Lang$ given by a DFA $D = (Q, \Sigma, \delta, q_0, F)$ with partial $\delta$. The constrained resolution problem is: given $x$, compute $\sem{\Lang}(x)$, the set of elements reachable from $x$ by some admissible word. For a labelled graph this is the regular path query of Chapter 6.

The answer is found by searching the product $A \times Q$: there is a product edge $(y, q) \to (z, \delta(q, a))$ for each move $(y, z) \in \sem{a}$ with $\delta(q, a)$ defined. Then $y \in \sem{\Lang}(x)$ iff some $(y, q)$ with $q \in F$ is reachable from $(x, q_0)$.

Part 1 is textbook material; parts 2 and 3 are elementary and quite possibly folklore, but together they state something that is rarely made explicit: a grammatical constraint is not a speedup. It changes the search space, in either direction, by up to the size of the automaton. Whether it helps depends jointly on the language and on the structure — exactly the claim of hypothesis H-005, which the experiments supported (CGT-H-005).

from cgtsdk import Cost, compile_regex
from cgtsdk.algorithms import product_reach
from cgtsdk.structures import GraphStructure

n = 101
cycle = GraphStructure(n, [(i, "a", (i + 1) % n) for i in range(n)])
for k in (1, 2, 5, 10):
    rx = " ".join(["a"] * k)                     # words of length divisible by k: (a^k)*
    reach, explored = product_reach(cycle, 0, compile_regex(f"({rx})*"), return_explored=True)
    print(f"k={k:2d}: product states explored = {explored:4d} = n*k = {n*k:4d};  |answer| = {len(reach)}")

k= 1: product states explored =  101 = n*k =  101;  |answer| = 101
k= 2: product states explored =  202 = n*k =  202;  |answer| = 101
k= 5: product states explored =  505 = n*k =  505;  |answer| = 101
k=10: product states explored = 1010 = n*k = 1010;  |answer| = 101

On random labelled graphs (CGT-EXP-003) the measured ratio of explored product states to unconstrained states ranged from $0.003$ (language $a^*$ on a sparse graph) to exactly $5.000$ (walk length divisible by $5$): both extremes of the theorem occur in practice, not only on constructed inputs.

8.3 Two incorrect shortcuts

Two tempting alternatives to the product construction fail.

Search, then filter. Plain reachability forgets which label words lead to a vertex, so no filtering of its answer can recover $\sem{\Lang}(x)$. On the random graphs of the experiment, unconstrained search misreported up to about 15,600 of 20,000 vertices for restrictive languages (CGT-OBS-007). The constraint must be carried during the search.

Enumerate walks, then check the word. This is correct if walks up to length $|Q| \cdot n$ are enumerated — any longer accepted walk revisits a product state and can be shortened — but the number of walks grows exponentially. On a 12-vertex graph the experiment’s walk enumeration hit its cap of two million walks while the product had at most $55$ states. The product construction is, in effect, the sharing mechanism applied to walks: all walks reaching the same (vertex, state) pair are represented once.

8.4 Context-free admissibility

When $\Lang$ is context-free — balanced parentheses for matched calls and returns, the Dyck language of Chapter 3 — the product is no longer a finite graph, and constrained reachability becomes CFL-reachability, the formulation behind interprocedural program analysis [Reps 1998; Yannakakis 1990]. It is solved by a dynamic program over pairs of vertices and nonterminals in time cubic in $n$ (with factors depending on the grammar) [Barrett et al. 2000]. Whether the factor-$|Q|$ phenomenon of Theorem 8.2 has a precise context-free analogue — how the size of the grammar enters, and whether the bound is attained — is open (CGT-OPEN-008).

Report an erratum or an unclear passage in this chapter