One language, several presentations

The number 24 can be written as $24$, as $4\cdot3\cdot2$, or as$2^3\cdot3$. The number has not changed, but each presentation makes different operations and regularities easy to see.

A formal language behaves similarly. The same set of words can be presented by a grammar, a machine, the left residuals of its prefixes, a stack discipline, or a persistent scaffold. FPRD keeps those presentations distinct long enough to ask four concrete questions: what information survives a prefix, what must cross the next cut, which updates are local, and which apparent costs belong only to the chosen representation?

language  →  grammar  ·  machine  ·  residual system  ·  persistent scaffold

Equivalence is therefore only the beginning. A useful transfer says what state is preserved, how it is updated, and where the translation stops working.

Research note · extension of Kim–Park

Residual information and the cost of access

How many continuation behaviours a prefix permits does not determine how cheaply they can be maintained or retrieved. Inside one explicit unambiguous context-free language, the construction gives easy and hard families with matching residual counts at every update cut and query prefix. The equality persists after fixing any initial update segment, including the probability multiset under uniform completions.

A direct scaffolding simulation connects the hard family to Ko’s Multiphase Inner Product lower bound. That external theorem supplies the access exclusion; the rank identities are proved directly. This note follows the late-query strategy and adapts the parity rules of Kim and Park’s explicit witness. Novelty of the extensions has not been established.

Read the research note →

Replay lower bound · FPRD-T151

One queried cell can still require linear cut memory

For the language that reads the middle bit of a completed binary word, each final answer has a one-cell replay certificate. But after a length-$2r$ prefix, odd zero paddings can select each of $r$independently variable old cells. The resulting response table has$2^r$ distinct rows.

Current open problem · canonical target observation

L-trivial membership: target residuals isolate the live boundary

Automata Exchange Problem 22.19 asks whether transformation membership for minimal L-trivial DFAs is in NP or PSPACE-hard. Here L-trivial means that no two distinct monoid elements generate the same principal left ideal. Passing to the opposite monoid exchanges left and right ideals, but its canonical partially ordered action may have one state per monoid element.

For a supplied target $f$, the canonical observer records only$P_f(x)=\{z:zx=f\}$. If$d_f$ distinct profiles occur, the reversed target fibre has a minimal $d_f$-state poDFA, so an accepted path gives a target word of length at most$d_f-1$. This sharpens the earlier conditional use ofthe general quadratic poDFA transformation bound because membership needs one accepting path rather than preservation of a whole observer action.

The external problem remains open. The live sufficient-bound question is now exact: must $d_f$ be polynomial in the supplied DFA degree under L-triviality? A superpolynomial observer family would refute this route, while a genuinely long-word family would be needed to rule out polynomial word certificates themselves.

Worked case · model transfer

From moving tapes to persistent structure

A strict real-time multitape Turing machine receives one input symbol, makes one global transition, and performs no computation after the input ends. Its work tapes look mutable: a head moves across a row of cells and overwrites symbols. The useful change of presentation is to cut each tape at its head. The scanned symbol stays in finite control, while the cells to the left and right become two stacks—a zipper.

The source tape and its scaffold history are different objects, but the two-stack decoding reconstructs every tape position after every prefix. The full mechanized scaffold-to-PEG theorem, FPRD-T110, then turns this operational simulation into a reverse-language statement:

$$\operatorname{rev}(\mathsf{RT\text{-}MTTM})\subsetneq\mathsf{PEG}.$$

This proper containment is FPRD-T90. It is a strong example of the area’s method, not a proposed summary of the whole area: mutable tapes expose motion, stacks expose the cut, scaffolds expose persistence, and the PEG theorem changes the direction in which the language is read.

Worked case · two proof routes

Two views of even palindromes

Let$\mathsf{EPAL}_2=\{ww^R:w\in\{0,1\}^*\}$. The Lab has an established transfer proof and a second, direct presentation proof. Keeping both is informative because they expose different mechanisms while retaining different evidence boundaries.

The direct route does more than provide a shorter dependency chain. It asks which immutable evidence a comparison really needs and makes that evidence the state. This is the FPRD lens in practice: hold the language fixed, change its presentation, and see which invariant becomes local.

Worked case · semantic state

When an implementation state becomes canonical

A generalized Dyck language matches typed opening and closing symbols. Its familiar recognizer keeps a stack of unmatched opening types. That stack might appear to be merely one convenient implementation. The residual calculation shows otherwise.

