FPRD LabShare an approach

← Claims

Computational finding · reproducible finite audit

FPRD-RE-C01

Three automata formulations agree on the finite audit

Exact statement

On 405 selected binary regular-expression pairs and all 31 suffixes of length at most four, three saved automata formulations agree in all 12,55512{,}555 membership comparisons. The Antimirov-versus-Thompson audit removes the first checker's normalization and derivative code, while a review audit replaces the epsilon-NFA oracle with an epsilon-free Glushkov position automaton. The first audit also detects four injected errors.

StatusReproduced by three saved checks; zero ordinary mismatches, identical semantic transcripts, four named negative controls detected, and 65 hostile star cases confirmed
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The original source report described a finite check but its program and certificate were unavailable. This replacement audit publishes both and does not claim to reproduce the original expression corpus.

Definitions

  • The construction oracle evaluates the quotienting expression as a relation on the normalized derivative carrier of the target expression.
  • The comparison oracle explores the synchronized derivative product and tests whether some reachable prefix state accepts the quotienting expression while the target state accepts the supplied suffix.

Hypotheses and scope

  • The alphabet is {a,b}\{a,b\}.
  • The finite domain contains 27 quotienting expressions, 15 target expressions, and all suffixes of length at most four.

Proof or evidence

The first saved checker reports 12,555 comparisons and zero ordinary mismatches while detecting reversed concatenation, one-step star truncation, reversed letter edges, and loss of the distinguished start state. A second checker independently parses the corpus, uses Antimirov partial derivatives for construction and Thompson epsilon-NFAs for its oracle, and reproduces the exact semantic transcript. The review checker uses an epsilon-free Glushkov position-automaton oracle, reproduces the same transcript, and confirms the unbounded-unfolding witness for k=0 through 64.

Finite audit and downloadable evidence →

Verification notes

The saved checks use Brzozowski derivatives, Antimirov partial derivatives, Thompson epsilon-NFAs, and Glushkov position automata in distinct roles. The fixed expression strings, alphabet, and case ordering remain shared by the original pair; the review checker additionally shares its parser with its two sides. All certificates were reproduced before publication.

Limitations

  • Finite evidence does not replace the structural proof for arbitrary regular expressions.
  • The replacement audit deliberately matches the earlier comparison count but does not claim the same test corpus.
  • The four mutation controls are targeted and do not establish general fault-detection completeness.
  • The audits share the fixed expression corpus and case ordering, and the review audit shares one parser between its two automata constructions.

Open work

Use the exact unbounded star family as the next adversary rather than continuing to enlarge this bounded corpus.