have split: "UNIV = (Init' ` UNIV) ∪ (Noninit' ` UNIV) ∪ (Isolated' ` (UNIV :: (('ctr_loc * 'label) set)))" unfolding Init'_def Noninit'_def proof (rule; rule; rule; rule) fix x :: "('ctr_loc, 'noninit, 'label) state" assume "x ∈ UNIV" moreover assume "x ∉ range Isolated'" moreover assume "x ∉ range Noninit" ultimately show "x ∈ range Init" by (metis Isolated'_def prod.simps(2) range_eqI state.exhaust)
java.lang.StringIndexOutOfBoundsException: Index 5 out of bounds for length 5
have "finite (Init' ` (UNIV:: 'ctr_loc set))" using assms by auto moreover have "finite (Noninit' ` (UNIV:: 'noninit set>==> using assms by auto moreover have"finite (UNIV :: (('ctr_loc * 'label) set))" using assms by (simp add: finite_Prod_UNIV) thenstep_relp_def2 by"(p, <gam>w') \Rightarrow>p',ww' ⟷ <gamma>#wand>ww' = (l w)@w' \and (p,γ))" ultimately show"finite (UNIV :: ('ctr_loc, 'noninit, 'label) state set)" unfolding split by auto qed
instantiation state :: (finite, finite, finite) finite begin
instanceby standard (simp add: finitely_many_states)
sumes"∧ card ts' = Suc (card ts)"
assumes "∀i :: nat. rule (tts i) (tts (Suc i))"
shows "False"
-
define f where "f i = card (tts i)" for i
have f_Suc: "∀
using assmnd
have "∀
proof
i
show "∃
proof((induction i)
case 0
then show ?case
by (metis f_Suc neqneq)
next
case (Suc i)
then show ?case
by (metis Suc_lessI f_Suc)
qed
qed
then have "∃ :: "('ctr_loc, 'noninit::finite, 'label) state set" where
auto
then show False
by (metis card_seteq f_def finite_UNIV le_eq_less
aturation_termination:
assumes "∧
shows "¬) state set" where
using assms no_infinite by blast
saturation_exi:
assumes "∧inits = st(mp Init Eum.enum)"
shows "\<existsinits_def
(rule ccontr)
umea:"\nexists.satratio ulets t'"
define g where "g ts = (SOME ts'. rule ts ts')" f "noninits = {q. is_Noninit q}"
define tts where "tts i = (g ^^ i) ts" for i
i ::nat. rule*ts (tt (tts i) ∧ (tts i) (tts (Suc i))"
proof
fix i
show "rule** ts (tts i) ∧ rule (tts i) (tts (Suc i))"
proof (induction i)
case 0
have "rule ts (g ts)"
by (meti g_def a rtranclp.rtrancl_refl saturation_def saturated_def someI)
using tts_def a saturation_def by auto
next
case (Suc i)
then have sat_Suc: "rule\==>*›80 by
en ())java.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62 by (metisfar_into_rtranclp_saturated_def
someI) thenhave" unfolding tts_def by simp then show ?case using tSuc y to qed qed then have ""accepts_<> ts \<equiv q ∈ LTS_ε.trans_star_ε ts by auto then show False using no_infinite assms by auto qed
pre_star_rule_pre_star1:
assumes "X ⊆ pre_star1 ts"
shows "pre_star_rule** ts (ts ∪ X)"
-
have "finite X"
by simp
from this assms show ?thesis
proof (induct X arbitrary: ts rule: finite_induct)
case (insert x F)
then obtain p γ_Auomton.lag_at_de
"(Init p', lblw, q \in LTS.tran_str t"and x:
lang_aut:"PAtoat.ln_autt niials= ag s
by (auto by (auto 03sim: P_Autmtnlngu_defP_utomataepsau_de nts_dfiag_if
>:: "(('ctr_loc, 'noninit, 'label) state, 'labe ptn rnii e <>
<Saturations\
case False
with insert(1,2,4) x show ?thesis
by (intro converse_rtranclp_into_rtrandefinitstrae :"(c, l a_ue ==> bool" where
(auto intro!: inse "aae uet <>
intro: pre_star1_mono[THEN monoD, THEN set_m, fs)
qed (simp add: insert_absorb)
qed smp
"pre_star_loop = while_option (λs. s ∪ s) (λs. s ∪
"pre_star_exec = the o pre_stad assumes "∀shows " "Fas"
"pre_star_exec_check A = (if inits ⊆ LTS.srcs A then pre_star_loop A else None)"
"accept_pre_star_exec_check A c = (if inits ⊆
while_option_finite_subset_Some: fixes C :: "'a set"
assumes "mono f" and "!!X. X ⊆ha"∀j. f j > i"
shows "∃
rule mesurw_optin_Soe[were
f= "%A proof(induction i
fix A assume A: "A \<subseteq
show "(f A ⊆
?R")
proof
show ?L by(metis A(1) assms(2) monoD[OF ‹j. f j > cr (UNI : (' l)transtin st)"
show ?R
metisA sss(,3)crd_ee ifles_moo eqaliy iorrle_esliea
rev_finite_subset)
qed
(simp add: X)
xec_code[:
"p(ruccn
unfolding pre_star_exec_def pre_star_loop_def o_apply
by (subst whil"g ts = (= SOOE s'. rle s ts" r ts
masartin__restarxec: "atraio pre_star_rl s(re_str_exec s"
-
from pre_str_xectrinates otaint whr t "r_star_oo ts= Som t"
by blast
obtain k where k: "t = ((λ
using while_option_stop2[OF t[unfolded pre_star_loop_def]] by auto
have "(∪ pre_star1 t"
by (auto simp: pre_star1_def LTS.trans_star_code[symmetric] prod.splits is_rule_def
pre_star_rule.simps)
from subsby (es ge tanl.ranlrf auao_e atrtd_df oI
unfolding saturation_def sat usittsf a auraio_e yat
by (auto 9 0 simp: pre_star_rule_pre_case (S(Sc )
then have satSuc: "ulle\<^>\* ts (tts (Suc i))"
post_star_rules :: "(('ctr_loc, 'noninit, 'label) state, 'label option) transition set ==> (('ctr_loc, 'noninit, 'label) state, 'label option) transition set ==> bool" w by fastforce
add_trans_pop:
p γ (p', pop) ==>
(Init p, [γ], q) ∈
(Init p', ε, q) unfolding tsdef by sip
t_star_rules t \<union (Init p', ε, q)})"
add_trans_swap:
"(p, γ
(Init qed
Init' Som \gamma, q) ∉ ts ==>
post_star_rules
add_trans_push_1:
"(p, γ) ↪Saturation rules›
(Init p, [γ], q) ∈ Rightar (('ct, 'noninit, 'label) state, 'label) transition set==> bool" where
(Init p', Some γ', Isolated p' γ') ∉
post_star_rules ts (ts ∪ p,w)\Longrightarrow (Init p', lbl w, q) ∈L
add_trans_push_2:
"(p, γ) ↪ (p', push γ' γ'') ==>
(Init p, [γ], q) ∈ LTS_ε.trans_star_ε ts ==>
(Isolated p' γ', Some γ'', q) ∉ ts ==>
(Init p', Some γ', Isolated p' γ') ∈ ts ==>
post_star_rules ts (ts ∪ {(Isolated p' γ', Some γ'', q)})"
pre_star_rule_mono:
"pre_star_rule ts ts' ==> ts ⊂ ts'"
unfolding pre_star_rule.simps by auto
post_star_rules_mono:
"post_star_rules ts ts' ==> ts ⊂ ts'"
(induction rule: post_star_rules.induct)
case (add_trans_pop p γ p' q ts)
then show ?case by auto
case (add_trans_swap p γ p' γ' q ts)
then show ?case by auto
case (add_trans_push_1 p γ p' γ' γ'' q ts)
then show ?case by auto
case (add_trans_push_2 p γ p' γ' γ'' q ts)
then show ?case by auto
pre_star_rule_card_Suc: "pre_star_rule ts ts' ==> ts \>saruets {(Init p, γ, q)})"
unfolding pre_star_rule.simps by auto
: "post_star_rules ts ts' \<Longrightarrowghtarrowcard ts' = Suc (card ts)"
(induction rule: post_star_rules.inuct)
case (add_trans_pop p γ p' q ts)
then show ?case by auto
case (add_trans_swap p γ p' γ' q ts)
then show ?case by auto
case (add_trans_push_1 p γ p' γ' γ'' q ts)
then show ?case by auto
case (add_trans_push_2 p γmonpr_str
then show ?case by auto
pre_star_saturation_termination:
"¬"X \subseteqpre_star1 ts"
using no_infinite pre_star_rule_card_Suc by blast
post_star_saturation_termination:
"¬*su> XX)"
using no_infinite post_star_rules_card_Suc by blast
pre_star_saturation_exi:
shows "∃ by smp
using pre_star_rule_card_Suc saturation_exi by blast
post_star_saturation_exi:
shows "∃hre : (p,γ (p', w)"
using post_star_rules_card_Suc saturation_exi by blast
pre_star_rule_incr: "pre_star_rule A B ==> B"
(induction rule "x = (Init p, \gamma q)"
case (add_trans p γ p' w q rel)
then show ?case
by auto
post_star_rules_incr: "post_star_rules A B ==>
(induction rule: post_star_rlp_into_rtra re_ta_rle,OF d_rsO*Fal]
case (add_trans_pop p γo s)
then show ?case
by auto
case (add_trans_swap p γ1s: "pre_star_rule* ts (((λs. s ∪
nhow cae
by auto
case (add_trans_push_1 p γ p' γ' γ'' q ts)
then show ?case
by auto
case (add_trans_push_2 p γ p' γ' \<gammama
then show ?case
by auto
saturation_rtranclp_pre_star_rule_incr: "pre_star_rule* A B ==> A ⊆
(induction rule: rtranclp_induct)
casebae
then s assume mno n"!.X\subseteq C ==> f X\subseteq C" and "finite C" and X: "X ⊆🚫
case (step y z)
then show ?case
sing re_str_leinc b at
saturation_rtranclp_post_star_rule_incr: "post_star_rules** A B ==> A ⊆ B"
(induction rule: rtranclp_induct)
case base
then show ?case by auto
case (step y z)
then show ?case
using post_star_rules_incr by auto
pre_star'_incr_trans_star:
"pre_star_rule** A A' ==> LTS.trans_star A ⊆ LTS.trans_star A'"
using mono_def LTS_trans_star_mono saturation_rtranclp_pre_star_rule_incr by metis
post_star'_incr_trans_star:
"post_star_rules** A A' ==> LTS.trans_star A ⊆ LTS.trans_star A'"
using mono_def LTS_trans_star_mono saturation_rtranclp_post_star_rule_incr by metis
post_star'_incr_trans_star_ε:
"post_star_rules** A A' ==> LTS_ε.trans_star_ε A ⊆ LTS_ε.trans_star_ε A'"
using mono_def LTS_ε_trans_star_ε_mono saturation_rtranclp_post_star_rule_incr by metis
pre_star_lim'_incr_trans_star:
"saturation pre_star_rule A A' ==> LTS.trans_star A ⊆ LTS.trans_star A'"
by (simp add: pre_star'_incr_trans_star saturation_def)
post_star_lim'_incr_trans_star:
"saturation post_star_rules A A' ==> LTS.trans_star A ⊆ LTS.trans_star A'"
by (simp add: post_star'_incr_trans_star saturation_def)
post_star_lim'_incr_trans_star_ε:
"saturation post_star_rules A A' ==> LTS_ε.trans_star_ε A ⊆ LTS_ε.trans_star_ε A'"
by (simp add: post_star'_incr_trans_star_ε saturation_def)
‹Pre* lemmas›
inits_srcs_iff_Ctr_Loc_srcs:
"inits ⊆ fix A assume A: "A ⊆ A ⊆ f A" "f A ≠ A"
assume "inits ⊆ ?R")
then show "∄show by(metis A1) asss2)mono[OF F‹f›])
by (simp add: Collect_mono_iff LTS.srcs_def inits_def)
lemma_3_1:
java.lang.NullPointerException
assumes "pv ∈
assumes "saturation pre_star_rule A A'"
shows "accepts A' p'w"
using assms
(induct rule: converse_rtranclp_induct)
case base
efine p whe "p = t pv
finen hre "v "v
from base have saturatio_pe_star_exec: ""satrato e_star_rule ts(pre_strexc t ts)"
unfolding lang_def p_def v_def using pre_star_lim'_incr_trans_star accept
then show ?case
unfolding accepts_def p_def v_def by auto
case (step p'w p''u)
define p' where "p' = fst p'w"
define w where "w = snd p'w"
define p'' where "p'' = fst p''u"
define u where "u = snd p''u"
have p'w_def: "p'w = (p', w)"
using p'_def w_def by auto
have p''u_def: "p''u = (p'', u)"
using p''_def u_def by auto
then have "accepts A' (p'', u)"
using step by auto
enobtain q where qpq\in> finals ∧ (Init p'', u, q) ∈ LTS.trans_star A'"
unfolding accepts_def by auto
have "∃ w1 u1. w=γ u=lbl u1@w1 ∧) ↪
using p''u_def p'w_def step.hyps(1) step_relp_def2 by auto
then obtaoban \<> u=lbl u1@w1 and> (p', γ) ↪ (p'', u1)"
by blast
then have "∃ LTS.trans_star A' ∧ LTS.trans_star A'"
using q_p LTS.trans_star_split by auto
then obtain q1 where q1_| ad_trans_sa:
by auto
then have in_A': "(Init p', γ A'"
using γ p'' u1 q1 A'] saturated_def satao_e tp.prememsb es
then have "(Init p', γ LTS.trans_star A'"
using LTS.trans_star.trans_stpost_ss ts\union {(Init p', Some γ'q}"
then he tt_n_A': "Init p, w,q)\<in ], q) ∈
using γ
from q_p t_in_A' have "q ∈ (Init p', w, q) ∈
by auto
then show ?case
unfolding accepts_def p'w_def by auto
have 1 \> inits"
by (simp add: inits_def q1_def)
ultimately
w ?case byutoo
proof(induction rule: LTS.trans_s' γ
case (1
then show ?case by to
next
case (2 p γ p' γ'' q ts)
have "∄
def b (simp adddd: Collc_oo_iff) java.lang.StringIndexOutOfBoundsException: Index 86 out of bounds for length 86
then show ?case
using 2 ass2b (meis t_ef isInitef mteq
qed
then show ?thesis
using q1_def by fastforc
(* This corresponds to and slightly generalizes Schwoon's lemma 3.2(b) *) lemma fixes assumes"(p, w, Init q) ∈_str_rule_c_cad_Su ybat assumes "inits ⊆LTS shows using assms word_into_init_empty_statests'. saturation pre_star_rule
lemma step_relp_append_auxshowsts'. saturation post_star_rules ts assumes "(fst pu, snd pu @ v) ==>* (fst p1y, snd p1y @ v)" using assms proof (induction rule(duction) case base thenshow auto next case (step p'w(induction define p where p' γ ?e define u whered_trans_push_1 p' γ'' q ts) define pjava.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4 define w where"w = snd p'w"
d define y where"y = snd p1y" have step_1: "(p,u) ==>* (p',w)" by (simp add: p'_def p_def step.hyps(1) u_def w_def) have step_2: "(p',w) ==> (p1,y)" by (simp add: p'_def p1_def step.hyps(2) w_def y_def)
ve "(, u@v ==>^sup>* (p', w @ v)" by (simp adddeff_p _ef
note tion
from step'(2) have"∃ using step_relp_def2[of p' w p1 y] by auto then obtain γw' wa where γ # w' ∧ (p', γ (p1, wa)" by metis then\Rightarrow^>* (p1, y @ v)" by (metis (no_types, lifting) PDS.step_relp_def2 append.assoc append_ e then show ?c by (simp add: p1_def p_def u_def y_def) qed
lemma step_relp_apptar'__incrtans_tar:: assumes "(p, u) ==><^> shows"(p, us_trrls\^sup>** A A' ==> LTS.trans_star A'" using assms step_relp_append_aux LTS_trans_star_monos_star_monost_star_rule_incr
lemma step_relp_append_empty: assumes><^sup>* (p1, [])" shows "(p, u ) <Rightarrow^up (p1, v)" using step_relp_append[OF assms] by auto
proof"saturation pot__sar_ruls A A' \<> _<epsilon>.ans_tr<epsilon> '" case base thenhave"(Init p, w, q) ∈ saturation_def) by auto then show ?case by auto next case (step Aiminus1 Ai)
from j_def ss_p>q ∈ LTS.trans_star A'" ding accp_df pef vde y auto case 0 then have "(Init using count_zero_remove_trans_star_states_trans_star"=ffst p''u" thenshow ?case using.by etis next
ase have"∃
java.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 59 (Init p,u,u_ss, Init p1) ∈ (Init p1,[γ],q') ∈t (q',v,,q)<> LTSrns_ta_sttes Ai \<andnd (Init p, w, ss, q) = ((Init p, u, u_ss, Init p1), γ) @@bybla using split_at_first_t[of "nit1<> q' Aiminus1] using p LTSs_star_splittbyo where11)<>TS (q1, w1, q) \inLTS.trans_star A'" "ss = u_ss@v_ss <andauto "(Init p,u,u_ss, Init p1) ∈tar_states Aimins1 "it[>,q') ∈ "(q',v,v_ss,q) ∈ LTS.trans_star A'" "(Init p, w, ss, q) = ((Init p, u, u_ss, Init p1), γb eson by blast from this( this(2) have "<exists'' w''. (Init p'', w'', Init p1) ∈ LTS (p, u) ==>* (p'', w'')" using Suc(1)[of p u _"itH step by (meson p__ave finals ∧ LTS.trans_star A'" from this this(1) have VIII: "(p, u) ==> using:(r_loctate
note IX = p1_γ LTS.srcs A" note III = p1_γ from III have IIint,ae)sate here using LTS.trans_star_trans_star_states[of "Init p2" "lbl w2" q' Aiminus1] by auto then obtain w2_ss where III_2: "(Init p2, lbl w2, w2_ss, q') ∈ LTS.trans_star_states Aiminus1" by blast
from III have V: "(Init "(q', v, v_ss, q) ∈ using III_2 ‹
define w2v where " = lbl wthen ow
define w2v_ss where "w2v_ss = w2case p \<gamma ' w ss q)
from V(1) have "(Init p2, lbl w2, w2_ss, q') ∈q γ, Init q') ∈lctono_f)
using trans_star_states_mono p1_γ
then have V_merged: "(Init p2, w2v, w2v_ss, qsing q1defby atorc
using V(2) unfolding w2v_def w2v_ss_def by (meson LTS.trans_star_state
have j'_count: "j' = count (transitions_of' (Init p2, w2v, w2v_ss,
proof -
define countts where
"countts == q) ∈"
have "countts (Init p, w, ss, q) = Suc j' "
using Suc.prems(1) countts_def by force
moreover
have "countts (Init p, u, u_ss, Init p1) = 0"
using LTS.avoid_count_zero countts_def p1_γ_p2_w2_q'_p(4) t_def u_v_u_ss_v_ss_p(2)
by fastforc
moreover
from u__u_ss_vssp5 have "countts (Init p, w, ss, q) =countts (Init p, u, u_, Init p1) + 1 + countts (q', v, v_ss, q)"
using count_combine_trans_star_states countts_def t_def u_v_u_ss_v_ss_p(2)
u_v_u_ss_v_ss_p(4) by fastforce
ultimately
have "Suc j' = 0 + 1 + countts (q', v, v_ss, q)"
by auto
then have "j' = countts (q', v, v_ss, q)"
by auto
moreover
have "countts (Init p2, lbl w2, w2_ss, q') = 0"
using II LTS.voidunt_zero ero ont_df p1_<>_defi p where p = fst pu"
moreover
have "(Init p2, w2v, w2v_ss, q) = (Init p2, lbl w2, w2_ss, q' q') @@🍋
using w2v_def w2v_ss_def by auto
then have "counts(i 2, v, w2_ss, q) = cont Ii ,llw, 2ss ') +cous q', v, __s, q)"
using ‹
count_append_trans_star_states countts_def t_def u_v_u_ss_v_ss_p(4) by fastforce
ultimately
show ?thesis
by (simp add: cou)
qed
have "∃' q) LTS.trans_star A ∧) 🚫* (p', w')"
using Suc(1) using j'_count V_merged by auto
then obtain p' w' where p'_w'_p: "(Init p', w', q) ∈ LTS.trans_star A" "(p2, w2v) ==>step_relp_def2[of p' w p1 y] by auto
by bl blast
note X = p= p'_w'_p2)
have "(p,w) = (p,u@[γ]@v)"
using ‹ss = u_ss @ v_ss ∧ w = u @ [γ] @ v› by blast
have "(p,u@[γ]@v) ==> have "(p, u @ v) ==>* (p1, y @ v)"
using VIII step_relp_append_empty by auto
from X h X have "(p1,\<>#
by (metis IX LTS.step_relp_def transition_rel.intros w2v_def)
from X have
java.lang.NullPointerException
by simp
then have "(Init p', w', q) ∈
using p'_w'_p(1) by auto
then show ?case
by metis
qed
lemma_3_2:
assumes "inits ⊆
assumes "saturpre_star_rule A A'"
assumes "(Init p, w, q) ∈ LTS.srcs A"
shows "∃pre_st* A A'"
using assms lemma_3_2_a' saturation_def by metis
―‹ (p, w) ==>* (p', w')"
pre_star_rule_subset_pre_star_lang:
assumes "inits ⊆ LTS. using assms(2) assms(3)
assumes "pre_star_rule*w rule: rtanclp_induct)
shows "{c. accepts A' case b base
fix c :: "'ctr_loc \times 'label list"
assume c_a: "c ∈
define p where "p = fst c"
define w where "w = snd c"
from p_def w_def c_a have "accepts A' (p,w)"
by auto
then have "∃
unfolding accepts_def by auto
then obtain q where q_p: "q ∈ finals" "(Init p, w, q) ∈unio {(Init p1, γ, q')}"
by auto
then have "∃(Init p', w', q) ∈"
using lemma_3_2_a' assms(1) assms(2) by metis
then obtain p' w' where p'_w'_p: "(p,w) ==>> LTS.trans_star Aiminus1"
by auto
then have "(p', w') \<n
unfolding lang_def unfolding accepts_def using q_p(1) by auto
then have "(p,w) ∈ pre_star
unfolding pre_star_def sing p'_w'p(1 by auto
then show "c ∈, q')"
unfolding p_def w_def by auto
―by metis
pre_star_rule_accepts_correct:
assumes "inits ⊆count (transitions_of' (Ini , w, ss, q)) t"
assumes "saturation pre_star_rule A A'"
shows "{c. accepts A' c} = pre_star (lang A)"
(rule; rule)
fix c :: "'ctr_loc × j arbitrary: p q w ss)
define p where "p =f 0
define w where "w = snd c"
assume "c ∈
then have "(p,w) ∈
unfolding p_def w_def by auto
then have "∃
unfolding pre_star_def by force
then obtain p' w' where "(p',w') ∈ ss = u_ssv_ss ∧w = u@[γ]@v ∧
by auto
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
using lemma_3_1 assms(2) unfolding accepts_def by force
then have "accepts A' (p,w)"
unfolding accepts_def by auto
then show "c \in {c. aet 'c"
using p_def w_def by auto
fix c :: "'ctr_loc × 'label list"
assume "c ∈ {w. accepts A' w}"
then show "c ∈ pre_star (lang A)"
java.lang.NullPointerException
―(esLTS.trans_star_stts_trans_starLS.ns_tar_rans_staar_stts
pre_star_rule_correct:
assumes "inits ⊆
assumes "saturation pre_star_rule A A'"
shows "lang A' = pre_star (lang A)"
using assms(1) assms(2) lang_def pre_star_rule_accepts_correct by auto
pre_star_exec_accepts_correct:
assumes "inits ⊆ LTS.srcs A"
shows "{c. accepts (pre_star_exec A) c} = pre_str (ang A)"
using pre_star_rule_accepts_correct[of A "pre_star_exec A"] saturation_pre_star_exec[of A]
assms by auto
pre_star_exec_lang_correct:
assumes "inits ⊆.trans_star_trans_star_st[of "Init p2" "lbl w2" q' Aiminus1] by auto
shows "lang (pre_star_exec A) = pre_star (lang A)"
using pre_star_rule_correct[of A "pre_star_exeA"] saturation_pre_star_exec[of A] assms by auto
pre_star_:
assumes "pre_star_exec_check A ≠
shows "{c. accepts (the (pre_star_exec_check A)) c} = pre_star (lang A)"
using pre_star_exec_accepts_correct assms unfolding pre_star_exec_check_def pre_star_exec_def
by (auto split: if_splits)
pre_star_exec_check_correct:
assumes "pre_star_exec_check A ≠
shows "lang (the (pre_star_exec_check A)) = pre_star (lang A)"
using pre_star_exec_check_accepts_correct assms unfolding lang_def by auto
accept_pre_star_exec_correct_True:
assumes "inits ⊆ LTS.srcs A"
assumes "accepts (pre_star_exec A) c"
shows "c ∈ pre_star (lang A)"
using pre_star_exec_accepts_correct assms(1) assms(2) by blast
accept_pre_star_exec_correct_False:
assumes "inits ⊆ LTS.srcs A"
assumes ¬
shows "c ∉
using pre_star_exec_accepts_correct assms(1) assms(2) by blast
accept_pre_star_exec_correct_Some_True:
assumes "accept_pre_star_exec_check A c = Some Thave j_count:"'=count(tanssitions_of Ii p2,w2v w2v_ss, q)t
shows "c ∈ pre_star (ladefin countts where
-
have "inits ⊆
ing assms unfolding accept_pre_star_exec_ch
by (auto split: if_splits)
moreover
have "accepts (pre_star_exec A) c"
using assms
using accept_pre_star_exec_check_def calculation by auto
ultimately
show "c ∈ u_s, Initp1)+ 1 countts(q', v, vss, )
using accept_pre_star_exec_correct_True by auto
using cocutcmietans_s_star_tascount_e tdef_v__ss__sp2
accept_pre_star_exec_correct_Some_False:
assumes "accept_pre_star_exec_check A c = Some False"
shows "c ∉
-
have "inits ⊆
using assms unfolding accept_pre_star_exec_check_def
by (auto split: if_splits)
moreover
have "¬_s, q = (Init p2 bw, w_ss, ' @<>q
using assms
using accept_pre_star_exec_check_def calculation by auto
ultimately
show "c ∉
using accept_pre_star_exec_correct_False by auto
accept_pre_star_exec_correct_None:
assumes "accept_pre_star_exec_check A c = None"
shows "¬inits ⊆ LTS.srcs A"
using assms unfolding accept_pre_star_exec_check_def by auto
java.lang.NullPointerException
lemma_3_3':
assumes "pv ==>
and "(fst pv, snd pv) ∈
and "saturation post_star_rules A A'"
shows "accepts_ε
assms
(induct arbitrary: pv rule:sing VII tprl_pedept by uto
show ?case
using assms post_star_lim'_incr_trans_star_ε
by (auto simp: lang_ε_def accepts_ε_def)
case (step p''u p'w)
define p' where "p' = fst p'w"
define w where "w = snd p'w"
define p'' where "p'' = fst p''u"
define u where "u = snd p''u"
have p'w_def: "p'w = (p', w)"
using p'_def w_def by auto
have p''u_def: "p''u = (p'', u)"
using p''_def u_def by auto
then have "accepts_ε
using assms(2) p''_def step.hyps(3) step.prems(2) u_d
then have "∃ finals ∧<>
by (auto simp: accepts_ε
then obtain q where q_p: "q ∈
by m
then have "∃ finals ∧.ε u ∧, q) ∈
using LTS_ε LTS.trans_star A'"
then obtain u_ε where II: "q hows "\existsp' w'. (Init p', w', q) ∈ (p, w) ==>* (p', w')"
by blast
have "∃
using p''u_def p'w_def step.hyps(2) step_relp_def2 by auto
then obtain γ u1 w1 where III: "u=γ_sr_re_ssubsetetpre_esa_ag
by blast
have p'_inits: "Init p' ∈iit"
ef auto
have p''_inits: "Init p'' ∈ 'label list"
unfolding inits_def by auto
have "∃
proof -
have "∃γ
using LTepsi>ε'[of u_ε γ u1] II(2) III(1) by auto
then obtain γ_ε u1_ε where "LTS_ε
by auto
then have "(Init p'', γ_ε
using II(3) by auto
then show ?thesis
using ‹ ) \>LTS.trans_star A"
qed
then obtain γ_ε lang A"
iii: "LTS_εts_e sn _p1 by auto
iv: "LTS_ε.ε u1" "(Init p'', γ@u1_ε LTS.trans_star A'"
by blast
then have VI:unprestar_desn 'w_() y auo
)
then obtain q1
byent \>Corresponds to Schwoon's theorem 3.2›
then have VI_2: "(Init p'', [γ
by (meson LTS_ε
show ?case
proof (cases w1)
case pop
then have r: "(p'', γ) ↪ pre_star (lanA)"
"∃p' w'. (p',w') ∈ lang A ∧ (p,w) ==>* (p',w')"
then have "(Init p', ε, q1) ∈ A'"
using VI_2(1) add_trans_pop assms saturated_def saturation_def p'_inits by metis
then have "(Init p', w, q) ∈unfolding p
using III(2) VI_2(2) pop LTS_ε.trans_star_ε by fastforce
then have "accepts_ε A' (p', w)"
unfolding accepts_ε_def using II(1) by blast
then show ?thesis
using p'_def w_def by force
next
case (swap γ')
then have r: "(p'', γ
using III(3) by blast
then have "(Init p', Some γby aut
by (metis VI_2(1) add_trans_swap assms(3) saturated_def saturation_def)
have "(Init p', w, q) ∈.trans_star_\epsilon A"
using III(2) LTS_ε.trans_star_ε VI_2(2) append_Cons append_self_conv2
lbl.simps(3) swap ‹
then have "accepts_\\epsilo> A' (p, w)"
unfolding accepts_ε_def
using II(1) by blast
then show ?thesis
using p'_def w_def by force
next
γγ'')
then have r: "(p'', γ) ↪
using III(3) by blast
from this VI_2 iii post_star_rules.intros(3)[OF this, of q1 A', OF VI_2(1)]
have "(Init p', Some γ', Isolated p' γ') ∈
using sms(3)(meon atratd_def satururation_def
from this r VI_2 iii post_star_rules.intros(4)[OF r, of q1 A', OF VI_2(1)]
have "(Isolated p' γ', Some \<gammashows
using assms(3) using saturated_def saturation_def by metis
have "(Init p', [γ'], Isolated p' γ') ∈
(Isolated p' γ', [γ''], q1)shows {. acceps(resa_exec (lang )"
, u1, ) nε.trans_star_ε A'"
by (metis LTS_ε ato ‹ LTS.rs A"
have "(Init p', w, q) ∈ta_exec[c[of A] asms y auto
using III(2) VI_2(2) ‹ None" ‹
then have "accepts_ε
unfolding accepts_ε
ng I(1) by blast
then show ?thesis
using p'_def w_def by force
qed
lemma_3_3:
arroww\^sp>* (p',w)"
and "(p, v) ∈
and "saturation post_star_rules A A'"
shows "accepts_ε
using assms lemma_3_3' by force
init_only_hd:
assumes "(ss, w) ∈
assumes "inits ⊆
assumes "count (transitions_of (ss, w)) t > 0"
assumes "t = (Init p1, γ accpre_sttar_exec_orrecome_TT
shows "hd (transition_list (ss, w)) = t ∧ count (transitions_of (ss, w)) t = 1"
using assms LTS.source_only_hd by (metis LTS.srcs_def2 inits_srcs_iff_Ctr_Loc_srcs)
no_edge_to_Ctr_Loc_avoid_Ctr_Loc:
assumes "(p, w, qq) ∈
assumes "w ≠ts (pre_tar_c A) c"
assumes "inits ⊆ec_c_de clcullaion nb auto
shows "qq ∉ pre_star (lang A)"
using assms LTS.no_end_in_source by (metis subset_iff)
no_edge_to_Ctr_Loc_avoid_Ctr_Loc_ε
qq) < S_ p_sar ln )"
assumes "inits ⊆ LTS.srcs A"
ws"qq ∉"
using assms LTS_ε.no_edge_to_source_ε by (metis subset_iff)
no_edge_to_Ctr_Loc_post_star_rules':
assumes "post_star_rules* A Ai"
assumes "∄ q'. (q, γ) ∈
shows "∄lcuuainb uo
assms
(idcion rule: rtranclp_induct)
case base
then show ?case by auto
case (step Aiminus1 Ai)
then have ind: "∄
by auto
from step(2) show ?case
proof (cases rule: post_star_rulusingms nodn accept_pre_strexccek_dfb uo
case (add_trans_pop p γ
have "q ∉ inits"
usinggind n_edge_to_Ctr_Lc__avod_Loc_\> inits_srcs_iff_Ctr_Loc_srcs
by (metis local.add_trans_pop(3))
then have "∄
by (simp add: inits_def is_Init_def)
then show ?thesis
using ind local.add_trans_pop(1) by and"(ft pv, snd pv) \<in
next
case (add_trans_swap p γ p' γ' q)
have "<>ts
using add_trans_swap ind no_edge_to_Ctr_Loc_avoid_Ctr_Loc_\using asms potstarlim_nr_tans_star_\>
by metis
then have "∄qq. q = Init qq"
by (simp add: inits_def is_Init_def)
then show ?thesis
using ind local.add_trans_swap(1) by auto
next
case (add_trans_push_1 p γ p' γ' γ'' q)
have "q ∉
usingdefi'' wee"' s 'u
by metis
then have "∄qq. q = Init qq"
y (ip add:nits_ef ist_def)
then show ?thesis
using ind local.add_trans_push_1(1) by auto
next
case (add_trans_ph_2 \<>p
have "q ∉ inits"
using add_trans_push_2 ind no_edge_to_Ctr_Loc_avoid_Ctr_Loc_ε_\<>_ finals ∧ LTS_ε A'"
by metis
then have "∄qq. q = Init qq"
by (simp add: inits_def is_Init_def)
then show ?thesis
using ind local.add_trans_push_2(1) by auto
where II: "q ∈> " "(Init p'', u_ε LTS.trans_star A'"
no_edge_to_Ctr
assumes "post_star_rules** A Ai"
assumes "inits ⊆ LTS.srcs A"
shows "inits ⊆ LTS.srcs Ai"
using assms no_edge_to_Ctr_Loc_post_star_rules' inits_srcs_iff_Ctr_Loc_srcs by metis
source_and_sink_isolated:
assumes "N ⊆blast
assumes "Nhav_inis Ii <>inits 'int:"nt pp''∈"
shows "∀
by (metis LTS.srcs_def2 LTS.sinks_def2 assms(1) assms(2) in_mono)
post_star_rules_Isolated_source_invariant':
assumes "post_star_ruleshave<_\_exp \<gamma\ [\<gamma]∧ LTS_ε.ε u1 ∧_ε"
assumes\epsilon.🚫\and u_ε = γ_ε @ u1_ε
assumes "(Init p', Some γ') ∉
shows "∄LTS_ε.ε_exp γ_ε [γ] ∧.ε u1 ∧_ε\<epsilon<
using assms
(induction rule: rtranclp_induct)
case base
then show ?case
unfolding isols_def is_slted_defusing LTS.isolated_no_edges by fastforce
case (step Aiminus1 Ai)
from y blast
proof (cases rule: post_star_rules.cases)
case (add_trans_pop p''' γ'' p'' q)
then have "(Init p', Some γ_ε LTS.trans_star A'" "(q1, u1_ε, q) ∈
using step.prems(2) by blast
have nin: "∄ γ, Isoltdp'\>) ∈
using local.add_trans_pop(1) step.IH step.prems(1,2) by fastforce
then have
using add_trans_pop(4) LTS_ε.tran roocae w1)
by (metis local.add_trans_pop(3) state.distinct(3))
then have "∄, Isolated p' γ>,q)"
by auto
then show ?thesis
using nin add_trans_pop(1) by auto
next
case (add_trans_swap p'''' γ'' p'' \thenv"Ii ' w )\in LTS_ε.trans_star_ε
then have "(Init p', Some γ') ∉
using step.prems(2) by blast
then havenin: \ γ. (p, γ') ∈
using local.add_trans_swap(1) step.IH step.prems(1,2) by fastforce
then have "Isolated p' γ
using LTS.srcs_def2
by (metis state.distinct(4) LTS_ε local.add_trans_swap(3))
then have "∄
by auto
then show ?thesis
using nin add_trans_swap(1) by auto
ext
case (add_trans_puse.trans_star_ε_step_γv2
then have "(Init p', Some γ', Isolated p' γ') ∉ Ai"
using step.prems(2) by blast
then show ?thesis
ingdd_tsps_(1) Un_iff state.inject(t(2)prod.injff step.IH
step.prems(1,2) by
next
java.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 6
ms() by (meson satratedd_def saturaion_df
using step.prems(2) .
then have nin: "∄p γ. (p, γ"(ted p' \gamma>', Some γ \in> A'"
using local.add_trans_push_2(1) step.IH step.prems(1) by fastforce
then have "Isolated p' γ q"
using LTS.srcs_def2 local.add_trans_push_2(3)
by (metis state.disc(1,3) LTS_ε.trans_star_not_to_source_ε (Isolated p' γ [γ''], q1) ∈ LTS_ε A' ∧
have "∄, Isolated p' γ, q)"
by a<>Isolated A'›
then show ?thesis
using nin add_I_2( \open(Init p', Some γ', Isolated p' γ') ∈ A'›(Isolated p' γ', Some γ'', q1) ∈ push LTS_ε.append_edge_edgetrasa_<>y
qed
post_star_rules_Isolate le:
assumespststarr_rules<^\<
assumes "isols ⊆
assumes "(Init p', Some γ', Isolated p' γ') ∉
shows "Isolated p' γ ) in>LT.path_with_word A"
by (meson LTS.srcs_def2 assms(1) assms(2) assms(3) post_star_rules_Isolated_source_invariantassits\> LTS.srcs A"
lated_sink_invariant
_rus\sup>* A A'"
assumes "isols ⊆
assumes "(Init p', Some γ
shows "∄.(Isoltedp <>'
using assms
(induction rsho "q \>inits"
case base
then show ?case
unfolding isols_def is_Isolated_def
isolated_no_edgestd_no_edgsb atoc
case (step Aiminus1 Ai)
from step(2) show ?case
proof (cases rule: post_star_rules.cases)
case (add_trans_pop p''' γ
then have "(Init p', Some γ')not> Ai"
using step.prems(2) by blast
then have nin: "∄p γ. (Isolated p' γ', γ, p) ∈ Aiminus1"
using local.add_trans_pop(1) step.IH step.prems(1,2) by fastforce
then have "Isolated p' γ' ≠ q'. (q, γ Ai"
using add_trans_pop(4)
LTS_ε.trans_star_not_to_source_ε[of "Init p'''" "[γ: rtralp_induct)
post_star_rules_Isolated_source_invariant local.add_trans_pop(1) step.hyps(1) step.prems(1,2)
UnI1 local.add_trans_pop(3) by (metis (full_types) state.distinct(3))
then have "∄
by auto
then show ?thesis
using nin add_trans_pop(1) by auto
next
case (add_trans_swap p'''' γ'' p'' γ''' q)
then have "(Init p', Some γ', Isolated p' γ') ∉
using step.prems(2) by blast
then have nin: "∄p γcaseadd_transns_p_pop p γ
local.add_trans_swap(1) step.IH step.prems(1,2) by fastforce
then have "Isolated p' γ' ≠ q"
ma>'']" q Aiius1
local.add_trans_swap(3) post_star_rules_Isolated_source_invariant[of _ Aiminus1 p' γ'] UnCI
local.add_trans_swap(1) step.hyps(1) step.prems(1,2) state.simps(7) by metis
then have "∄qq. q = Init qq"
by auto
then ssis
using nin add_trans_swap(1) by auto
next
case (add_trans_push_1 p'''' γ'' p'' γ''' γ'usi d locladd_trans_pop(1)by utojava.lang.StringIndexOutOfBoundsException: Index 46 out of bounds for length 46
then have "(Init p', Some γ', Isolated p' γ inits"
using step.prems(2) by blast
then show ?thesis
ing g add_trasps_(1) U_iff stt.net rdinect stsingleton_n_iff stepIH
step.prems(1,2) by blast
next
case (add_trans_push_2 p'''' γ'' p'' γ''' γthen ha"∄ = Initqq"
have "(Init p', Some γ', Isolated p' γ
using step.prems(2) by blast
then have nin: "∄ p' γ'' q)
using local.add_trans_push_2(1) step.IH step.prems(1,2) by fastforce
then have "Isolated p' γ' ≠ inits"
using state.disc(3)
Isolated ' γ"]
local.add_trans_push_2(3)
using post_star_rules_Isolated_source_invariant[of _ Aiminus1 p' γ'] UnCI
local.add_trans_push_2(1) step.hyps(1) step.prems(1,2) state.disc(1) by metis
then have "∄
auto
then show ?thesis
using nin add_trans_push_2(1)
using al.atrans_ush_2 step.pems((2)b uo
qed
assumes "(Init p', Some γ
java.lang.NullPointerException
by (meson LTS.sinks_def2 assms(1,2,3) post_star_rules_Isolated_sink_invariant')
―
rtranclp_post_star_rules_constains_successors_states:
assumes "post_star_rulesLTS.sinks A"
assumes "inits \<> by (mmetis.srcs_def LTS.s_d2 asms(1) ssm( nmn)
assumes "isols ⊆
java.lang.NullPointerException
shows "(¬is_Isolated q ⟶ (∃', q) \in LTS_ε.trans_star_ε A ∧ (p',w') ==>* (p, LTS_ε.remove_ε ∧
(is_Isolated q ⟶∄p γ, Isolated p' γ A'"
using assms
(induction arbitrary: p q w ss rule: rtranclp_indutorl: trancl_inct
case base
{
ssume ctr__lo "is_Init q \<or q"
then have "(Init p, LTS_ε<> .trans_star_ε
using base LTS_ε.trans_star_states_trans_star_ε by metis
then have "∃
by auto
then have ?case
using ctr_loc ‹ A›
}
moreover
{
assume "is_Isolated q"
then have ?case
proof (cases w)
case Nil
then have False using base
using LTS.trans_star_empty LTS.trans_star_sttes_trans_sar \ <>is_Isolated
y (meate.disc(7))
thenhen show ?thess
by metis
next
then have "(Init p, γ#w_rest, ss, q) ∈'' p'' γ
using base Cons by blast
then have "∃s γprs(2) blast
using LTS.trans_star_states_transition_relation by metis
then have False
using ‹
by (metis mem_Collect_eq _\epsilon.trans_sε local.add_trans_swap(3))
then show ?thesis
auto
qed auto
}
ultimately
show ?case
by (mesonateehaus_ic
case (step Aiminus1 Ai)
from step(2) have "∃rd.injectngeo_ff sepp.IH
by (cases rule: post_star_rules.cases) auto
then obtain p1 γ'' p'' γ'''' q)
"Ai = Aiminus1 ∪') Ai"
"(p1, γ, q1)ep.pr2).
by auto
define t where "t = (p1, γ, q1)"
define j where "j = count (transitions_of' (Init p, w, ss, q)) t"
note s_p = step(6)
from j_def ss_p show ?case
proof (induction j arbitrary: p q w ss)
case 0
then have "(Init p, w, ss, q) ∈ LTS.trans_star_states Aiminus1"
using count_zero_remove_path_with_word_trans_star_states p1_γ
by metis
then show ?case
using step by auto
next
case (Suc j)
from step(2) show ?case
proof (cases rule: post_star_rules.cases)
case (add_trans_pop p2 \<gamma>2 p1 q1) (* Note: p1 shadows p1 from above. q1 shadows q1 from above. *) note III = add_trans_pop(3) note VI = add_trans_pop(2) have t_def: "t = (Init p1, ε, q1)" usinglocal.add_trans_pop(1) local.add_trans_pop p1_γ_p2_w2_q'_p(1) t_def by blast have init_Ai: "inits ⊆(me LTS.rcs_def2asms(1 assms(2) assms(3) post_star_rules_Isolated_source_invariant') ng sep(1,2) step() using no_edge_to_Ctr_Loc_post_star_rules using r_into_rtranclp by (metis) have t_hd_once: "hd (transition_list (ss, w) t🪙 proof have"(ss, w) ∈p γ. (Isolated p' γ, p) \<in using Suc(3) LTS.trans_star_states_path_with_word by metis moreover have "caseinus1 using init_Aiproofle_es moreover "0 < count (transitions_of (ss, w)) t" by (metis Suclast moreover have it\>
singjava.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 29 moreover have"Init p1 ∈p γ\gamma Isolated p' γ') = (Init p'', ε, q)" by (simp ultimately show"hd (transition_list (ss, w)) (ad_rns_swp p'' gamm'' p'' ga>''' q) using init_only_hd[of ss w Ai t p1 ε q1] by auto qed
have "transition_list (ss, w) ≠ []" by (metis LTS.trans_star_states_path_with_word LTS.path_with_word.simps Suc.prems(1) Suc.prems(2) count_empty less_not_refl2 list.distinct(1) transition_list.simps(1) transitions_of'.simps transitions_of.simps(2) zero_less_Suc) then have ss_w_split: "([Init p1,q1], [ε]) @🍋 (tl ss, tl w) = (ss, w)" using t_hd_once t_def hd_transition_list_append_path_with_word by metis then have ss_w_split': "(Init p1, [ε], [Init p1,q1], q1) @@🍋 (q1, tl w, tl ss, q) = (Init p1, w, ss, q)" by auto have VII: "p = p1" proof - have "(Init p, w, ss, q) ∈ LTS.trans_star_states Ai" using Suc.prems(2) by blast moreover have "t = hd (transition_list(Init p, w s,q)java.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 59 using <open>hd (transition_list (ss, w)) = t ∧ count (transitions_of (ss, w)) t 1 by fastforce moreover have"transition_list' (Init p, w, ss, q) ≠p γ, Isolated p' γ''', q)" by (simp add moreover have"t = (Init p1, ε_1 p'''' amma'' p'' γ''' γ''''' q) using t_def by auto ultimately show "p = p1" using LTS.hd_is_hd by fastforce qed have "j=0" using Suc(2) ‹ by force have " Init p1, [ε LTS.trans_star_states Ai"
proof -
have "(Init p1, ε
using local.add_trans_pop(1) by auto
moreover
have "(Init p1, εthenha"sola p'\gamma≠ q"
by (simp add: local.add_trans_pop)
ultimately
show "(Init p1, [ε], [Init p1, q1], q1) _ Aiiu1p' \>'] UnCI
by (meson LTS.trans_star_states.trans_star_states_refl
LTS.trans_star_states.trans_star_states_step)
qed
have "(q1, tl w, tl ss, q) ∈
proof -
from Suc(3) have "(ss, w) ∈
by (meson LTS.trans_star_states_path_with_word)
then have tl_ss_w_Ai: "(tl ss, tl w
java.lang.NullPointerException
transition_list.simps(2))
from t_hd_once have zero_p1_epsilon>q1: "0 count traitions_of (tl s, t w)) (ntp <psilon,
using count_append_path_with_word_γ[of "[hd ss]" "[]" "tl ss" "hd w" "tl w" "Init p1" ε q1, simplified]
java.lang.NullPointerException \>ttransition_list (ss, w) ≠ Suc.prems(2) VII
LTS.transition_list_Cons[of "Init p" w ss q Ai ε q1] by (auto simp: t_def)
have Ai_Aiminus1: "Ai = Aiminus1 ∪, q1)}"
using local.add_trans_pop(1) by auto
from t_hd_once tl_ss_w_Ai zero_p1_ε_q1 Ai_Aiminus1
count_zero_remove_path_with_word[OF tl_ss_w_Ai, of "Init p1" εinuus]
have "(tl,tl ) \in LTS.path_with_word Aiminus1"
moreover
have "hd (tl ss) = q1"
using Suc.prems(2) VII ‹ is_Noninit q"
TS.trratin_list_Cn _hd_oce yfstfce
moreover
have "last ss = q"
by metis LTS T.trans_star_states_stSuc.pre(2)
ultimately
show "(q1, tl w, tl ss, q) ∈(Init p, LTS_ε.remove_ε w, q) ∈ LTS_ε.trans_star_ε by blast
by (metis (no_types, lifting) LTS.trans_star_states_path_with_word
LTS.path_with_word_trans_star_states LTS.path_with_word_not_empty Suc.prems(2)
last_ConsR list.collapse)
qed
have "w ε # (tl w)"
by (metis Suc(3) VII ‹
list.sel(1) t_def LTS.transition_list_Cons t_hd_once)
then have w_tl_ε: "LTS_\epsilon.remove_εS_e>.remove_ε (tl w)"
by (metis LTS_ε.remove_ε_def removeAll.simps(2))
have "∃γ2'. LTS_ε.ε_exp γ2' [γ2] ∧ (Init p2, γ2', q1) ∈ LTS.trans_star Aiminus1"
using add_trans_pop
by (sy (simm d:LT<>.
then obtain γ
by blast
then have "∃ LTS.trans_star_states A"
by (simp addr_srtas_sta
then obtain ss2 where<>is_Isolated
by blast
have IIII_2: "(q1, tl wby uto
using ss_w_split' Suc(3) Suc(2) ‹
using ‹
have IIII: "(Init p2, γ2' l w, s @ (tl (tll ss))) ∈ LTS.trs_starr_states Aiminus1"
using IIII_1 IIII_2 by (meson LTS.trans_star_states_append)
""¬ is_Isolated q"
using state.exhaust_disc by blast
then show ?thesis
proof
assume ctr_q: "¬
then have "∃p' w'. (Init p', w', q) ∈
using V by auto
ar_rulesr.css
VIII:"(Init p', w', q) ∈ = add_trans_pop(3)
by blast
hen haae"p,') \<><2' @ tl w)\nd
(p2, LTS_ε.d_trans_pop(1p2_w2_q'_p(1) t_def by blast
proof -
have γ2'_γLTS_\epsilon>.remove_ε γ2' = [γ2]"
by (metis LTS_ε.ε_exp_def LTS_ε.remove_εp(4
have"(p',w'\^sup>* (p2, LTS_ε.remove_\epsilon> (γ))"
using steps by auto
moreover
ave re: "(p2, \ γ (p, pop)"
using VI VII by auto
from steps have steps': "(p', w') ==>.pt_ih_word Ai"
using γ) LTSLTLTS.trans_star_states_path_with_word by metis
by (metis Cons_eq_appendI LTS_ε.remove_ε
from rule steps' have "(p2, γ2 # (LTS_ε (tl w))) ==>* (p, LTS_ε.remove_ε
using VIII
by (metis PDS.transition_rel.intros append_self_conv2 lbl.simps(1) r_into_rtranclp
step_relp_def) (* VII *) thenmetis Suc.prems(1) transitions_of zero_less_Suc by (simp add: LTS_ε.remove_<epsilon , q1)" ultimately show "(p',w') ==>∈
(p2 ((ss and count (transitions_of,) t " by auto qed then have "(p',w') ==>* (p, LTS_ε.remove_ε (tl w)) ∧using[of w Ai ε
yorce thenbymetisrans_star_states_path_with_wordath_with_wordith_word using w_tl_ε by auto thenshow ?then_:([nit p1q1<epsilon<cute using ctr_q ‹p = p1›, ε ,q1,q1@@acute, tl, tl, q = ( p1 ss" next assume proof - from V have "(the_Ctr_Loc q, [the_Label Suc( java.lang.StringIndexOutOfBoundsException: Index 37 out of bounds for length 37 by (metis LTS_ε_exp_defεepsilonappend_dist LTS_ε.remove_ε_def ‹LTS_ε.ε_exp by fasfastforc
append_Cons append_self_conv2 w_tl_ε)
then have "(the_Ctr_Loc q, [the_Label q]) ==>* (p1, LTS_εby (p dd:: \>rasiton_list (ss w) \noteq []› using VI ( append_Nil lbl.simps(1) rtranclp.simps step_relp_def2) thenhave"(the_Ctr_Loc q, [the_Label q]) ==> by auto using VII by auto then show ?thesis using ‹ qed next (add_trans_swap p2 γ2 p1 γ' q1) (* Adjusted from previous case *) note III = add_trans_swap(3) note VI = add_trans_swap(2) have t_def: " = (Init p1, Some γ', q1)"
using local.add_trans_swap(1) local.add_trans_swap p1_γ_p2_w2_q'_p(1) t_def by blast
have ihave"(Init p1, ε) ∈
using step(1,2,4) no_edge_to_Ctr_Loc_post_star_rules by (meson r_into_rtranclp)
have t_hd_once: "hd (transition_list (ss, w)) = t ∧ count (tranh "(Init p1 εno> A"
proof -
have "(ss, w) ∈
using c() LTS.trns_starr_state_pat_with_wr bymts
moreover
have "inits ⊆
using init_Ai by auto
moreover
have "0 < count
by (metis Suc.prems(1) transitions_of'.simps zero_
moreover
have "t = (Init p1, Some γ', q1)"
using t_def
by auto
moreover
have "Init p1 ∈
using inits_def by force
ultimately
show "hd (transition_list (ss, w)) = t ∧) t = 1"
using init_only_hd[of ss w Ai t p1 ransiinlisst.imp(2))
java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
have "transition_list (ss, w) \noteq
by (metis LTS.trans_star_states_path_with_word LTS.path_with_word.simps Suc.prems(1,2)
count_empty less_not_refl2 list.distinct(1) transition_list.simps(1) transitions_of'.simps
transitions_of.simps(2) zero_less_Suc)
then have ss_w_split: "([Init p1,1,[ome \gamma']) @🍋
using t_hd_once t_def hd_transition_list_append_path_with_word by metis
then have ss_w_split': "(Init p1, [Some γ'], [Init p1,q1], q1) @@🍋_q1 Ai_Aiminus11
by auto
have VII: "p = p1"
have "(Init p, w, ss, q) ∈
using Suc.prems(2) by blast
oreover
have "t = hd (transition_list' (Init p, w, ss, q))"
using ‹hd (transition_list (ss, w)) = t ∧ count (transitions_of (ss, w)) t = 1›by fastforce
moreover
have "transition_list' (Init p, w, ss, q) ≠ []"
by (simp add: ‹transition_list (ss, w) ≠ []›)
moreover
have "t = (Init p1, Some γ', q1)"
using t_def by auto
ultimately
show "p = p1"
using LTS.hd_is_hd by fastforce
qed
have "j=0"
using Suc(2) ‹hd (transition_list (ss, w)) = t ∧ count (transitions_of (ss, w)) t = 1› by force
have "(Init p1, [Some γ'], [Init p1, q1], q1) ∈ LTS.trans_star_states Ai"
proof -
have "(Init p1, Some γ', q1) ∈ Ai"
using local.add_trans_swap(1) by auto
moreover
have "(Init p1, Some γ', q1) ∉ Aiminus1"
using local.add_trans_swap(4) by blast
mately
show "(Init p1, [Some γ'], [Init p1, q1], q1) ∈
by (meson LTS.trans_star_states.trans_star_ ave "last ss q
qed
ve q, tl w, tl ss, q) ∈
proof -
from Suc(3) have "(ss, w) ∈ LTS.path_with_word Ai"
by (meson LTS.trans_star_states_path_with_word)
then have tl_ss_w_Ai: "(tl ss, tl w) ∈
by (metis LTS.path_with_word.simps ‹
from t_hd_once have zero_p1_ε_q1: "0 = count (transitions_of ast_onltops)
using count_append_path_with_word_γ[of "[hd ss]" "[]" "tl ss" "hd w" "tl w" "Init p1" "Some γ'" q1, simplified] ‹transition_list (ss, w) ≠>list.distinct(1) list.exhaust_sel
Suc.prems(2) VII LTS.transitithen haewt_<>:
by (auto simp: t_def)
have Ai_Aiminus1: "Ai = Aiminus1 ∪
ingocalad_trn_ssap(1) by uto
from t_hd_once tl_ss_w_Ai zero_p1_ε
count_zero_remove_path_with_word[O tls_wA,of"Initp1"_
have "(tl ss, tl w) ∈ LTS.path_with_word Aiminus1"
by auto
moreover
have "hd (tl ss) = q1"
using Suc.prems(2) VII ‹t_def LTS.transition_list_Cons t_hd_once by fastforce
moreover
have "last ss = q"
by (metis LTS.trans_star_states_last Suc.prems(2))
ultimately
show "(q1, tl w, tl ss, q) ∈ LTS.trans_star_states Aiminus1"
by (metis (no_types, lifting) LTS.trans_star_states_path_with_word
TS.athwth_wr_ra_starstaes TSpath_ithword_ot_pt Succ.pem(2
last_ConsR list.collapse)
qed
e w = Som γ# (tl w)"
by (metis Suc(3) VII ‹ lst.distict1 list.exhust_stsl
list.sel(1) t_def LTS.transition_list_Cons t_hd_once)
ε: "LTS_ε
usingT\epsilonove_\epsilonfrmoeAlsms2
by presburger
have "∃γ
add_trans_swap by (simp add: LTS_εε_exp_trans_star)
java.lang.StringIndexOutOfBoundsException: Index 53 out of bounds for length 53
by blast
then have "∃ss2. (Init p2, γ2', ss2, q1) ∈ (the_Ctr_Loc q, [the_Label ]<>\
by (simp add: LTS.trans_star_trans_star_states)
then obtain ss2 where IIII_1: "(Init p2, γ2', ss2, q1) ∈ LTS.trans_star_states Aiminus1"
by blast
have IIII_2: "(q1, tl w, tl ss, q) ∈IIII
using ss_w_split' Suc(3) Suc(2) ‹.prems(1,,3) by blast
using ‹
have IIII: "(Init p2, γ2' @ tl w, ss2 @ (tl (tl ss)), q) ∈
using IIII_1 IIII_2 by (meson LTS.trans_star_states_append)
from Suc(1)[of p2 "γ ?thesis
have V: "(¬is_Isolated q ⟶
(∃p' w'. (Init p', w', q) ∈ LTS_ε.trans_star_ε A ∧ (p', w') ==>
(is_Isolated q ⟶ (the_Ctr_Loc q, [the_Label q]) ==>"∃', q) <> A 🪙* (p2, LTS_ε.remove_ε2' @ tl w))"
using IIII
using step.IH step.prems(1,2,3) by blast
have "¬(Init p', w', q) ∈.trans_star_εd ses: "(p', w') \Rightarrow\<>* w))"
using state.exhaust_disc by y blast
then show ?thesis
proof
assume ctr_q: "¬is_Isolated q"
hen hae "\exists' w. (nit ',w', q \in> TSS_\epsilon>.trans__ε (p', w') ==>.eove\<psilon 🚫
then obtain p' w' where
VIII:"(Init p', w', q)∈.trans_star_🚫 A" and steps: "(p', w') ==>* (p2, LTS_εepsilon> (γ2' @ tl w))"
by blast
then have "(p "(p',w') ==>* (p2, LTS_ε.remove_ε (γ2' @ tl w)) ∧
(p2, LTS_ε.remove_ε (γusing steps steps by auto
proof -
have γ2'_γ2: "LTS_ε.remove_ε rule: "(p, γ (p, pop)"
by (metis LTS_ε.εusing VI V VII by auto
have "(p',w') ==>* (p2, LTS_ε.remove_ε2' @ tl w))"
using steps by auto
moreover
have rule: "(p2, γ2) ↪ Cons_eq_appendI LTS_\\ε>_append_dist self_append_conv2)
using VI VII by auto
from step hae step':"p', w' \ightarrow>> (tl w)))"
using γ2'_γ2
by (metis Cons_eq_appendI LTS_ε.remove_ε
from rule steps' have "(p2, γ2 # (LTS_εby (metisPDStrnsiton_el.itros appndsef_onv2 lblsimp(1) _itortranl
using VIII
using PDS.transition_rel.intros append_self_conv2 lbl.simps(1) r_into_rtranclp step_relp_def
by fastforce
then have "(p2, LTS_ε (γ2' @ tl w)) ==>* (p, γ' # LTS_ε (tl w))"
"('w) \Rightarrow.remove_ε (γ2' @ tl w)) ∧
ultimately
show (p',w') ==>* (p2, LTS_ε.remove_ε (γ2' @ tl w)) ∧
(p2, LTS_ε.remove_ε (γ2' @ tl w)) ==>* (p, γ' # LTS_ε.remove_ε (tl w))"
by auto
qed
then have "(p',w') ==>have "(p',w') ==>* (p, LTS_ε.remove_ε (tl w)) ∧ (Init p', w', q) ∈ LTS_ε.trans_star_\epsilon> A""
VIII by force
then have "∃w_tl_ε
using LTS_ε.remove_ε_Cons_tl by (metis ‹
then show ?thesis
using ctr ‹ b blast
next
assume "is_Isolated q"
from V this have "(the_Ctr_Loc q, [the_Label q]) ==>V h"(the_C q, [the_Label q]) ==>* (p2, γ2(LTS_\epsilon>remε
to
then have "(the_Ctr_Loc q, [the_Label q]) ==>\ ‹ (Init p2, γ', 1 ∈‹
by (metis LTS_ε.ε_exp_def LTS_ε.remove_ε_append_dist LTS_εapen_sefconv2 w_tlε ‹
append_self_conv2)
then have "(the_Ctr_Loc q, [the_Label q]) ==>VI by (metis append_Nil lbl.simps(1) rtranclp.simps step_relp_def2))
using VI
by (metis (no_types) append_Cons append_Nil lbl.simps(2) rtranclp.rtrancl_into_rtrancl
step_relp_def2)
then have "(the_Ctr_Loc q, [the_Label q]) ==>* (p, γ show ?thesis
using VII by auto
then show ?thesis
using ‹
by (metis LTS_ε.remove_ε_Cons_tl w_tl_ε)
qed
next
case (add_trans_push_1 p2 γ2 p1 γ1 γ'' q1')
then have t_def: "t = (Init p1, Some γ1, Isolated p1 γht_def: "t = (Ini p1, Some γ
using local.add_trans_pop(1) local.add_trans_pop p1_γ<>LTS
have init_Ai: "inits ⊆ (transition_list (ss, w)) = t ∧, w)) t = 11
proof - -
using no_edge_to_Ctr_Loc_post_star_rules
by (meson r_into_rtranclp)
have t_hd_once: "hd (transition_list (ss, w)) = t ∧ Suc(3) LTS.t.trans_sta by metis
moreover
have "(ss LTS.srcs Ai"
using Suc(3) LTS.trans_star_states_path_with_word by metis
moreover
have "inits ⊆
using init_Ai by auto
moreover
have "0 < counttransitions_of'.simps zero_less_Suc)
by (metis Suc.prems(1) moreover
moreover
have "t = (Init p1, Some γ1, Isolated p1 γ1)"
using t_ by auto
moreover
have "Init p1 ∈
using inits_def by fastforce
ultimately
how"d (transition (ss, w)) = t ∧
using init_only_hd[of ss w Ai t] by auto
qed
s "hd (transition (ss, w)) = \and on trnii ) t=1"
by (metis LTS.trans_star_states_path_with_word LTS.path_with_word.simps Suc.prems(1
count_empty less_not_refl2 list.distinct(1) transition_list.simps(1)
transitions_of' ave "t "trastin_is(ss,w)\<oteq
have V "p = p1"
proof -
have "(Init p, w hen have ss_w_: "([Init p1,q1], [Some 🚫
using Suc.prems(2) by blast
java.lang.StringIndexOutOfBoundsException: Index 53 out of bounds for length 16
have "t = hd (transition_list' (Init p, w, ss, q))"
using ‹hd (transition_list (ss, w)) = t ∧ count (transitions_of (ss, w)) t = 1›by fastforce
moreover
have "transition_list' (Init p, w, ss, q) ≠ []"
by (simp add: ‹transition_list (ss, w) ≠ have VII: "p = p1"
moreover
have "t = (Init p1, Some γ1, Isolated p1 γ1)"
using t_def by auto
ultimately
show "p = p1"
using LTS.hd_is_hd by fastforce
qed
from add_trans_push_1(4) have "∄nlis'(Int p, w, ss ))
using post_star_rules_Isolated_sink_invariant[of A Aiminus1 p1 γ1] step.hyps(1)
step.prems(1,2,3) unfolding LTS.sinks_def by blast
then have "∄p γ. (Isolated p pγ, p) ∈
using local.add_trans_push_1(1) by b oreover
enhves_w_sot ss = itp1Isoatedp1<>1
using Suc.prems(2) VII ‹ count (transitions_of (ss, w)) t = 1›
Snthinafter_sik "it p1" "Islte p1 🚫" "tl (tl ss)" "Some γ1" "tl w" Ai] ‹ []›
LTS.trans_star_states_path_with_word[of "Init p" w ss q Ai]
LTS.transition_list_Cons[of "Init p" w ss q Ai]
by (auto simp: LTS.sinks_def2)
then have q_ext: "q = Isolated p1 γ1"
using LTS.trans_star_states_last Suc.prems(2) by fastforce
have "(p1, [γ1]) ==>LTS.trans_star_states Ai"
using ss_w_short unfolding LTS_ε
using VII by force
using locl.d_rsswp(1) yat
by (simp add: ‹ Aiminus1"
then show ?thesis
using q_ext by auto
next
case (add_trans_push_2 p2 \<gamma>2 p1 \<gamma>1 \<gamma>'' q') (* Adjusted from previous case *) note LTS.trans_star_states Aiminus1 note XIII = add_trans_push_2(2) have t_def: "t = (Isolated p1 γ1, Some γatithor) using local.add_trans_push_2(1,4) p1_γ_p2_w2_q'_p(1) t_def by blast have init_Ai: "inits using step(1,2) step(4) using no_edge_to_Ctr_Loc_post_star_rules
(eson
from Suc(2,3) split_at_first_t[of "Init ""olatedaep <" <>'" q' Aiminus1] t_def have "∃uby
@>
w = u @ [Some γ''] @ v ∧
(Init\epsilon>_ _Aiminus1
e🚫_ss, )<> LTSAi usinglocal.add_trans_push_2 have"(tl ss, tl w) ∈" thenobtain u v u_ss v_ss where
:s s@ss
w_split: "w = u @ [Some γ''] @ v"and byetisSucems
out_trans: "(Isolated p1 γ1, [Some γ''], q') ∈ tl w, tl ss, q) ∈ path LTS.path_with_word_trans_star_states LT.ath_ih_wor_o_empt u.rem() auto from step(3)[of p u u_ss "Isolated p1 γ1"]have "Some' # (tl w)" "(¬is_Isolated (Isolated p1 γ1) ⟶
(∃p' w'. (Init p', w', Isolated p1 γ1) thenhaveε>.remove_ε w = LTS_>.remove_ε<gamma'#tl )
(Isolated1) ⟶
(the_Ctr_Loc (olated1), [the_Labellated1)]) ==>* (p, LTS_ε.remove_ε using step uto then (Ctr_Loc<gammahe_Labelgamma1)]) ==>* (p, LTS_ε.remove_ε by auto thenhave p1_γ1_p_u: "(p1, [γ1]) ==>2', ss2, q1) ∈s1" by auto from IXe\exists><amma2ε γ2ss. LTS_ε.ε_exp γ2ε [γ2] ∧ (Init p2, γ2ε, γ2ss <in_tar_states by (meson LTS.trans_star_trans_star_statesusing ss_w_splitucj=0› thentain>ε γepsilonε_exp γ2ε [γ2] ∧ (Init p2, <gamma,2ss, q') <> LTSates by blast have"(q', v, v_ss, q) ∈starstaesi" using path .
ed "(¬ (is_Isolated q ⟶ (the_Ctr_(from Suc()[f p2<>2' @ tl ""ss2 @ (tl (tl ss))" qjava.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 67 proof - have γ2ss_len: "length γ2ss = Suc (length γ (the_Ctr_Loc q, [the_Label q]) ==>* (p2, LTS_ε.remove_ε (γ2' @ tl w)))" by (meson LTS.trans_star_states_length XI_1)
haveusing IIII by (metis LTS.trans_star_states.simps path list.distinct(1))
have γt_disc by (metis LTS.trans_star_states_hd LTS
aveansitions_ofv " proof - have last_u_ss: "Isolated p1 γ1 = last u_ss" rans_star_states_lasttar_states_lastX1 have q'_hd_v_sVIII:"nit LTS_ε.trans_star_ε pw <Rightarrow> (p2, LTS_ε.remove_ε (γ by (meson LTS by blast
have"count (transitions_of' (((Init p, u, u_ss, Isolated p1 γ1), Some γ.remove_ε2' @ tl w)) ==>* (p, γ' # LTS_ε.remove_ε"
(Isolated p1 γ1, Some γ2'_γ2: "TS_<>.remove_\epsilon γ2' = [γ2]"
count (transitions_of' (Init p, u, u_ss bymetisTS_.εdef<>.move__def‹ (Init p2, γ2', q1) ∈) (ifIsolatedp1\<gamma>1=lastu_ss\<andhave"'<ightarrow\<^sup>*(p2,LTS_\<epsilon>.remove_\<epsilon>(\<gamma>2'@tlw))" count(transitions_of'(q',v,v_ss,)olatedtedp1<>1,Some\<gamma>'',q'" usingcount_append_trans_star_states_\<gammalengthfsu_Initsolated<amma>""Some\<gamma>''"q'vq"Isolatedp1\<gamma>1""Some\<gamma>''"q']t_defss_splitw_splitX_1 bySans_star_states_lengthstar_states_lengthr_states_lengthtates_lengthes_lengths_lengthss_empty thenhave"count(transitions_of(u_ss@v_ss,u@Some\<gamma>''#v))(lastusingVIIIbyforce
thenhave"j=count(transitions_of'((q',v,v_ss,q)))t" usinglast_u_ssq'_hd_v_ssX_1ss_splitw_splitadd_trans_push_2(4)Suc(2) LTS.avoid_count_zero[of"Initp"uu_ss"Isolatedp1\<gamma>1"Aiminus1"Isolatedp1\<gamma>1""Some\<gamma>''"q'] by(autosimp:t_def) thenshow"j=count(transitions_of((v_ss,v)))t" byforce qed havep2_q'_states_Aiminus1:"(Initp2,\<gamma>2<2ss,q')\<in>LTS.trans_star_statesjava.lang.StringIndexOutOfBoundsException: Index 122 out of bounds for length 122 usingXI_1byblast engamma2:"count(transitions_of2ss,\<gamma>2<>))=" usingLTS.l__)ocal_ans_pop<>_p2_w2_q1_eflast havetransitions_ofgamma2ss,\<gamma>2\<epsilon>)@\<acute>_) usingLTS.count_append_path_with_word[of\<gamma>2ss\<gamma>2\<epsilon>v_ssv"Isolated()<in>LTSh_with_word_wordjava.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 50 chave"=Init<>1,olatedgamma1)" byforce thenhavej_count:"j=count byqed
have"gamma2,\<gamma>2\<epsilon>)\<in>LTS.path_with_wordAiminus1" by(mesonLTS.trans_star_states_path_with_wordp2_q'_states_Aiminus1) thenhave\<gamma>2ss_path:"(\<gamma>2ss,\<gamma>2\<epsilon>)\<in>LTS.path_with_wordhavehdion_listss using path_with_word_mono'[of\<gamma>2ss
have"(Initp2,\<gamma>2\<epsilon>yjava.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 27 typesgLTSth_with_word_trans_star_states LTS.trans_star_states_appendLTS.trans_star_states_hdXI_1path\<gamma>2ss_path\<gamma>2ss_last) bymesonr_into_rtranclp show "(\<not>is_Isolatedq\<longrightarrow>(\<exists>p'w'.(Initp',w',q)\<in>LTS_\<epsilon>.trans_star_\<epsilon>A\<and>(p',w')\<Rightarrow>\<^sup>*(p2,LTS_\<epsilonhaveexistsuvu_ssv_ss. (the_Ctr_Locq,[[q])\<Rightarrow>\<sup*(,LTS_\epsilonremove_(\<gamma>2\<epsilonv) usingj_countbyfastforce qed
show?thesis proof(cases"is_Init<is_Noninitq") True (exists'witq<>TS_epsilon.trans_star_\<epsilon>A\<dp\<^sup>*(p2,LTS_.remove_\<epsilon>(\<gamma>@v)))" usingTrueindbyfastforce obtainp'w'where'_'_p('q<>LTS_\<epsilon>._r_<epsilon<>\<^sup>*(p2_><>(\<gamma>2\<epsilon>@v))" byauto thenhave"(p',w')\<Rightarrow>\<^sup>*(p2,LTS_\<epsilon>.remove_\<epsilon>(\<gamma>2\<epsilon>@v))" byauto havep2_\<gamma>2\<epsilon>v_p1_\<gamma(solated1,Some\<gamma>'',q')= proof- have"\<gamma>2#(LTS_\<epsilon>.remove_\<epsilon>v)=LTS_\<epsilon>.remove_\<epsilon>(\<gamma>2\<epsilon>@v)" usingXI_1 by(metisLTS_\<epsilon>.\<epsilon>_exp_defLTS_\<epsilon>.remove_\<epsilon>_append_distLTS_\<epsilon>.remove_\<epsilon>_.avoid_count_zero[fInitpuu_ss"Isolated\<>11Isolatedp1\gamma""\<gamma'"java.lang.StringIndexOutOfBoundsException: Index 132 out of bounds for length 132 self_append_conv2) moreover fromXIIIhave"(p2,\<>\>remove_v))\<Rightarrow^sup*(p1,\<gamma>1#\<gamma>''#LTS_<epsilone_epsilon" by(metisPDS.transition_rel.introsappend_Consappend_Nillbl.simps(3)r_into_rtranclp ultimately show"(p2,LTS_\<epsilon>.remove_\<epsilon>(\<gamma>2\<epsilon>@v))\<Rightarrow>\< byauto qed have\<gamma>\<>''v_p_uv(,\gamma#<>'S_<silonove_>)Rightarrow\<^sup>*(p,(S_>.remove_\<epsilon>u)(''#LTS_\<epsilon>.remove_\<epsilon>v) bymetisp1_\<gamma>1_p_uappend_Consappend_Nilstep_relp_append have"(LTS_epsilon>.remove_\<epsilon>u)@(\<gamma>''#LTS_\<epsilon>.remove_\<epsilon>v))=(_.remove_\<epsilon>)java.lang.StringIndexOutOfBoundsException: Index 148 out of bounds for length 148 by(metis(no_types,lifting)Cons_eq_append_convLTS_\<epsilonby(etisLTS_\<>.<>_LTS_\<epsilon.\<epsilon>_append_dist\<epsilon>\<epsilon LTS_\<epsilon>.remove_\<epsilon>_append_distw_splithd_Cons_tllist.injectlist.sel(1)list.simps(3) self_append_conv2) show?thesis Truep1_\<gamma>1\<gamma>''v_p_uvp2_\<gamma>2\<epsilon>v_p1_\<gamma>1_\<gamma>''_vp'_w'_pbyfastforce next caseFalse thenhaveq_nlq_p2_\<gamma>2\<epsilon>v:"(the_Ctr_Locq,[the_Labelq])\<Rightarrow>\<^sup>*(byblast usingindstate.exhaust_disc byjava.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18 <\<epsilon>v_p1_<gamma>\gamma>,\<epsilon>.remove_\<epsilon\>2\epsilon>)<>\<^sup*p1,\<\>.epsilonv)" by((mono_tags)\<epsilon_exp_defLTS_epsilon.remove_\<epsilon>_append_dist\<epsilon>.remove_\<epsilon>_defXIII XI_1append_Consappend_Nillbl.simps(step_relp_def2) havep1_\<gamma>1\<gamma>''_v_p_u\<gamma>'1#\<gamma>''#TS_epsilon>.remove_\<epsilon>v\Rightarrow\<^sup>*(p,LTS_\<epsilonove_>u@\<gamma'_epsilon.remove_\<epsilon>v) by(metisp1_\<gamma>1_lemmapost_star_rules_saturation_constains_successors: "(p,LTS_\<epsilon>.remove_\<epsilon>u@\<gamma>''#LTS_\<epsilon>.remove_\<epsilon>v)=(p,LTS_\<epsilon>.remove_\<epsilon>w)" (metisLTS_\epsilon>.remove_\<epsilon>_Cons_tlLTS_\<epsilonremove_\<epsilon>append_distappend_Consappend_Nilw_split hd_Cons_tllist.distinct(1)list.inject) thenshow?thesis usingFalsep1_\<gamma>1\<gamma>''_v_p_u\<gamma>''vp2_\<gamma>2\<epsilon>v_p1_\<gamma>1\<gamma>''vq_nlq_p2_\<gamma>2\<epsilon>v by(metis(no_types,lifting)indrtranclp_trans) qed qed qed
\<comment>\<openCorrespondsSchwoon'slemma3.\close> lemmartranclp_post_star_rules_constains_successors: assumes"post_star_rules\<^F_not_Extq_p()blast s"inits\<ubseteqLTS.srcsA" assumes"isols\<subseteq>LTS.isolatedA" assumes"(Initp,w,q)\<have"(Initp'wa)\inLTS_\<epsilon>.trans_star_\<epsilon>A\<and>(p',w'a)\<Rightarrow>\<^sup>*(p,w)" shows"(\<not>is_Isolatedq\<longrightarrow>(\<exists>p'w'.(Initp',w',q)\<in>java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3 (is_Isolatedq\<longrightarrow>(the_Ctr_Locq,[the_Labelq])\<Rightarrow>\<define"w=c" usingrtranclp_post_star_rules_constains_successors_statesassms by(metisaveaccepts_\<epsilon>A"
\\<open>CorrespondstoonedirectionofSchwoon'stheorem3.3\<close> theorempost_star_rules_subset_post_star_lang: assumes"post_star_rules\<^sup>*\<^sup assumes"inits\<subseteq>LTS.srcsA" ssumes>LTS.isolatedA"
java.lang.StringIndexOutOfBoundsException: Index 82 out of bounds for length 80 proof fixc::"('ctr_loc,'label)conf" definepwhere"p=fstc" definewwhere"w=sndc" assume"c\<in>{c.accepts_\<epsilon>A'c}" thenhavesubsection\>IntersectionilonAutomata<close> unfoldingp_defw_defbyauto thenobtainqjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 unfoldingaccepts_\<epsilon>_defbyauto thentainef:"_<psilon.\<epsilon>_expw'w\<and>(Initp,w',q)\<in>LTS.trans_starA'" by(mesonLTS_\<epsilon>.trans_star_\<epsilon>_iff_\<epsilon>_exp_trans_star) thenhavepath:"(Initp,w byauto have"\<not>is_Isolatedq" usingF_not_Extq_p(1)byblast thenobtainp'w'awhere"(Initp',w'a rtranclp_post_star_rules_constains_successors[OFassms(1)assms(2)assms(3)path]byauto thenhave"(Initp',w'a,q)\<in>LTS_\<epsilon>.trans_star_\<epsilon>A\<and>(p',w'a)\<Rightarrow>\<^sup>*(p,w)" usingw'_def by(metisLTS_\<epsilon>.\<epsilon>_exp_defLTS_\<epsilon>.remove_\<epsilonhavep'w)inLTS_\<epsilon>.trans_star_\<epsilon>(inters_\<epsilon>ts1ts2)" \openLTS_\<epsilon>.\<epsilon>_expw'w\<and>(Initp,w',q)\<in>LTS.trans_starA'\<close>) ost_star<>A)" usingq\<in>finals\<close>unfoldingLTS.post_star_defaccepts_\<epsilon>_deflang_\<epsilon>_defbyfastforce thenshow"c\<in>post_star(lang_\<epsilon>A)" unfoldingby(nTS_.trans_star_\<epsilon>.trans_star_<epsilon>_step_\<>) qed
\<comment>\<open>CorrespondstoSchwoon'stheorem3.3\<close> theorempost_star_rules_accepts_\<epsilon>_correct: assumes"saturationpost_star_rulesAA'" assumes"inits\<subseteq>LTS.srcsA" assumes"isols\<subseteq>LTS.isolatedA" shows"{c.accepts_\<epsilon>A'c}=post_star(lang_\<epsilon>A)"
java.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18 fixc::"('ctr_loc,'label)conf" define"p=c" definewwhere"w=sndc" assume"c\<usingby(metis) java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15 byutopost_star_defw_def thenhave"accepts_\<epsilon>A'(p,w)" usinglemma_3_3[ofp'w'pwAA']assms(1)byauto thenhave"accepts_\<epsilon>A'c" unfoldingp_defw_defbyauto then((p'q1),w,p2q2LTS_\<epsilon>.trans_star_\<epsilon>(inters_\epsilon>ts2)" java.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11 next c:'_abelnf" <{c.accepts_\<epsilon>A'c}" thenshow"c\<in>post_star(lang_\<epsilon>A)" usingassmspost_star_rules_subset_post_star_langunfoldingsaturation_defbyblast qed
definitionlang_inters::"(('ctr_loc,'noninit,'label)state*('ctr_loc,'noninit,'label)state,'label)transitionset\<Rightarrow>(('ctr_loc,'- lang_interstsfinals={c.accepts_interstsjava.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 59
lemmatrans_star_trans_star_\<epsilon>_inter "LTS_\<epsilon>.\<epsilon>expw1w" assumes"LTS_\epsilon.<>_expw2w" assumes"(p1,w1,p2)\<in>LTS.trans_starts1" assumes"(q1,w2,q2)\<in>LTS.trans_starts2" shows"(p1,q1),w:labellist,(p2q2)\>LTS_\<>.trans_star_epsilon(inters_\<epsilon>)" usingassms proof(induction"lengthw1+lengthw2"arbitrary:w1w2wp1q1rule:less_induct) case thenshow?case proof(cases"\<exists>\<alpha>w1'w2'\<beta>.w1= Trueobtain\<java.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 59 "w1=Some\<alpha>#w1'" "w2=Some\<beta>next byauto have"\<alpha>=\<beta>" se)True2S_<>.\<epsilon>_xp_Some_hdssrems)ssems) thenhaveTrue': "w1=Some\<alpha>#w1'" "w2=Some\<alpha>w2' usingTrue''byauto obtainp'wherep'_(p1,Some\<alpha,p)<>ts1\<and>(p',w1',)inLTS.trans_starts1" usinglessTrue'(1)by(metisLTS_\<epsilon>.trans_star_cons_\<epsilon>) obtainq'whereq'_p:"(q1,Some\<alpha>,q')\<in>ts2\<and>(q',w2',q2)\<in>LTS.trans_starts2" java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19 haveind:"((p',q"pome<gamma>)in(,\epsilon>,p1,q2)|p11.\<>q2)\<in>ts2}" proof- have"lengthw1'+lengthw2'<lengthw1+lengthw2" usingTrue'(1)True'(2)byo moreover "\epsilonepsilon_expw1'w'" by(metis(no_types)LTS_\<epsilon>.\<epsilon>_exp_defless(2)True'(1)list.map(2)list.sel(3) option.simps(3)removeAll.simps(2)w'_def) moreover have"LTS_\<epsilon>.\<epsilon>_expw2'w'" by(metis(no_types)LTS_\<epsilon>.\<epsilon>_exp_defless(3)True'(2)list.map(2)list.sel(3) option.simps(3)removeAll.simps(2)w'_def) moreover have"(p',w1',p2)\<in>LTS.trans_starts1" usingp'_pbysimp moreover have"(q',w2',q2)\<in>LTS.trans_starjava.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3 usingq'_pbysimp ultimately show"((p',q'),byauto usingless(1)[ofw1'w2'w'p'q']byauto qed moreover have"((p1,q1),Some\<alpha>,(p',q'))\<in>(inters_\<epsilon>ts1ts2)" by(simpadd:inters_\<epsilon>_defp'_pq'_p) ultimately have"((p1,q1),\<alpha>#w'_inters(inters_\<epsilons1)c<longleftrightarrows_<silon1candaccepts_\<epsilon>ts2c" by(mesonLTS_\<epsilon>.trans_star_\<epsilon>.trans_star_\<epsilon>_step_\<gamma>) moreover have"lengthw>0" usingless(3)True'LTS_\<epsilon.>_exp_Some_lengthmetis moreover have"hdw=\<alpha>" usingless(thenwaccepts_epsilon_inters(inters_\<epsilon>s1) ultimately show?java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 16 usingw'_defbyforce next caseFalse noteFalse_outer_outer_outer_outer_r_outerFalse show?thesis (casesw1\>[ caseTrue thenhavesame:"p1=p2\<and>q1=q2" by(metisLTS.trans_star_emptyless.prems(3)less.prems(4)) have"w=[]" usingTrueless(2)LTS_\<epsilonty_emptyto thenshow?thesis usinglessTrue by(simpadd:LTS_\<epsilon>.trans_star_\<epsilon>.trans_star_\<epsilon>_reflsame) next caseFalse noteFalse_outer_outer_outer=False show?thesis proof(cases"\<exists>w1'.w1=\<epsilon>#w1'")
case True (* Adapted from above. *) obtain w1' where True': "w1=ε#w1'" by auto obtain p' where p'_p: "(p1, ε, p') ∈ ts1 ∧ (p', w1', p2) ∈ LTS.trans_star ts1" using less True'(1) by (metis LTS_ε.trans_star_cons_ε) have using less by (metis) have : "(p, q), w, p2, q2) \in LTε (inters_ε proof - have "length w1' + length w2 < length w1 + length w2" using True'(_of_LTS_None: "(,'
have"LTS_ε.ε_exp w1' w" by (metis (no_types) LTS_ε<\< moreover haveassumesq) ∈ (S_>of_LTS A2 by (metis (no_types) less(3)) moreover have"(p', w1', p2) ∈ using p'_p by simp moreover have "(q1, w2, q2) ∈ LTS.trans_star ts2" p ultimately show() 2) \<> using less(1)[of w1' w2 w p' q1] by auto qed moreover have "((p1, q1), ε, (p', q1)) ∈ (inters_ε'q by (simp add: inters_ε LTS__of_LTS_Noneby ultimately have"((p1, q1), w, p2, q2) ∈ LTS_ε.trans_star_ε (inters_ε ts1 ts2)" using LTS_ε.trans_star_ε.simps by fastforce then show ?thesis by next case False note add\epsilontrans_star_>trans_star__refljava.lang.StringIndexOutOfBoundsException: Index 82 out of bounds for length 82 then proof (cases "∃ case True (* Adapted from above. *) then obtain w2' where True': "w2=ε#w2'" byaut have p'_p: "(p1, w1, p2) ∈ LTS.trans_star ts1lemmaεepsilonof_LTS_is_lang: "lang_ε (LTS_ε_of_LTS A2') = lang A2'" using obtain q' where q'_p: "(q1, ε, q') ∈ ts2 ∧(q', w2', q2) ∈ LTS.trans_star ts2" using less True'(1) by (metis LTS_ε.trans_star_cons_ε) "isols ⊆ havelengthw+ thw'< True'(1) by simp moreover have TS_\epsilon_exp w1 w" by (metis (no_types) less(2))
java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20 have"LTS_ε.ε_exp w2' w" by (metis (no_types) LTS_ε.ε_exp_def less(3) True'(1) removeAll have A1'_correct post_star (lang_ε moreover have"(p1, w1, p2) ∈ LTS.trans_star ts1" using p'_p by simp moreover have2',q2 LTS.trans_star ts2 using q'_p by simp ultimately show"((p1, q'), w, p2, q2) ∈ LTS_ε.trans_star_ε (inters_ε ts1 ts2)" using less(1)[of w1 w2' w p1 q'] by auto qed
oreover have"((p1, q1), ε, (p1, q')) ∈ by (simp add: inters_ε_def p'_p q'_p) ultimately have "((p1c1∈.existsc2∈==>* c2" using LTS_ε.trans_star_ε.simps by fastforce then show ?thesis by force next case False then have "(w1 = [] ∧ LTS.isolated using False_outer_outer False_outer_outer_outer False_outer_outer_outer_outer by (metis neq_Nil_conv option.exhaust_sel)
? by (metis LTS_ε
list.simps(8) list.size(3) removeAll.simps(1))
java.lang.StringIndexOutOfBoundsException: Index 75 out of bounds for length 11 qed qed qed qed
lemma trans_star_ε assumes"(p1, w :: 'label list, p2)\in LTS_ε.trans_star_ε assumes "(q1, w, q2) ∈using🚫 shows"((p1, q1), w, (p2, q2)) ∈ LTS_ε.trans_star_ε (inters_ε ts si A1by auto proof - have "∃p (p1, w1', p2 LTSans_star using assms by (simp add:by thenobtain w1' where"LTS_ε.ε_exp w1' w ∧ (p1, w1', p2) ∈ LTS.trans_star ts1" by auto moreover have"∃.ε w2' w ∧ q) ∈ ts2" using assms by (simp add: LTS_ε.trans_star_ε_ε_exp_trans_star) thenobtain w2' where"LTS_ε.ε_exp w2' w ∧(q1, 2', q2 LTS.trans_star ts2" by auto ultimately show ? using trans_star_trans_star_ε_inter by metis qed
lemma inters_trans_star_ε1: assumes"(p1q2, w :: 'label list, p2q2) ∈ LTS_ε.trans_star_ε (inters_ε shows "(fst p1q2, w, fst p2q2) ∈ LTS_ε.trans_star_ε dual_star_correct_early_termination_configs using assms proof (induction rule: LTS_ε.trans_star_ε.inductassumes LTS.isolated A1" case (1 p) then show ?case by (simp add: LTS_ε.trans_star_ε.trans_star_ε_refl) next case (2 p γ q' w q) then have ind: "(fst LTS_ε ts1 by auto from2( ()have"p Some γ {((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1} ∪ " <LTS A1
{((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts1}" unfolding inters_ε_def by auto moreover { assume "(p, Some γ, q') ∈ saturation A2 \and (q1 γ) <> ts2 by simp thenobtain p1 q1 where"p = (p1, q1) ∧ (∃ by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_γ ind by fastforce } moreover { assume "(p, Some γ, q') ∈ {((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1}" then have ?case by auto } moreover { assume "(p, Some γ, q') ∈ {((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts1}" then have ?case by auto } ultimately show ?case by auto next case (3 p q' w q) then have ind: "(fst q', w, fst q) ∈ LTS_ε.trans_star_ε ts1" by auto from 3(1) have "(p, ε, q') ∈
{((p1, q1), α, (p2, q2)) | p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2} ∪
{((p1, q1), ε, (p2, q1)) | p1 p2 q1. (p1, ε, p2) ∈ ts1} ∪
{((p1, q1), ε, (p1, q2)) | p1 q1 q2. (q1, ε, q2) ∈ ts2}" unfolding inters_ε_def by auto moreover { assume "(p, ε, q') ∈ {((p1, q1), α, p2, q2) |p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2}" then have "∃p1 q1. p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, ε, p2) ∈ ts1 ∧ (q1, ε, q2) ∈ ts2)" by simp then obtain p1 q1 where "p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, ε, p2) ∈ ts1 ∧ (q1, ε, q2) ∈ ts2)" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } moreover { assume "(p, ε, q') ∈ {((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1}" then have "∃p1 p2 q1. p = (p1, q1) ∧ q' = (p2, q1) ∧ (p1, ε, p2) ∈ ts1" by auto then obtain p1 p2 q1 where "p = (p1, q1) ∧ q' = (p2, q1) ∧ (p1, ε, p2) ∈ ts1" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } moreover { assume "(p, ε, q') ∈ {((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts2}" then have "∃p1 q1 q2. p = (p1, q1) ∧ q' = (p1, q2) ∧ (q1, ε, q2) ∈ ts2" by auto then obtain p1 q1 q2 where "p = (p1, q1) ∧ q' = (p1, q2) ∧ (q1, ε, q2) ∈ ts2" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } ultimately show ?case by auto qed
lemma inters_trans_star_ε: assumes "(p1q2, w :: 'label list, p2q2) ∈ LTS_ε.trans_star_ε (inters_ε ts1 ts2)" shows "(snd p1q2, w, snd p2q2) ∈ LTS_ε.trans_star_ε ts2" using assms proof (induction rule: LTS_ε.trans_star_ε.induct[OF assms(1)]) case (1 p) then show ?case by (simp add: LTS_ε.trans_star_ε.trans_star_ε_refl) next case (2 p γ q' w q) then have ind: "(snd q', w, snd q) ∈ LTS_ε.trans_star_ε ts2" by auto from 2(1) have "(p, Some γ, q') ∈
{((p1, q1), α, p2, q2) |p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2} ∪
{((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1} ∪
{((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts2}" unfolding inters_ε_def by auto moreover { assume "(p, Some γ, q') ∈ {((p1, q1), α, p2, q2) |p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2}" then have "∃p1 q1. p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, Some γ, p2) ∈ ts1 ∧ (q1, Some γ, q2) ∈ ts2)" by simp then obtain p1 q1 where "p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, Some γ, p2) ∈ ts1 ∧ (q1, Some γ, q2) ∈ ts2)" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_γ ind by fastforce } moreover { assume "(p, Some γ, q') ∈ {((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1}" then have ?case by auto } moreover { assume "(p, Some γ, q') ∈ {((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts2}" then have ?case by auto } ultimately show ?case by auto next case (3 p q' w q) then have ind: "(snd q', w, snd q) ∈ LTS_ε.trans_star_ε ts2" by auto from 3(1) have "(p, ε, q') ∈
{((p1, q1), α, (p2, q2)) | p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2} ∪
{((p1, q1), ε, (p2, q1)) | p1 p2 q1. (p1, ε, p2) ∈ ts1} ∪
{((p1, q1), ε, (p1, q2)) | p1 q1 q2. (q1, ε, q2) ∈ ts2}" unfolding inters_ε_def by auto moreover { assume "(p, ε, q') ∈ {((p1, q1), α, p2, q2) |p1 q1 α p2 q2. (p1, α, p2) ∈ ts1 ∧ (q1, α, q2) ∈ ts2}" then have "∃p1 q1. p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, ε, p2) ∈ ts1 ∧ (q1, ε, q2) ∈ ts2)" by simp then obtain p1 q1 where "p = (p1, q1) ∧ (∃p2 q2. q' = (p2, q2) ∧ (p1, ε, p2) ∈ ts1 ∧ (q1, ε, q2) ∈ ts2)" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } moreover { assume "(p, ε, q') ∈ {((p1, q1), ε, p2, q1) |p1 p2 q1. (p1, ε, p2) ∈ ts1}" then have "∃p1 p2 q1. p = (p1, q1) ∧ q' = (p2, q1) ∧ (p1, ε, p2) ∈ ts1" by auto then obtain p1 p2 q1 where "p = (p1, q1) ∧ q' = (p2, q1) ∧ (p1, ε, p2) ∈ ts1" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } moreover { assume "(p, ε, q') ∈ {((p1, q1), ε, p1, q2) |p1 q1 q2. (q1, ε, q2) ∈ ts2}" then have "∃p1 q1 q2. p = (p1, q1) ∧ q' = (p1, q2) ∧ (q1, ε, q2) ∈ ts2" by auto then obtain p1 q1 q2 where "p = (p1, q1) ∧ q' = (p1, q2) ∧ (q1, ε, q2) ∈ ts2" by auto then have ?case using LTS_ε.trans_star_ε.trans_star_ε_step_ε ind by fastforce } ultimately show ?case by auto qed
lemma inters_ε_accept_ε_iff: "accepts_ε_inters (inters_ε ts1 ts2) c ⟷ accepts_ε ts1 c ∧ accepts_ε ts2 c" proof assume "accepts_ε_inters (inters_ε ts1 ts2) c" then show "accepts_ε ts1 c ∧ accepts_ε ts2 c" using accepts_ε_def accepts_ε_inters_def inters_trans_star_ε inters_trans_star_ε1 by fastforce next assume asm: "accepts_ε ts1 c ∧ accepts_ε ts2 c" define p where "p = fst c" define w where "w = snd c"
from asm have "accepts_ε ts1 (p,w) ∧ accepts_ε ts2 (p,w)" using p_def w_def by auto then have "(∃q∈finals. (Init p, w, q) ∈ LTS_ε.trans_star_ε ts1) ∧
(∃q∈finals. (Init p, w, q) ∈ LTS_ε.trans_star_ε ts2)" unfolding accepts_ε_def by auto then show "accepts_ε_inters (inters_ε ts1 ts2) c" using accepts_ε_inters_def p_def trans_star_ε_inter w_def by fastforce qed
lemma inters_ε_lang_ε: "lang_ε_inters (inters_ε ts1 ts2) = lang_ε ts1 ∩ lang_ε ts2" unfolding lang_ε_inters_def lang_ε_def using inters_ε_accept_ε_iff by auto
subsection ‹Dual search›
lemma dual1: "post_star (lang_ε A1) ∩ pre_star (lang A2) = {c. ∃c1 ∈ lang_ε A1. ∃c2 ∈ lang A2. c1 ==>* c ∧ c ==>* c2}" proof - have "post_star (lang_ε A1) ∩ pre_star (lang A2) = {c. c ∈ post_star (lang_ε A1) ∧ c ∈ pre_star (lang A2)}" by auto moreover have "... = {c. (∃c1 ∈ lang_ε A1. c1 ==>* c) ∧ (∃c2 ∈ lang A2. c ==>* c2)}" unfolding post_star_def pre_star_def by auto moreover have "... = {c. ∃c1 ∈ lang_ε A1. ∃c2 ∈ lang A2. c1 ==>* c ∧ c ==>* c2}" by auto ultimately show ?thesis by metis qed
lemma dual2: "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {} ⟷ (∃c1 ∈ lang_ε A1. ∃c2 ∈ lang A2. c1 ==>* c2)" proof (rule) assume "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {}" then show "∃c1∈lang_ε A1. ∃c2∈lang A2. c1 ==>* c2" by (auto simp: pre_star_def post_star_def intro: rtranclp_trans) next assume "∃c1∈lang_ε A1. ∃c2∈lang A2. c1 ==>* c2" then show "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {}" using dual1 by auto qed
lemma trans_star_ε_LTS_ε_of_LTS_trans_star: assumes "(p,w,q) ∈ LTS_ε.trans_star_ε (LTS_ε_of_LTS A2')" shows "(p,w,q) ∈ LTS.trans_star A2'" using assms proof (induction rule: LTS_ε.trans_star_ε.induct[OF assms(1)] ) case (1 p) then show ?case by (simp add: LTS.trans_star.trans_star_refl) next case (2 p γ q' w q) moreover have "(p, γ, q') ∈ A2'" using 2(1) using LTS_ε_of_LTS_Some by metis moreover have "(q', w, q) ∈ LTS.trans_star A2'" using "2.IH" 2(2) by auto ultimately show ?case by (meson LTS.trans_star.trans_star_step) next case (3 p q' w q) then show ?case using LTS_ε_of_LTS_None by fastforce qed
lemma trans_star_trans_star_ε_LTS_ε_of_LTS: assumes "(p,w,q) ∈ LTS.trans_star A2'" shows "(p,w,q) ∈ LTS_ε.trans_star_ε (LTS_ε_of_LTS A2')" using assms proof (induction rule: LTS.trans_star.induct[OF assms(1)]) case (1 p) then show ?case by (simp add: LTS_ε.trans_star_ε.trans_star_ε_refl) next case (2 p γ q' w q) then show ?case by (meson LTS_ε.trans_star_ε.trans_star_ε_step_γ LTS_ε_of_LTS_Some) qed
lemma accepts_ε_LTS_ε_of_LTS_iff_accepts: "accepts_ε (LTS_ε_of_LTS A2') (p, w) ⟷ accepts A2' (p, w)" using accepts_ε_def accepts_def trans_star_ε_LTS_ε_of_LTS_trans_star trans_star_trans_star_ε_LTS_ε_of_LTS by fastforce
lemma lang_ε_LTS_ε_of_LTS_is_lang: "lang_ε (LTS_ε_of_LTS A2') = lang A2'" unfolding lang_ε_def lang_def using accepts_ε_LTS_ε_of_LTS_iff_accepts by auto
theorem dual_star_correct_early_termination: assumes "inits ⊆ LTS.srcs A1" assumes "inits ⊆ LTS.srcs A2" assumes "isols ⊆ LTS.isolated A1" assumes "isols ⊆ LTS.isolated A2" assumes "post_star_rules** A1 A1'" assumes "pre_star_rule** A2 A2'" assumes "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {}" shows "∃c1 ∈ lang_ε A1. ∃c2 ∈ lang A2. c1 ==>* c2" proof - have "{c. accepts_ε A1' c} ⊆ post_star (lang_ε A1)" using assms using post_star_rules_subset_post_star_lang by auto then have A1'_correct: "lang_ε A1' ⊆ post_star (lang_ε A1)" unfolding lang_ε_def by auto
have "{c. accepts A2' c} ⊆ pre_star (lang A2)" using pre_star_rule_subset_pre_star_lang[of A2 A2'] assms by auto then have A2'_correct: "lang A2' ⊆ pre_star (lang A2)" unfolding lang_def by auto
have "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) = lang_ε A1' ∩ lang_ε (LTS_ε_of_LTS A2')" using inters_ε_lang_ε[of A1' "(LTS_ε_of_LTS A2')"] by auto moreover have "... = lang_ε A1' ∩ lang A2'" using lang_ε_LTS_ε_of_LTS_is_lang by auto moreover have "... ⊆ post_star (lang_ε A1) ∩ pre_star (lang A2)" using A1'_correct A2'_correct by auto ultimately have inters_correct: "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ⊆ post_star (lang_ε A1) ∩ pre_star (lang A2)" by metis
from assms have "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {}" using inters_correct by auto then show "∃c1∈lang_ε A1. ∃c2∈lang A2. c1 ==>* c2" using dual2 by auto
qed
theorem dual_star_correct_saturation: assumes "inits ⊆ LTS.srcs A1" assumes "inits ⊆ LTS.srcs A2" assumes "isols ⊆ LTS.isolated A1" assumes "isols ⊆ LTS.isolated A2" assumes "saturation post_star_rules A1 A1'" assumes "saturation pre_star_rule A2 A2'" shows "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {} ⟷ (∃c1 ∈ lang_ε A1. ∃c2 ∈ lang A2. c1 ==>* c2)" proof - have "{c. accepts_ε A1' c} = post_star (lang_ε A1)" using post_star_rules_accepts_ε_correct[of A1 A1'] assms by auto then have A1'_correct: "lang_ε A1' = post_star (lang_ε A1)" unfolding lang_ε_def by auto
have "{c. accepts A2' c} = pre_star (lang A2)" using pre_star_rule_accepts_correct[of A2 A2'] assms by auto then have A2'_correct: "lang A2' = pre_star (lang A2)" unfolding lang_def by auto
have "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) = lang_ε A1' ∩ lang_ε (LTS_ε_of_LTS A2')" using inters_ε_lang_ε[of A1' "(LTS_ε_of_LTS A2')"] by auto moreover have "... = lang_ε A1' ∩ lang A2'" using lang_ε_LTS_ε_of_LTS_is_lang by auto moreover have "... = post_star (lang_ε A1) ∩ pre_star (lang A2)" using A1'_correct A2'_correct by auto ultimately have inters_correct: "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) = post_star (lang_ε A1) ∩ pre_star (lang A2)" by metis
show ?thesis proof assume "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {}" then have "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {}" using inters_correct by auto then show "∃c1∈lang_ε A1. ∃c2∈lang A2. c1 ==>* c2" using dual2 by auto next assume "∃c1∈lang_ε A1. ∃c2∈lang A2. c1 ==>* c2" then have "post_star (lang_ε A1) ∩ pre_star (lang A2) ≠ {}" using dual2 by auto then show "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {}" using inters_correct by auto qed qed
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.118Bemerkung:
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
Suchen