Here the operational memory and the semantic memory coincide: two prefixes are equivalent precisely when they leave the same live stack. A canonical closing word separates different stacks. The stack is not just how one parser happens to work; it is the language’s exact future behavior in this presentation.

Worked case · sewing finite views

Finite fits are not yet one model

Projecting away hidden pushdown actions leaves a frontier: for every visible prefix, the relation of control states and stacks that might still be live. One can often fit this frontier over each finite horizon. Those separate fits do not automatically produce one stationary recognizer that works at every length.

The theorem is deliberately conditional. It turns local obligations into a global transfer, but it does not assert that every projected pushdown system has such a bounded stationary presentation. That unresolved sewing step is exactly where representation becomes a mathematical constraint rather than a change of notation.

Worked case · coordinates and their failure

A small frontier still needs stable addresses

Suppose each visible control carries at most one live stack after every prefix. The control itself can name that stack. A fixed allocator keeps one slot per control and may choose any derivation reaching a target control, because all such derivations must produce the same stack.

Finite causal refinements extend this idea by remembering hidden actions. But no fixed action suffix works universally: one regular unary example has two histories with the same retained suffix and different stacks for every fixed depth.

Worked case · syntax becomes dynamics

Regular-expression star hides an orbit closure

Left quotient by union and concatenation follows direct constructor equations. Star is different. For languages$K,L$, the quotient$(K^*)^{-1}L$ is the least fixed point of

$$X\longmapsto L\cup K^{-1}X.$$

A finite derivative graph turns this unbounded language orbit into finite reachability. That is a presentation change with an exact receipt: residual states remember where repeated quotienting can land. The change is sufficient. A proposed carrier-free discipline excludes this auxiliary graph, but it is not yet a formal compiler class: its admissible recursion schemes and auxiliary encodings remain to be specified before a general existence question can be stated.

This is the FPRD distinction in a small classical setting: the same quotient language can be presented as syntax, an infinite iteration, or finite residual dynamics. Brzozowski, Antimirov, Thompson, and Glushkov automata agree on the published finite audit. The unresolved task is to formalize what counts as eliminating residual memory before asking for a theorem about every constructor-only compiler.

Focused program

Shuffle and Boolean-Product Automata

This program studies how asynchronous and policy-controlled language composition changes prefix quotients, state refinement, and automaton complexity.

Program overview and current research directions →

Broda, Maia, Moreira, and Reis prove in The Prefix Automaton (2021)that, for ordinary regular expressions and for synchronized intersection, the prefix automaton is obtained from the position or location automaton by a left-invariant quotient. Shuffle changes the frontier: either component may move while the other stays fixed, so one location can retain independent recurrence on different letters.

For two nonempty fixed words repeated under ordinary asynchronous shuffle, the prefix automaton is a state quotient exactly when both words are powers of one common letter. Even then no left-invariant quotient exists: the initial shuffle fork forces two boundary locations into one prefix state, but their predecessor profile cannot reproduce that state's three-way fan-in. The exceptional one-letter-by-one-letter case fails separately because its interior state lacks the initial predecessor carried by the boundary states. Thus no nonempty starred-word shuffle has a left quotient.

Synchronization changes that boundary. Using the strong, arbitrary, and weak operators defined by Broda, Machiavelo, Moreira, and Reis, the unary cycle family separates three outcomes: strong synchronization gives a left quotient for all cycle lengths; arbitrary synchronization gives an ordinary quotient only when one cycle has length one and a left quotient only at$(1,1)$; weak synchronization gives an ordinary quotient for every pair but no left quotient.

Read the complete ordinary- and left-quotient classification →

Broda, Machiavelo, Moreira, and Reis's arbitrary-arity Boolean-product frameworkseparates two questions. First, componentwise left quotients in the sense of A Mesh of Automataalways transfer through a memoryless support policy: quotienting the components before forming the product gives the same automaton as quotienting the product afterward. Second, the natural prefix automaton of the combined expression need not be that product. It is the component-prefix product split by possible last events. The two constructions agree for every component expression exactly when each active letter has one participant set and the sets for distinct letters overlap pairwise. Beyond that zero-overhead boundary, a compatibility graph on event signatures gives the exact worst-case number of natural states lying over one product state. Computing that policy-only number is NP-complete by reduction from three-dimensional matching, already for one three-participant support per letter. Globally, the exact overhead is the collision excess of the signature target sets. For pairwise-disjoint one-support policies—including pure shuffle—this gives a closed finite-size formula: the clique coefficient is asymptotically sharp, and the finite bound is strict when there are at least two active blocks and the product has a noninitial state.

