Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `Decidable equivalence of regular functions`

groundedproofs/Lax916827Proofs/Results.lean · lax-916827

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.

Read the Lean proof on GitHub

In the paper

Description

Equivalence of total coded two-way transducers is decidable (Theorem C.1.4), Transducers.regularequivalencedecidableTransducers.regular_equivalence_decidable of the source.

Proof strategy

The source bounds the length of a shortest distinguishing input by an explicit arithmetic expression in the two codes (Transducers.RegDec.codeBoundTransducers.RegDec.codeBound, from the crossing-sequence decomposition of a two-way run and Schützenberger's rank criterion, PartC/Reg.leanPartC/Reg*.lean) and compares the two coded transducers on all inputs up to that bound over the letters of the codes and one fresh letter (PartC/RegEqDec.leanPartC/RegEqDec.lean, PartC/TwoWaySimPrimrec.leanPartC/TwoWaySimPrimrec.lean). The concept's codes are the same lists as the source's; the bridge identifies the coded transducers (twoWayCodeAuttoSrctwoWayCodeAut_toSrc), their relations and the totality promise, and DecidableUnderPromiseDecidableUnderPromise unfolds identically.

Attribution

Theorem C.1.4 of Transducers, Part C; formalised by Aristotle (Harmonic).