Proof of `Decidable equivalence of regular functions`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 87 of the paper of lax-157538, Transducers
Description
Equivalence of total coded two-way transducers is decidable (Theorem C.1.4), of the source.
Proof strategy
The source bounds the length of a shortest distinguishing input by an explicit arithmetic expression in the two codes (, from the crossing-sequence decomposition of a two-way run and Schützenberger's rank criterion, ) and compares the two coded transducers on all inputs up to that bound over the letters of the codes and one fresh letter (, ). The concept's codes are the same lists as the source's; the bridge identifies the coded transducers (), their relations and the totality promise, and unfolds identically.
Attribution
Theorem C.1.4 of Transducers, Part C; formalised by Aristotle (Harmonic).