FPRD LabShare an approach

← Claims

Proper-containment theorem and language corollary

FPRD-T90

Strict real-time transfer is properly contained in PEG

Exact statement

The reversal of the strict real-time multitape Turing-machine languages is a proper subclass of PEG\mathsf{PEG}. Combining this containment with the classical real-time palindrome theorem and its ordinary single-head multitape implementation yields EPAL2={wwR:w∈{0,1}∗}∈PEG\mathsf{EPAL}_2=\{ww^R:w\in\{0,1\}^*\}\in\mathsf{PEG}, so Conjecture 7 of Loff--Moreira--Reis is false.

StatusSource-verified informal proof with mechanized compiler composition; internally audited
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The compiler gives the positive inclusion after reversal. A language from the Loff--Moreira--Reis online lower bound witnesses strictness, while even palindromes provide a concrete consequence.

Hypotheses and scope

  • The strict real-time class is exactly the finite deterministic ordinary single-head multitape model used by FPRD-T89.
  • PEG means ordinary total complete-match parsing expression grammars in the Loff--Moreira--Reis sense.
  • The palindrome corollary uses the cited classical real-time recognition and multihead-to-single-head implementation results.

Proof or evidence

Lean checks the universal machine-to-scaffold compiler, the sufficient scaffold-to-PEG construction, their containment composition, and the implication from an exact strict real-time EPAL recognizer to EPAL membership in PEG. The classical recognizer and the properness witness are source-verified rather than re-mechanized.

Recognition-class consequence →

Verification notes

Independent internal reviews checked the final lower-bound witness, the reversal direction, the embedding of strict real time in Online(O(1)), same-prefix timing, blank initialization, empty-word behavior, fixed-rate speedup, and the distinction between proved theorems and rejected intermediate reconstructions.

Limitations

  • The complete proof chain is mixed-assurance and therefore remains classified as an informal proof rather than wholly machine checked.
  • The positive inclusion reverses languages; omitting that reversal changes the theorem.
  • The theorem does not say that every PEG language has a strict real-time multitape recognizer.

Open work

Obtain external formal-languages review of the classical recognizer interface, ordinary-machine realization, and properness-source composition.

Notes

The proper containment is the primary result; even-palindrome membership is its first major corollary. Strictness follows from Loff--Moreira--Reis Theorem 23. The positive direction uses their Theorem 16; the palindrome corollary uses Slisenko's real-time recognizer and the Leong--Seiferas ordinary single-head implementation and cited speedup. The load-bearing palindrome premise is the simplified paper's final two-sided real-time recognition theorem, not a reconstruction from selected one-directional intermediate propositions. Galil's distinct shorter multitape construction corroborates the result but explicitly reuses Slisenko's chain notion and four string lemmas; Slisenko 1973 is fallback only. The independent properness audit is complete. The standalone candidate was independently refuted at `0110`: its outward-only heads make both tapes write-only, so W26 was not activated and that packet contributes no premise. The theorem package closes as a source-verified informal proof. Lean now checks the universal machine-to-scaffold compiler, the LMR sufficient direction, their containment composition, and the implication from an exact strict real-time multitape EPAL recognizer to EPAL_2 in PEG. The classical recognizer, ordinary-machine realization, speedup, and Theorem 23 properness premise remain source-verified rather than re-mechanized.