Theory Wrap_Prefix_Runs
theory Wrap_Prefix_Runs
imports Wrap_Prefix_Patch
begin
section ‹Runs of the patched wrap›
text ‹The patched wrap's first steps are its encoder's, forced because the
encoder is deterministic; the runs below are the canonical ones, and
‹relpow_forced_split› below says every other run of the wrap or of
its patch agrees with them. None of the arguments assumes the
simulated machine deterministic.›
subsection ‹Forced splitting›
lemma relpow_backward:
assumes backward: "⋀x y. (x, y) ∈ R ⟹ G y ⟹ G x"
and run: "(a, b) ∈ R ^^ n" and good: "G b"
shows "G a"
using run good
proof (induction n arbitrary: b)
case 0
then show ?case by simp
next
case (Suc n)
obtain b' where "(a, b') ∈ R ^^ n" and "(b', b) ∈ R"
using Suc.prems(1) by (rule relpow_Suc_E)
then show ?case using Suc.IH backward Suc.prems(2) by blast
qed
text ‹Against a run that is good at step ‹p›, a run of length ‹n› from
the same configuration either passes through that point, or stops
short of it while still good.›
lemma relpow_forced_split:
assumes unique: "⋀x y z. (x, y) ∈ R ⟹ (x, z) ∈ R ⟹ G x ⟹ y = z"
and backward: "⋀x y. (x, y) ∈ R ⟹ G y ⟹ G x"
and one: "(a, b) ∈ R ^^ p" and good: "G b"
and two: "(a, c) ∈ R ^^ n"
shows "p ≤ n ∧ (b, c) ∈ R ^^ (n - p) ∨ n < p ∧ G c"
proof (cases "p ≤ n")
case True
have "(a, c) ∈ R ^^ (p + (n - p))" using two True by simp
then obtain x where ax: "(a, x) ∈ R ^^ p" and xc: "(x, c) ∈ R ^^ (n - p)"
unfolding relpow_add by blast
have "b = x" by (rule relpow_forced[where R=R and G=G, OF unique backward one ax good])
then show ?thesis using True xc by simp
next
case False
have "(a, b) ∈ R ^^ (n + (p - n))" using one False by simp
then obtain y where ay: "(a, y) ∈ R ^^ n" and yb: "(y, b) ∈ R ^^ (p - n)"
unfolding relpow_add by blast
have gy: "G y" by (rule relpow_backward[where R=R and G=G, OF backward yb good])
have "y = c" by (rule relpow_forced[where R=R and G=G, OF unique backward ay two gy])
then show ?thesis using False gy by simp
qed
lemma wrap_forced_split:
fixes A :: "('q, 'b) ktm"
assumes one: "(a, b) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ p"
and good: "∀q. ktc_state b ≠ W_Run q"
and two: "(a, c) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ n"
shows "p ≤ n ∧ (b, c) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (n - p)
∨ n < p ∧ (∀q. ktc_state c ≠ W_Run q)"
proof -
have d: "delta_ktm (encoding_wrap A pack m S) = wrap_delta A pack m S" by simp
show ?thesis unfolding d
by (rule relpow_forced_split[where R = "ktm_step (wrap_delta A pack m S)"
and G = "λC. ∀q. ktc_state C ≠ W_Run q",
OF wrap_step_unique_non_run wrap_step_back_non_run
one[unfolded d] good two[unfolded d]])
qed
lemma wrap_prefix_forced_split:
fixes A :: "('q, 'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool"
assumes one: "(a, b) ∈ (ktm_step (delta_ktm
(wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ p"
and good: "∀q. snd (ktc_state b) ≠ W_Run q"
and two: "(a, c) ∈ (ktm_step (delta_ktm
(wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ n"
shows "p ≤ n ∧ (b, c) ∈ (ktm_step (delta_ktm
(wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (n - p)
∨ n < p ∧ (∀q. snd (ktc_state c) ≠ W_Run q)"
by (rule relpow_forced_split[where R = "ktm_step (delta_ktm
(wrap_prefix_patch (encoding_wrap A pack m S) table N))"
and G = "λC. ∀q. snd (ktc_state C) ≠ W_Run q",
OF wrap_prefix_step_unique wrap_prefix_step_back_non_run one good two])
subsection ‹The flagged first compression block›
lemma wrap_prefix_first_block:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and j: "j < m" "j ≤ length w"
defines "W ≡ encoding_wrap A pack m S"
and "P ≡ wrap_prefix_patch W table N"
and "C ≡ λj. mid_buf_extending_config_gen (k_ktm A) A pack m w 0 j"
shows "(init_config_ktm P (map Raw w),wrap_flag_config True (C j))
∈ (ktm_step (delta_ktm P)) ^^ Suc j"
and "(init_config_ktm W (map Raw w),C j)
∈ (ktm_step (delta_ktm W)) ^^ Suc j"
proof -
have zero: "C 0 = mid_encoder_config_gen (k_ktm A) A pack m w 0"
by (simp add: C_def mid_buf_extending_config_gen_def mid_encoder_config_gen_def fun_eq_iff split: nat.split)
have old_init: "(init_config_ktm W (map Raw w),C 0)
∈ ktm_step (delta_ktm W)"
using init_to_mid_zero[OF valid positive, where pack=pack and w=w and Σu=S]
by (simp add: W_def zero)
have new_init: "(init_config_ktm P (map Raw w),wrap_flag_config True (C 0))
∈ ktm_step (delta_ktm P)"
proof -
have target: "wrap_prefix_target W table N True
(ktc_state (init_config_ktm W (map Raw w)))
(λk. ktc_tape (init_config_ktm W (map Raw w)) k
(ktc_pos (init_config_ktm W (map Raw w)) k)) (ktc_state (C 0))
= (True,ktc_state (C 0))"
by (auto simp: W_def C_def
mid_buf_extending_config_gen_def wrap_prefix_target_def wrap_first_flag_def)
show ?thesis using wrap_prefix_step[OF old_init target]
by (simp add: P_def)
qed
have prefixes:
"(init_config_ktm P (map Raw w),wrap_flag_config True (C i))
∈ (ktm_step (delta_ktm P)) ^^ Suc i ∧
(init_config_ktm W (map Raw w),C i)
∈ (ktm_step (delta_ktm W)) ^^ Suc i"
if "i < m" "i ≤ length w" for i
using that
proof (induction i)
case 0
show ?case using old_init new_init by simp
next
case (Suc i)
have i: "i < m" "i < length w" using Suc.prems by auto
have old_step: "(C i,C (Suc i)) ∈ ktm_step (delta_ktm W)"
using mid_buf_extend_step[where i=0 and j=i, OF valid positive word Suc.prems(1)]
i by (simp add: C_def W_def)
have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
have nonempty: "w ≠ []" using i(2) by (cases w) auto
have target: "wrap_prefix_target W table N True (ktc_state (C i))
(λk. ktc_tape (C i) k (ktc_pos (C i) k)) (ktc_state (C (Suc i)))
= (True,ktc_state (C (Suc i)))"
using i Suc.prems k nonempty
by (simp add: W_def C_def
mid_buf_extending_config_gen_def wrap_prefix_target_def wrap_first_flag_def)
have new_step: "(wrap_flag_config True (C i),wrap_flag_config True (C (Suc i)))
∈ ktm_step (delta_ktm P)"
using wrap_prefix_step[OF old_step target] by (simp add: P_def)
have ih: "(init_config_ktm P (map Raw w),wrap_flag_config True (C i))
∈ (ktm_step (delta_ktm P)) ^^ Suc i"
"(init_config_ktm W (map Raw w),C i)
∈ (ktm_step (delta_ktm W)) ^^ Suc i"
using Suc.IH[OF i(1)] Suc.prems by auto
show ?case using relpow_Suc_I[OF ih(1) new_step]
relpow_Suc_I[OF ih(2) old_step] by blast
qed
show "(init_config_ktm P (map Raw w),wrap_flag_config True (C j))
∈ (ktm_step (delta_ktm P)) ^^ Suc j"
and "(init_config_ktm W (map Raw w),C j)
∈ (ktm_step (delta_ktm W)) ^^ Suc j"
using prefixes[OF j] by auto
qed
lemma wrap_prefix_short_run:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
defines "W ≡ encoding_wrap A pack m S"
and "P ≡ wrap_prefix_patch W table N"
assumes short: "length w < m" "length w ≤ N"
shows "(init_config_ktm P (map Raw w),
wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)))
∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
and "(wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)),
KConfig (False,if table w then t_ktm W else r_ktm W)
(ktc_tape (post_encoder_config_gen (k_ktm A) A pack m w))
(ktc_pos (post_encoder_config_gen (k_ktm A) A pack m w)))
∈ ktm_step (delta_ktm P)"
proof -
let ?C = "mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)"
let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
let ?q = "if table w then t_ktm W else r_ktm W"
have first: "(init_config_ktm P (map Raw w),wrap_flag_config True ?C)
∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
and m=m and w=w and S=S and j="length w"]
valid positive word short
by (simp add: W_def P_def)
have old_first: "(init_config_ktm W (map Raw w),?C)
∈ (ktm_step (delta_ktm W)) ^^ Suc (length w)"
using wrap_prefix_first_block(2)[where A=A and pack=pack
and m=m and w=w and S=S and j="length w"]
valid positive word short
by (simp add: W_def)
have old_whole: "(init_config_ktm W (map Raw w),?D)
∈ (ktm_step (delta_ktm W)) ^^ (length w+2)"
using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w and Σu=S, OF valid positive word blle k2 pack]
by (simp add: W_def)
have goodC: "∀q. ktc_state ?C ≠ W_Run q"
by (simp add: mid_buf_extending_config_gen_def)
have last: "(?C,?D) ∈ ktm_step (delta_ktm W)"
using wrap_forced_split[OF old_first[unfolded W_def] goodC old_whole[unfolded W_def]]
by (simp add: W_def)
have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
have target: "wrap_prefix_target W table N True (ktc_state ?C)
(λj. ktc_tape ?C j (ktc_pos ?C j)) (ktc_state ?D) = (False,?q)"
using short k
by (simp add: W_def wrap_prefix_target_def
mid_buf_extending_config_gen_def post_encoder_config_gen_def)
let ?final = "KConfig (False,?q) (ktc_tape ?D) (ktc_pos ?D)"
have new_last: "(wrap_flag_config True ?C,?final) ∈ ktm_step (delta_ktm P)"
using wrap_prefix_redirect_step[OF last target] by (simp add: P_def)
show "(init_config_ktm P (map Raw w),wrap_flag_config True ?C)
∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)" by (rule first)
show "(wrap_flag_config True ?C,?final) ∈ ktm_step (delta_ktm P)" by (rule new_last)
qed
lemma wrap_prefix_long_prefix:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
defines "W ≡ encoding_wrap A pack m S"
and "P ≡ wrap_prefix_patch W table N"
assumes long: "N < length w"
shows "(init_config_ktm P (map Raw w),
wrap_flag_config False (post_encoder_config_gen (k_ktm A) A pack m w))
∈ (ktm_step (delta_ktm P)) ^^ (length w+2)"
proof -
let ?C = "λj. mid_buf_extending_config_gen (k_ktm A) A pack m w 0 j"
let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
have old_whole: "(init_config_ktm W (map Raw w),?D)
∈ (ktm_step (delta_ktm W)) ^^ (length w+2)"
using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
and Σu=S, OF valid positive word blle k2 pack]
by (simp add: W_def)
have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
show ?thesis
proof (cases "length w < m")
case True
have first: "(init_config_ktm P (map Raw w),wrap_flag_config True (?C (length w)))
∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
and m=m and w=w and S=S and j="length w"] valid positive word True
by (simp add: W_def P_def)
have old_first: "(init_config_ktm W (map Raw w),?C (length w))
∈ (ktm_step (delta_ktm W)) ^^ Suc (length w)"
using wrap_prefix_first_block(2)[where A=A and pack=pack
and m=m and w=w and S=S and j="length w"] valid positive word True
by (simp add: W_def)
have goodC: "∀q. ktc_state (?C (length w)) ≠ W_Run q"
by (simp add: mid_buf_extending_config_gen_def)
have last: "(?C (length w),?D) ∈ ktm_step (delta_ktm W)"
using wrap_forced_split[OF old_first[unfolded W_def] goodC old_whole[unfolded W_def]]
by (simp add: W_def)
have target: "wrap_prefix_target W table N True (ktc_state (?C (length w)))
(λj. ktc_tape (?C (length w)) j (ktc_pos (?C (length w)) j))
(ktc_state ?D) = (False,ktc_state ?D)"
using long k
by (simp add: W_def wrap_prefix_target_def wrap_first_flag_def
mid_buf_extending_config_gen_def post_encoder_config_gen_def)
have new_last: "(wrap_flag_config True (?C (length w)),wrap_flag_config False ?D)
∈ ktm_step (delta_ktm P)"
using wrap_prefix_step[OF last target] by (simp add: P_def)
show ?thesis using relpow_Suc_I[OF first new_last] by simp
next
case False
have m_le: "m ≤ length w" using False by simp
have index: "m-1 < m" "m-1 ≤ length w" using positive m_le by arith+
let ?B = "mid_encoder_config_gen (k_ktm A) A pack m w 1"
have first: "(init_config_ktm P (map Raw w),wrap_flag_config True (?C (m-1)))
∈ (ktm_step (delta_ktm P)) ^^ m"
using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
and m=m and w=w and S=S and j="m-1"] valid positive word index
by (simp add: W_def P_def)
have old_first: "(init_config_ktm W (map Raw w),?C (m-1))
∈ (ktm_step (delta_ktm W)) ^^ m"
using wrap_prefix_first_block(2)[where A=A and pack=pack
and m=m and w=w and S=S and j="m-1"] valid positive word index
by (simp add: W_def)
have nonempty: "w ≠ []" using positive m_le by (cases w) auto
have block: "pack (take m w) ∈ Sigma_ktm A"
using pack[of 0] nonempty by simp
have close: "(?C (m-1),?B) ∈ ktm_step (delta_ktm W)"
using mid_buf_close_step[where M=A and pack=pack and c=m and w=w
and Σu=S and i=0, OF valid positive word _ _ blle k2] m_le block
by (simp add: W_def)
have target: "wrap_prefix_target W table N True (ktc_state (?C (m-1)))
(λj. ktc_tape (?C (m-1)) j (ktc_pos (?C (m-1)) j))
(ktc_state ?B) = (False,ktc_state ?B)"
using positive m_le k
by (simp add: W_def wrap_prefix_target_def wrap_first_flag_def
mid_buf_extending_config_gen_def mid_encoder_config_gen_def)
have new_close: "(wrap_flag_config True (?C (m-1)),wrap_flag_config False ?B)
∈ ktm_step (delta_ktm P)"
using wrap_prefix_step[OF close target] by (simp add: P_def)
have new_block: "(init_config_ktm P (map Raw w),wrap_flag_config False ?B)
∈ (ktm_step (delta_ktm P)) ^^ Suc m"
by (rule relpow_Suc_I[OF first new_close])
have old_block: "(init_config_ktm W (map Raw w),?B)
∈ (ktm_step (delta_ktm W)) ^^ Suc m"
by (rule relpow_Suc_I[OF old_first close])
have order: "Suc m ≤ length w+2" using m_le by arith
have goodB: "∀q. ktc_state ?B ≠ W_Run q"
by (simp add: mid_encoder_config_gen_def)
have suffix: "(?B,?D) ∈ (ktm_step (delta_ktm W)) ^^ (length w+2-Suc m)"
using wrap_forced_split[OF old_block[unfolded W_def] goodB old_whole[unfolded W_def]]
order by (simp add: W_def)
have lifted: "(wrap_flag_config False ?B,wrap_flag_config False ?D)
∈ (ktm_step (delta_ktm P)) ^^ (length w+2-Suc m)"
using wrap_prefix_false_run[OF suffix] by (simp add: P_def)
have total: "(init_config_ktm P (map Raw w),wrap_flag_config False ?D)
∈ (ktm_step (delta_ktm P)) ^^ (Suc m+(length w+2-Suc m))"
using new_block lifted unfolding relpow_add by blast
show ?thesis using total order by simp
qed
qed
lemma wrap_prefix_short_reaches:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
and short: "length w < m" "length w ≤ N"
shows "reaches_state_in_time_ktm
(wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w)
(False,if table w then t_ktm (encoding_wrap A pack m S)
else r_ktm (encoding_wrap A pack m S)) (length w+2)"
proof -
note run = wrap_prefix_short_run[where A=A and pack=pack and m=m and S=S and w=w
and table=table and N=N, OF valid positive word blle k2 pack short]
show ?thesis
by (rule reaches_state_in_time_ktmI[OF _ relpow_Suc_I[OF run]]) simp_all
qed
subsection ‹Terminal states, transport and language›
text ‹The simulated machine's halting states are sinks of the wrap, and so
of its patch.›
lemma wrap_run_terminal_sink:
assumes valid: "valid_ktm A" and q: "q ∈ {t_ktm A, r_ktm A}"
shows "(W_Run q, a, p, b, d) ∉ wrap_delta A pack m S"
proof
assume member: "(W_Run q, a, p, b, d) ∈ wrap_delta A pack m S"
have run: "(W_Run q, a, p, b, d) ∈ wrap_run_delta A S"
by (rule wrap_delta_W_Run_source_only_run[OF member])
obtain a0 p0 b0 d0 where source: "(q, a0, p0, b0, d0) ∈ delta_ktm A"
using run unfolding wrap_run_delta_def by auto
have "delta_ktm A ⊆
(Q_ktm A - {t_ktm A, r_ktm A}) × (UNIV → Γ_ktm A) ×
Q_ktm A × (UNIV → Γ_ktm A) × (UNIV → UNIV)"
by (rule valid_ktm_delta_set[OF valid])
with source q show False by auto
qed
lemma wrap_prefix_terminal_sink:
fixes A :: "('q,'b) ktm"
assumes valid: "valid_ktm A" and q: "q ∈ {t_ktm A, r_ktm A}"
and state: "snd (ktc_state c) = W_Run q"
shows "(c, y) ∉ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
proof
assume "(c, y) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
then obtain s ts n p' b d where src: "c = KConfig s ts n"
and tuple: "(s, λj. ts j (n j), p', b, d) ∈ wrap_prefix_delta (encoding_wrap A pack m S) table N"
by (cases rule: ktm_step.cases) auto
obtain first q0 p where s: "s = (first, q0)"
and old: "(q0, λj. ts j (n j), p, b, d) ∈ delta_ktm (encoding_wrap A pack m S)"
using tuple unfolding wrap_prefix_delta_def by blast
have "q0 = W_Run q" using state src s by simp
then have "(W_Run q, λj. ts j (n j), p, b, d) ∈ wrap_delta A pack m S"
using old by simp
with wrap_run_terminal_sink[OF valid q] show False by blast
qed
text ‹On a long input the patch runs as the wrap does, so every
simulation-phase state the wrap reaches the patch reaches in the same
time, with the flag clear.›
lemma wrap_prefix_transport:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
and long: "N < length w"
and reach: "reaches_state_in_time_ktm (encoding_wrap A pack m S) (map Raw w) (W_Run q) T"
shows "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) (False, W_Run q) T"
proof -
obtain k fin where k: "k ≤ T"
and run: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), fin) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ k"
and st: "ktc_state fin = W_Run q"
using reach unfolding reaches_state_in_time_ktm_def by blast
let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
have old_whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), ?D)
∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2)"
using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
and Σu=S, OF valid positive word blle k2 pack] by simp
have goodD: "∀q. ktc_state ?D ≠ W_Run q" by (simp add: post_encoder_config_gen_def)
have split: "length w + 2 ≤ k ∧
(?D, fin) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (k - (length w + 2))"
using wrap_forced_split[OF old_whole goodD run] st by auto
have new_prefix: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False ?D)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2)"
by (rule wrap_prefix_long_prefix[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack long])
have lifted: "(wrap_flag_config False ?D, wrap_flag_config False fin)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - (length w + 2))"
using wrap_prefix_false_run split by blast
have "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False fin)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2 + (k - (length w + 2)))"
using new_prefix lifted unfolding relpow_add by blast
moreover have eqk: "length w + 2 + (k - (length w + 2)) = k"
using split[THEN conjunct1] by simp
ultimately have whole: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False fin)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
by (simp only: eqk)
show ?thesis by (rule reaches_state_in_time_ktmI[OF k whole]) (simp add: st)
qed
text ‹On a short input every accepting run is the table's: the forced
prefix ends in the redirected transition, whose target is a sink.›
lemma wrap_prefix_short_accepts:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
and short: "length w < m" "length w ≤ N"
and acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) T"
shows "table w"
proof -
let ?C = "wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w))"
let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
let ?q = "if table w then t_ktm (encoding_wrap A pack m S) else r_ktm (encoding_wrap A pack m S)"
let ?fin = "KConfig (False, ?q) (ktc_tape ?D) (ktc_pos ?D)"
note run = wrap_prefix_short_run[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack short]
obtain k E where accrun: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), E)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
and stE: "ktc_state E = t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N)"
using acc unfolding accepts_in_time_ktm_iff_reaches reaches_state_in_time_ktm_def by blast
have stE': "ktc_state E = (False, W_Run (t_ktm A))" using stE by simp
have goodC: "∀q. snd (ktc_state ?C) ≠ W_Run q"
by (simp add: mid_buf_extending_config_gen_def)
have after: "(?C, E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - Suc (length w))"
using wrap_prefix_forced_split[OF run(1) goodC accrun] stE' by auto
obtain j where j: "k - Suc (length w) = Suc j"
proof (cases "k - Suc (length w)")
case 0
then have "E = ?C" using after by simp
then show ?thesis using stE' by simp
next
case (Suc j)
then show ?thesis by (rule that)
qed
obtain Y where CY: "(?C, Y) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
and YE: "(Y, E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ j"
using relpow_Suc_D2[OF after[unfolded j]] by blast
have Y: "Y = ?fin" by (rule wrap_prefix_step_unique[OF CY run(2) goodC])
have sink: "(?fin, Z) ∉ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))" for Z
proof (cases "table w")
case True
show ?thesis by (rule wrap_prefix_terminal_sink[OF valid, of "t_ktm A"]) (simp_all add: True)
next
case False
show ?thesis by (rule wrap_prefix_terminal_sink[OF valid, of "r_ktm A"]) (simp_all add: False)
qed
have "E = ?fin"
proof (cases j)
case 0
then show ?thesis using YE Y by simp
next
case (Suc i)
then obtain Z where "(?fin, Z) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
using relpow_Suc_D2[OF YE[unfolded Y Suc]] by blast
with sink show ?thesis by blast
qed
then have "?q = W_Run (t_ktm A)" using stE' by simp
moreover have "r_ktm A ≠ t_ktm A" using valid by (cases A) auto
ultimately show "table w" by (cases "table w") simp_all
qed
text ‹On a long input every accepting run of the patch passes through the
wrap's post-encoder configuration with the flag clear, and from there it
is a run of the wrap.›
lemma wrap_prefix_long_accepts:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
and table :: "'a list ⇒ bool" and N :: nat
assumes valid: "valid_ktm A" and positive: "0 < m"
and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
and k2: "2 ≤ k_ktm A"
and pack: "⋀i. i*m < length w ⟹
pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
and long: "N < length w"
and acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) T"
shows "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
proof -
let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
have new_prefix: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False ?D)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2)"
by (rule wrap_prefix_long_prefix[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack long])
have old_whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), ?D)
∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2)"
using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
and Σu=S, OF valid positive word blle k2 pack] by simp
obtain k E where k: "k ≤ T"
and accrun: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
and stE: "ktc_state E = t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N)"
using acc unfolding accepts_in_time_ktm_iff_reaches reaches_state_in_time_ktm_def by blast
have stE': "ktc_state E = (False, W_Run (t_ktm A))" using stE by simp
have goodD: "∀q. snd (ktc_state (wrap_flag_config False ?D)) ≠ W_Run q"
by (simp add: post_encoder_config_gen_def)
have split: "length w + 2 ≤ k ∧ (wrap_flag_config False ?D, E)
∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - (length w + 2))"
using wrap_prefix_forced_split[OF new_prefix goodD accrun] stE' by auto
obtain E' where E: "E = wrap_flag_config False E'"
and tail: "(?D, E') ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (k - (length w + 2))"
using wrap_prefix_false_run_proj split by blast
have "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), E')
∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2 + (k - (length w + 2)))"
using old_whole tail unfolding relpow_add by blast
moreover have eqk: "length w + 2 + (k - (length w + 2)) = k"
using split[THEN conjunct1] by simp
ultimately have whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), E')
∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ k"
by (simp only: eqk)
have "ktc_state E' = t_ktm (encoding_wrap A pack m S)" using stE' E by simp
then show ?thesis unfolding accepts_in_time_ktm_iff_reaches
by (rule reaches_state_in_time_ktmI[OF k whole])
qed
text ‹With the wrap's own language as the table, the patch accepts the
same user-facing language as the wrap. No determinism is assumed.›
theorem wrap_prefix_language:
fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b" and N :: nat
assumes valid: "valid_ktm A" and positive: "0 < m"
and blle: "bl_ktm A ≠ le_ktm A" and k2: "2 ≤ k_ktm A"
and width: "N < m"
and enc: "⋀w. set w ⊆ S ⟹ set (wrap_enc pack m w) ⊆ Sigma_ktm A"
shows "Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) = Lang_user_wrap (encoding_wrap A pack m S)"
proof (rule set_eqI)
fix w
have legal: "set (map Raw w) ⊆ Raw ` S ⟷ set w ⊆ S" by auto
have tP: "t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) = (False, W_Run (t_ktm A))" by simp
show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) ⟷ w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
proof (cases "set w ⊆ S")
case False
then have badW: "¬ set (map Raw w) ⊆ Sigma_ktm (encoding_wrap A pack m S)"
and badP: "¬ set (map Raw w) ⊆ Sigma_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)" by auto
have "map Raw w ∉ Lang_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)" and "map Raw w ∉ Lang_ktm (encoding_wrap A pack m S)"
using badW badP unfolding Lang_ktm_iff by blast+
then show ?thesis by (simp add: Lang_user_wrap_def)
next
case word: True
have packw: "pack (take m (drop (i*m) w)) ∈ Sigma_ktm A" if "i*m < length w" for i
using enc[OF word] pack_take_in_set_wrap_enc[OF positive that, where pack=pack] by blast
show ?thesis
proof (cases "length w ≤ N")
case short: True
have shortm: "length w < m" using short width by simp
show ?thesis
proof
assume "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
then obtain T where acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
show "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
by (rule wrap_prefix_short_accepts[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
OF valid positive word blle k2 packw shortm short acc])
next
assume member: "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
have "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w)
(False, W_Run (t_ktm A)) (length w + 2)"
using wrap_prefix_short_reaches[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
OF valid positive word blle k2 packw shortm short] member by simp
then have "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) (length w + 2)"
unfolding accepts_in_time_ktm_iff_reaches tP .
then show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
qed
next
case long: False
have longN: "N < length w" using long by simp
show ?thesis
proof
assume "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
then obtain T where acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
have "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
by (rule wrap_prefix_long_accepts[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
OF valid positive word blle k2 packw longN acc])
then show "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
next
assume "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
then obtain T where acc: "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
have reach: "reaches_state_in_time_ktm (encoding_wrap A pack m S) (map Raw w) (W_Run (t_ktm A)) T"
using acc unfolding accepts_in_time_ktm_iff_reaches by simp
have "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) (False, W_Run (t_ktm A)) T"
by (rule wrap_prefix_transport[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
OF valid positive word blle k2 packw longN reach])
then have "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
unfolding accepts_in_time_ktm_iff_reaches tP .
then show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
qed
qed
qed
qed
end