[Imprint][Data Privacy Statement][E-Mail]

Back to main index. View the specification. View theorem base summary, View theorem base listing, the used properties by spec, the dependency list, the symbol table,

Theorem base for Specification IOtrace

This is a listing of all goals defined over the current specification. Axioms are marked yellow, proved theorems green and unproved theorems blue. Click on individual names to get more information on the proof.

Name: Sequent: Type:
trace ⊦ trace(IOAut(startf, stepf))(α) ↔ (∃ σ, β. α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β)) An Axiom
tracestar ⊦ trace*(IOAut(startf, stepf))(α) ↔ trace(IOAut(startf, stepf))(α) ∧ finp(α) An Axiom
traceomega ⊦ traceω(IOAut(startf, stepf))(α) ↔ trace(IOAut(startf, stepf))(α) ∧ ¬ finp(α) An Axiom
execomega ⊦ execω(IOAut(startf, stepf))(σ, β) ↔ exec(IOAut(startf, stepf))(σ, β) ∧ ¬ finp(β) An Axiom
execstar ⊦ exec*(IOAut(startf, stepf))(σ, β) ↔ exec(IOAut(startf, stepf))(σ, β) ∧ finp(β) An Axiom
exec ⊦ exec(IOAut(startf, stepf))(σ, β) ↔ frag(IOAut(startf, stepf))(σ, β) ∧ startf(σ[0]) An Axiom
fragomega ⊦ fragω(IOAut(startf, stepf))(σ, β) ↔ frag(IOAut(startf, stepf))(σ, β) ∧ ¬ finp(β) An Axiom
fragstar ⊦ frag*(IOAut(startf, stepf))(σ, β) ↔ frag(IOAut(startf, stepf))(σ, β) ∧ finp(β) An Axiom
frag ⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1])) An Axiom
move ⊦ move(IOAut(startf, stepf))(s1, β, s2) ↔ (∃ α, sl. frag*(IOAut(startf, stepf))(⌜sl⌝ , α) ∧ s1 = sl[0] ∧ s2 = sl.last ∧ α ^ = β) An Axiom
emptymove-splitfirstmove(IOAut(startf, stepf))(s, [], s2), s ≠ s2 ⊦ ∃ s1. stepf(s, τ, s1) ∧ move(IOAut(startf, stepf))(s1, [], s2) A User Theorem
exec-fin1 ⊦ ¬ exec(IOAut(startf, stepf))(⌜sf⌝ , ⌜al⌝ ) A User Theorem
exec-fin2 ⊦ ¬ exec(IOAut(startf, stepf))(⌜sl⌝ , ⌜af⌝ ) A User Theorem
exec-step⌜n⌝ < # α ⊦ ¬ stepf(σ[n], α[n], σ[n + 1]) → (exec(IOAut(startf, stepf))(σ, α) ↔ false) A User Theorem
exec-step-finn + 1 < # sl ⊦ ¬ stepf(sl[n], α[n], sl[n + 1]) → (exec(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
exec-step-fin-2⌜n⌝ < # α ⊦ ¬ stepf(sl[n], α[n], sl[n + 1]) → (exec(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
exec-step-fin-zeroα ≠ [] ⊦ ¬ stepf(sl[0], α[0], sl[1]) → (exec(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
exec-step-inf ⊦ ¬ stepf(sf(n), α[n], sf(n + 1)) → (exec(IOAut(startf, stepf))(⌜sf⌝ , α) ↔ false) A User Theorem
exec-step-inf-zero ⊦ ¬ stepf(sf(0), α[0], sf(1)) → (exec(IOAut(startf, stepf))(⌜sf⌝ , α) ↔ false) A User Theorem
exec-step-zeroα ≠ [] ⊦ ¬ stepf(σ[0], α[0], σ[1]) → (exec(IOAut(startf, stepf))(σ, α) ↔ false) A User Theorem
frag-fin1 ⊦ ¬ frag(IOAut(startf, stepf))(⌜sf⌝ , ⌜al⌝ ) A User Theorem
frag-fin2 ⊦ ¬ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜af⌝ ) A User Theorem
frag-from ⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ⌜n⌝ < # α → frag(IOAut(startf, stepf))(σ from n, α from n) A User Theorem
frag-from-fin ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) ∧ n < # al → (frag(IOAut(startf, stepf))(⌜sl from n⌝ , ⌜al from n⌝ ) ↔ true) A User Theorem
frag-move ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) → move(IOAut(startf, stepf))(hd(sl), ⌜al⌝ ^, sl.last) A User Theorem
frag-one ⊦ frag(IOAut(startf, stepf))(⌜s '⌝ , []) A User Theorem
frag-rec ⊦ frag(IOAut(startf, stepf))(⌜s '⌝ + σ, ⌜a '⌝ + α) ↔ stepf(s, a, hd(σ)) ∧ frag(IOAut(startf, stepf))(σ, α) A User Theorem
frag-rec-end ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ + ⌜s '⌝ , α + ⌜a '⌝ ) ↔ stepf(sl.last, a, s) ∧ frag(IOAut(startf, stepf))(⌜sl⌝ , α) A User Theorem
frag-size ⊦ frag(IOAut(startf, stepf))(σ, α) → (# σ < # α ↔ false) A User Theorem
frag-size-2 ⊦ frag(IOAut(startf, stepf))(σ, α) → (# α < # σ ↔ finp(α)) A User Theorem
frag-split⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ⌜n⌝ < # α → frag*(IOAut(startf, stepf))(σ to n + 1, α to n) ∧ frag(IOAut(startf, stepf))(σ from n, α from n) A User Theorem
frag-step⌜n⌝ < # α ⊦ ¬ stepf(σ[n], α[n], σ[n + 1]) → (frag(IOAut(startf, stepf))(σ, α) ↔ false) A User Theorem
frag-step-finn + 1 < # sl ⊦ ¬ stepf(sl[n], α[n], sl[n + 1]) → (frag(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
frag-step-fin-2⌜n⌝ < # α ⊦ ¬ stepf(sl[n], α[n], sl[n + 1]) → (frag(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
frag-step-fin-zeroα ≠ [] ⊦ ¬ stepf(sl[0], α[0], sl[1]) → (frag(IOAut(startf, stepf))(⌜sl⌝ , α) ↔ false) A User Theorem
frag-step-inf ⊦ ¬ stepf(sf(n), α[n], sf(n + 1)) → (frag(IOAut(startf, stepf))(⌜sf⌝ , α) ↔ false) A User Theorem
frag-step-inf-inf ⊦ ¬ stepf(sf(n), af(n), sf(n + 1)) → (frag(IOAut(startf, stepf))(⌜sf⌝ , ⌜af⌝ ) ↔ false) A User Theorem
frag-step-inf-zero ⊦ ¬ stepf(sf(0), α[0], sf(1)) → (frag(IOAut(startf, stepf))(⌜sf⌝ , α) ↔ false) A User Theorem
frag-step-zeroα ≠ [] ⊦ ¬ stepf(σ[0], α[0], σ[1]) → (frag(IOAut(startf, stepf))(σ, α) ↔ false) A User Theorem
frag-to ⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ¬ # α < ⌜n⌝ → frag*(IOAut(startf, stepf))(σ to n + 1, α to n) A User Theorem
frag-to-1 ⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ¬ # α < ⌜n⌝ → (frag(IOAut(startf, stepf))(σ to n + 1, α to n) ↔ true) A User Theorem
frag-to-fin ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) ∧ ¬ # al < n → (frag(IOAut(startf, stepf))(⌜sl to n + 1⌝ , ⌜al to n⌝ ) ↔ true) A User Theorem
frag-transfrag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ), frag(IOAut(startf, stepf))(⌜sl0⌝ , ⌜al0⌝ ), sl0[0] = sl.last ⊦ frag(IOAut(startf, stepf))(⌜sl.butlast⌝ + ⌜sl0⌝ , ⌜al⌝ + ⌜al0⌝ ) A User Theorem
frag-two ⊦ frag(IOAut(startf, stepf))(⌜s ' + s0 '⌝ , ⌜a '⌝ ) ↔ stepf(s, a, s0) A User Theorem
fragfin-size ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) → (# sl = # al + 1 ↔ true) A User Theorem
fragfin-size-le ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) → (# sl ≤ # al ↔ false) A User Theorem
fragfin-size-ls ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) → (# sl < # al ↔ false) A User Theorem
fragfin-size-notls ⊦ frag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) → (# al < # sl ↔ true) A User Theorem
infappend-movesstartf(sf(0)), ∀ n. move(IOAut(startf, stepf))(sf(n), ⌜af(n) '⌝ ^, sf(n + 1)) ⊦ trace(IOAut(startf, stepf))(⌜af⌝ ^) A User Theorem
move-cutmove(IOAut(startf, stepf))(s, α1 + α2, s2) ⊦ ∃ s1. move(IOAut(startf, stepf))(s, α1, s1) A User Theorem
move-cut-2¬ # α < ⌜n⌝ , move(IOAut(startf, stepf))(s, α, s2) ⊦ ∃ s1. move(IOAut(startf, stepf))(s, α to n, s1) A User Theorem
move-empty ⊦ move(IOAut(startf, stepf))(s, [], s) A User Theorem
move-one ⊦ stepf(s, a, s0) ∧ IOAut?(IOAut(startf, stepf)) → move(IOAut(startf, stepf))(s, ⌜a '⌝ ^, s0) A User Theorem
move-one-ext ⊦ stepf(s, a, s0) ∧ a ≠ τ ∧ IOAut?(IOAut(startf, stepf)) → move(IOAut(startf, stepf))(s, ⌜a '⌝ , s0) A User Theorem
move-split¬ # α < ⌜n⌝ , move(IOAut(startf, stepf))(s, α, s2) ⊦ ∃ s1. move(IOAut(startf, stepf))(s, α to n, s1) ∧ move(IOAut(startf, stepf))(s1, α from n, s2) A User Theorem
move-trans ⊦ move(IOAut(startf, stepf))(s, α1, s1) ∧ move(IOAut(startf, stepf))(s1, α2, s2) → move(IOAut(startf, stepf))(s, α1 + α2, s2) A User Theorem
moveone-splitstepa ≠ τ, move(IOAut(startf, stepf))(s, ⌜a '⌝ , s2) ⊦ ∃ s0, s1. move(IOAut(startf, stepf))(s, [], s0) ∧ stepf(s0, a, s1) ∧ move(IOAut(startf, stepf))(s1, [], s2) A User Theorem
not-exec-empty ⊦ ¬ exec(IOAut(startf, stepf))([], α) A User Theorem
not-frag-empty ⊦ ¬ frag(IOAut(startf, stepf))([], α) A User Theorem
notfragomega-fin ⊦ ¬ fragω(IOAut(startf, stepf))(σ, ⌜al⌝ ) A User Theorem
notfragstar-inf ⊦ ¬ frag*(IOAut(startf, stepf))(σ, ⌜af⌝ ) A User Theorem
preserve-INVfrag(IOAut(startf, stepf))(σ, α), startf(σ[0]), ∀ s. startf(s) → iNV(s), ∀ s, a, s0. iNV(s) ∧ stepf(s, a, s0) → iNV(s0) ⊦ ∀ n. ⌜n⌝ < # σ → iNV(σ[n]) A User Theorem
shortest-fragfrag(IOAut(startf, stepf))(⌜sl⌝ , ⌜al⌝ ) ⊦ ∃ sl0, al0. hd(sl0) = hd(sl) ∧ sl0.last = sl.last ∧ frag(IOAut(startf, stepf))(⌜sl0⌝ , ⌜al0⌝ ) ∧ (∀ sl1, al1. hd(sl1) = hd(sl) ∧ sl1.last = sl.last ∧ frag(IOAut(startf, stepf))(⌜sl1⌝ , ⌜al1⌝ ) → # sl0 ≤ # sl1) A User Theorem
trace-append ⊦ trace(IOAut(startf, stepf))(⌜al⌝ + α) → (trace(IOAut(startf, stepf))(⌜al⌝ ) ↔ true) A User Theorem