Theorems

Real-time transfer

Let $L$ be recognized by a finite deterministic strict real-time multitape Turing machine with a fixed positive number of ordinary single-head work tapes. The machine receives one input symbol and makes one global transition per step, has no input-length advice, and performs no post-input computation. Then $$L^R\in\mathsf{PEG}.$$…

$\mathsf{EPAL}_2\in\mathsf{PEG}$ . Hence Conjecture 7 of Loff–Moreira–Reis is false.

Loff–Moreira–Reis

For every language $K$ , $$K\in\mathsf{PEG} \quad\Longleftrightarrow\quad K^R\text{ is decided by a scaffolding automaton}.$$

Fresh initial state

Every finite scaffolding automaton $A$ has an equivalent finite scaffolding automaton $A^\star$ whose initial state occurs only before the first input symbol. The construction preserves acceptance of the empty word and every nonempty word without inserting an input step.

Persistent-stack update

Suppose the old scaffold is strictly backward and satisfies $\mathsf{CleanEmpty}$ . After appending the node specified by the table, the decoded stack at $v^+$ is exactly the result of the selected stack operation. The new scaffold is strictly backward and again satisfies $\mathsf{CleanEmpty}$ .

Parallel persistent stacks

Every deterministic letter-synchronous finite-control machine with a fixed positive number $s$ of stacks, performing at most one push, keep, or pop per stack and per input symbol, is simulated exactly by a degree- $s$ , distance-two scaffolding automaton.

Tape zipper

Every strict real-time $m$ -tape machine is simulated letter-for-letter by a finite-control machine with $2m$ stacks, performing at most one push, keep, or pop on each stack per input symbol.

Strict machine-to-scaffold simulation

Let $M$ be a strict real-time $m$ -tape machine, $m\geq 1$ . There is a scaffolding automaton $A_M$ of degree $2m$ and distance two such that $$L(A_M)=L(M).$$ After every input prefix, the two persistent stacks associated with each tape, together with its scanned symbol in finite control, reconstruct the s…

If $L$ is recognized by a strict real-time multitape machine, then $$L^R\in\mathsf{PEG}.$$ Equivalently, $$\mathsf{rev}(\mathsf{RT\text{-}MTTM})\subseteq\mathsf{PEG}.$$

Strict real time is online constant time

Every language recognized by a strict real-time multitape machine belongs to $\mathsf{Online}(O(1))$ in the sense of Loff–Moreira–Reis Definition 22.

Proper class containment

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

Classical palindrome interface (classical, imported

). There are finite $m,Q,T$ and a total strict real-time $m$ -tape machine $P$ such that, for every $x\in\{0,1\}^*$ , the state reached after exactly $|x|$ transitions is accepting if and only if $x=x^R$ . The statement includes $x=\varepsilon$ : the initial state is accepting.

Even-palindrome identity

For every binary word $x$ , $$x\in\{ww^R:w\in\{0,1\}^*\} \quad\Longleftrightarrow\quad x=x^R\ \text{ and }\ |x|\text{ is even}.$$ The equivalence includes $x=\varepsilon$ .

Reversal invariance

$$(\mathsf{EPAL}_2)^R=\mathsf{EPAL}_2.$$

Parity product

Suppose a strict real-time machine $P$ reports after every prefix $x$ , including the empty prefix, whether $x=x^R$ . Then a strict real-time machine $P_{\mathrm{even}}$ recognizes exactly $\mathsf{EPAL}_2$ .

The even-length binary palindrome language has a parsing expression grammar: $$\boxed{\mathsf{EPAL}_2=\{ww^R:w\in\{0,1\}^*\}\in\mathsf{PEG}.}$$

Conjecture 7 of Loff, Moreira, and Reis [4] is false.