The overlapping-support search now has an exact Knuth bridge. Knuth's color-controlled exact cover enumerates compatible signature families without building the canonical product. A depth-one graph specialization makes product states exactly graph matchings, with overhead$\sum_M(|M|-1)_+$. An isolated-edge identity reduces Valiant's classical all-matchings count to this overhead, proving #P-completeness under polynomial-time Turing reductions even though Dancing Links supplies a sparse reversible enumerator.

For uniform one-support policies, the zero-overhead condition is exactly independence in a Kneser graph. For$n<2r$, every support family is intersecting. From $n\ge2r$, Erdős–Ko–Rado gives the overall ceiling; for$r\ge2$ and$n>2r$, Hilton–Milner gives the sharp empty-core ceiling and equality structures. At$n=2r$, the non-star gap disappears through complementary pairs. Above the EKR ceiling, a spectral calculation forces an explicit number of disjoint-support witnesses, and a diversity receipt can activate already at the Hilton–Milner scale. The depth-one one-shot overhead dominates both kinds of obstruction count.

Kupavskii's diversity parameter also controls exact search. After choosing a maximum-degree participant, every compatible family is an exceptional matching with at most one support from the remaining star. The sharper formulation permits any pairwise-intersecting core. Within this factorization, the smallest exception count is the vertex-cover number of the support-disjointness graph and can be arbitrarily smaller than diversity. This yields a fixed-parameter target factorization when a cover is supplied, and the depth-one model collapses the chosen core to a conflict-mask quotient evaluated by the classical subset-zeta transform. Exponential XCC output remains possible, but that does not imply an exponential lower bound for evaluating the final overhead.

Repeated support policies have an exact Shannon dictionary. Cartesian support tensors induce strong graph powers, so Shannon capacity is the asymptotic support-packing rate of the overlap graph. This statement alone does not make tensor letters reachable in a prefix expression. The separate pentagon calibration now does: an optional-once five-cycle expression has 16 natural-prefix states, while a relabelled synchronized square reaches only six states and exposes all five nonrectangular pairs $(i,2i)$. A reversible two-block lowering is equally small, but every classical language slice still factors through an ordinary strong-power code. The unresolved $C_7$ capacity therefore remains a support-policy boundary, not a solved expression problem.

The word-level pentagon calibration separates three constructions that the policy dictionary alone does not. The classical block language$\{00,12,24,31,43\}^*$ realizes the twist as length-two paths. Its natural prefix automaton has eleven states; the compact reversible DFA has six only after quotienting. An independent audit checks all 488,281 words of lengths zero through eight; 781 are accepted. Earlier Boolean-carrier counts are no longer reported because their precise source model and verifier were not recovered. Expression reachability is not rectangle-bound, but unrestricted hard-coded block expressions do not strengthen Shannon-capacity methods.

The seven-cycle base code now has a path compiler that does not store its 367 vectors. Polak and Schrijver's cyclic arithmetic construction and conflict filter produce 327 words; the remaining 40-word extension is a forced 37-word core plus three binary choices. Among the eight resulting maximum extensions and all coordinate orders, the published choice is the unique code whose best order gives a 128-state minimal automaton for the finite word language. Gao's complete private-pair and$O/H/V$ interface verifies on that generated code. The full product tree closes under ten typed languages: a 204-node syntax DAG denotes Gao's 200-dimensional code, and exact symbolic derivatives give a deterministic compiler with 192,771 reachable canonical syntax states without enumerating its more than$4\times10^{102}$ words. This is a resource-preserving presentation of a known code. In a direct two-block calibration, 780 canonical syntax states collapse to 766 distinct residual languages, so the large compiler count is not a minimality result. Nor does it improve$\Theta(C_7)$.

Read the event-signature, compatibility, and complexity theorems →

Where the area is moving

Current work follows the same question at several scales: direct persistent recognition with scaffolding automata and PEGs; derivatives, quotients, and Dyck residuals; finite-state and pushdown resource bounds; and exact learning of rational sequences. The common object is not a preferred machine. It is the information a recognition task forces a presentation to preserve.

Read the canonical future-row, one-way communication, and exact memory theorem →

Read the exact Dyck Hankel ranks and finite future-quotient theorem →

Working answer to the driving question. Different models recognize the same languages when the information needed after every prefix can be translated into a bounded, stationary, locally updated representation with exact readout. The open work is to find such translations—or representation-independent obstructions to them—without mistaking a failed encoding for a language lower bound.