Theory Wrap_Band_Speedup
theory Wrap_Band_Speedup
imports Wrap_Convention Wrap_Speedup_Arithmetic
begin
section ‹First-block speedup above a linear band›
text ‹The machine here is the wrap with its first-block language table. The
table decides short inputs within the convention's floor; long inputs follow
the raw wrap at the same cost. The table is a finite restriction of the
source language, so the machine is shown to exist rather than computed from
the source.
The timing conclusion gives a bounded accepting run for each word in the
language, and says nothing about rejecting runs. On a short word the machine
stops with the table's verdict, so a nondeterministic source that both
accepts and rejects that word along different runs keeps only its accepting
verdict. On long inputs every simulated run is carried over, so a statement
about the time to reject needs its own argument about how the source's runs
end.›
abbreviation wrap_speedup ::
"nat ⇒ ('q, 'a) ktm ⇒
(('q × 'a ae_stage, 'a, nat ⇒ 'a) wrap_state,
('a, nat ⇒ 'a) wrap_alphabet) ktm" where
"wrap_speedup m M ≡ encoding_wrap
(alphabet_enlarge m M) (ae_pack m (bl_ktm M)) (m) (Sigma_ktm M)"
definition wrap_speedup_bound :: "nat ⇒ nat ⇒ nat ⇒ nat" where
"wrap_speedup_bound m n T = n + 3 * ((n + m - 1) div m) +
8 * ((T + m - 1) div m) + 9"
abbreviation wrap_prefix_speedup ::
"nat ⇒ ('q,'a) ktm ⇒ nat ⇒
(bool × (('q × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm" where
"wrap_prefix_speedup m M N ≡
wrap_prefix_patch (wrap_speedup m M) (λw. w ∈ Lang_ktm M) N"
definition wrap_prefix_speedup_bound where
"wrap_prefix_speedup_bound N m n T = (if n ≤ N then n+2 else wrap_speedup_bound m n T)"
lemma wrap_prefix_speedup_contract:
fixes M :: "('s,'a) ktm"
and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm"
assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
and width: "N < m"
defines "P ≡ wrap_prefix_speedup m M N"
shows "valid_ktm P"
and "Lang_ktm P = map Raw ` Lang_ktm M"
and "det_ktm M ⟹ det_ktm P"
proof -
have m_pos: "0 < m" using width by linarith
let ?m = "m"
let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
let ?W = "encoding_wrap ?A ?pack ?m (Sigma_ktm M)"
have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
have positive: "0 < ?m" by (rule m_pos)
have blleA: "bl_ktm ?A ≠ le_ktm ?A"
using LE_block_neq_bl_block[OF m_pos blle]
by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
note F = linear_speedup_form_1_raw_nae[OF wf k2 m_pos]
show "valid_ktm P" unfolding P_def by (rule wrap_prefix_patch_valid[OF F(1)])
have enc: "set (wrap_enc ?pack ?m w) ⊆ Sigma_ktm ?A"
if "set w ⊆ Sigma_ktm M" for w
by (rule ae_wrap_enc_in_Sigma[OF validM that m_pos])
have table: "(λu. u ∈ Lang_ktm M) = (λu. u ∈ Lang_user_wrap ?W)"
using F(2) by simp
have lang: "Lang_user_wrap P = Lang_ktm M"
proof -
have "Lang_user_wrap P = Lang_user_wrap ?W"
unfolding P_def table
by (rule wrap_prefix_language[OF validA positive blleA k2A width enc])
then show ?thesis using F(2) by simp
qed
show "Lang_ktm P = map Raw ` Lang_ktm M"
proof
show "Lang_ktm P ⊆ map Raw ` Lang_ktm M"
proof
fix v assume member: "v ∈ Lang_ktm P"
then have "set v ⊆ Raw ` Sigma_ktm M"
by (simp add: P_def Lang_ktm_iff)
then have "v ∈ lists (Raw ` Sigma_ktm M)" by (auto simp: in_lists_conv_set)
then obtain w where v: "v = map Raw w" by (auto simp: lists_image)
have "w ∈ Lang_user_wrap P"
unfolding Lang_user_wrap_def mem_Collect_eq using member unfolding v .
then show "v ∈ map Raw ` Lang_ktm M" using lang v by blast
qed
show "map Raw ` Lang_ktm M ⊆ Lang_ktm P"
using lang unfolding Lang_user_wrap_def by blast
qed
assume det: "det_ktm M"
have "det_ktm ?W"
by (rule linear_speedup_form_1_raw_dae(2)[OF wf det k2 m_pos])
then show "det_ktm P" unfolding P_def by (rule wrap_prefix_patch_det)
qed
lemma wrap_prefix_speedup_short:
fixes M :: "('s,'a) ktm"
and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm"
assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
and width: "N < m"
and word: "set w ⊆ Sigma_ktm M" and short: "length w ≤ N"
defines "P ≡ wrap_prefix_speedup m M N"
shows "reaches_state_in_time_ktm P (map Raw w)
(if w ∈ Lang_ktm M then t_ktm P else r_ktm P) (length w + 2)"
proof -
have m_pos: "0 < m" using width by linarith
let ?m = "m"
let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
let ?W = "encoding_wrap ?A ?pack ?m (Sigma_ktm M)"
have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
have positive: "0 < ?m" by (rule m_pos)
have blleA: "bl_ktm ?A ≠ le_ktm ?A"
using LE_block_neq_bl_block[OF m_pos blle]
by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
have pack: "?pack (take ?m (drop (i*?m) w)) ∈ Sigma_ktm ?A"
if "i*?m < length w" for i
using ae_wrap_enc_in_Sigma[OF validM word m_pos]
pack_take_in_set_wrap_enc[OF positive that, where pack="?pack"] by blast
have shortm: "length w < ?m" using short width by arith
have run: "reaches_state_in_time_ktm P (map Raw w)
(False, if w ∈ Lang_ktm M then t_ktm ?W else r_ktm ?W) (length w + 2)"
unfolding P_def
by (rule wrap_prefix_short_reaches[where A="?A" and pack="?pack" and m="?m"
and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N=N,
OF validA positive word blleA k2A pack shortm short])
show ?thesis using run by (cases "w ∈ Lang_ktm M") (simp_all add: P_def)
qed
lemma wrap_prefix_speedup_long:
fixes M :: "('s,'a) ktm"
and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm"
assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
and word: "set w ⊆ Sigma_ktm M" and long: "N < length w"
and run: "reaches_state_in_time_ktm (wrap_speedup m M) (map Raw w) (W_Run q) T"
and m_pos: "0 < m"
defines "P ≡ wrap_prefix_speedup m M N"
shows "reaches_state_in_time_ktm P (map Raw w) (False, W_Run q) T"
proof -
let ?m = "m"
let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
have positive: "0 < ?m" by (rule m_pos)
have blleA: "bl_ktm ?A ≠ le_ktm ?A"
using LE_block_neq_bl_block[OF m_pos blle]
by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
have pack: "?pack (take ?m (drop (i*?m) w)) ∈ Sigma_ktm ?A"
if "i*?m < length w" for i
using ae_wrap_enc_in_Sigma[OF validM word m_pos]
pack_take_in_set_wrap_enc[OF positive that, where pack="?pack"] by blast
show ?thesis unfolding P_def
by (rule wrap_prefix_transport[where A="?A" and pack="?pack" and m="?m"
and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N=N,
OF validA positive word blleA k2A pack long run])
qed
lemma wrap_prefix_speedup_accepts:
fixes M :: "('s,'a) ktm"
and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm"
assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
and width: "N < m"
and word: "set w ⊆ Sigma_ktm M"
and source: "accepts_in_time_ktm M w T"
defines "P ≡ wrap_prefix_speedup m M N"
shows "accepts_in_time_ktm P (map Raw w)
(wrap_prefix_speedup_bound N (m) (length w) T)"
proof (cases "length w ≤ N")
case True
have member: "w ∈ Lang_ktm M" using word source by (auto simp: Lang_ktm_iff)
have run: "reaches_state_in_time_ktm P (map Raw w)
(if w ∈ Lang_ktm M then t_ktm P else r_ktm P) (length w + 2)"
unfolding P_def by (rule wrap_prefix_speedup_short[OF wf k2 width word True])
show ?thesis using run member True
by (simp add: accepts_in_time_ktm_iff_reaches wrap_prefix_speedup_bound_def)
next
case False
have m_pos: "0 < m" using width by linarith
let ?m = "m"
let ?W = "wrap_speedup m M :: (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state,
('a,nat ⇒ 'a) wrap_alphabet) ktm"
have long: "N < length w" using False by simp
have raw: "accepts_in_time_user_wrap ?W w
(length w + (length w + ?m - 1) div ?m + 5
+ 2 * ((length w + ?m - 1) div ?m) + 8 * ((T + ?m - 1) div ?m) + 4)"
using linear_speedup_form_1_raw_nae(3)[where T="λ_. T",
OF wf k2 m_pos] word source by blast
have run: "reaches_state_in_time_ktm ?W (map Raw w)
(W_Run (t_ktm M, init_stage m (le_ktm M))) (wrap_speedup_bound ?m (length w) T)"
using raw by (simp add: accepts_in_time_user_wrap_def accepts_in_time_ktm_iff_reaches
t_ktm_alphabet_enlarge wrap_speedup_bound_def algebra_simps)
have "reaches_state_in_time_ktm P (map Raw w)
(False, W_Run (t_ktm M, init_stage m (le_ktm M))) (wrap_speedup_bound ?m (length w) T)"
unfolding P_def by (rule wrap_prefix_speedup_long[OF wf k2 word long run m_pos])
then show ?thesis using False
by (simp add: P_def accepts_in_time_ktm_iff_reaches
t_ktm_alphabet_enlarge wrap_prefix_speedup_bound_def)
qed
lemma wrap_prefix_speedup_bound_band:
assumes q: "0 < q"
and width: "16 * (3 + 8*c) * (q+1) + 16*c + 1 ≤ m"
and band: "⋀n. N0 ≤ n ⟹ n + n div q ≤ t n"
shows "wrap_prefix_speedup_bound (max N0 (q * (81 + 128*e))) m n (c*t n+e)
≤ max (n+2) (t n)"
proof (cases "n ≤ max N0 (q * (81 + 128*e))")
case True then show ?thesis by (simp add: wrap_prefix_speedup_bound_def)
next
case False
have far: "N0 ≤ n" and big: "q * (81 + 128*e) ≤ n" using False by auto
have "n + (n+m-1) div m + 5 + 2*((n+m-1) div m)
+ 8*((c*t n+e+m-1) div m) + 4 ≤ t n"
by (rule speedup_band_arith[OF q width big band[OF far]])
then show ?thesis using False
by (simp add: wrap_prefix_speedup_bound_def wrap_speedup_bound_def algebra_simps)
qed
theorem wrap_prefix_speedup_band:
fixes M :: "('s,'a) ktm"
and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
('a,nat ⇒ 'a) wrap_alphabet) ktm"
assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
and timed: "⋀w. w ∈ Lang_ktm M ⟹
accepts_in_time_ktm M w (c * t (length w) + e)"
and q: "0 < q"
and band: "⋀n. N0 ≤ n ⟹ n + n div q ≤ t n"
and large: "16 * (3 + 8*c) * (q+1) + 16*c + 1 ≤ m"
and width: "max N0 (q * (81 + 128*e)) < m"
defines "P ≡ wrap_prefix_speedup m M (max N0 (q * (81 + 128*e)))"
shows "time_bounded_conv P t"
proof -
have lang: "Lang_ktm P = map Raw ` Lang_ktm M"
unfolding P_def by (rule wrap_prefix_speedup_contract(2)[OF wf k2 width])
show ?thesis unfolding time_bounded_conv_def
proof
fix v assume "v ∈ Lang_ktm P"
then obtain w where v: "v = map Raw w" and member: "w ∈ Lang_ktm M"
using lang by blast
have word: "set w ⊆ Sigma_ktm M" using member by (simp add: Lang_ktm_iff)
have run: "accepts_in_time_ktm P (map Raw w)
(wrap_prefix_speedup_bound (max N0 (q * (81 + 128*e)))
(m) (length w) (c*t (length w)+e))"
unfolding P_def by (rule wrap_prefix_speedup_accepts[OF wf k2 width word timed[OF member]])
have "accepts_in_time_ktm P (map Raw w) (max (length w+2) (t (length w)))"
by (rule accepts_in_time_ktm_mono[OF run wrap_prefix_speedup_bound_band[OF q large band]])
then show "accepts_in_time_ktm P v (max (length v+2) (t (length v)))"
by (simp add: v)
qed
qed
end