| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/Isabelle/Archive-of-Formal-Proofs/thys/Pushdown_Systems/ Datei vom 29.4.2026 mit Größe 135 kB |
|
Quelle PDS.thySprache: Isabelle |
|||||||||||||||
|
theory PDS imports "P_Automata" "HOL-Library.While_Combinator" begin section ‹PDS› datatype 'label operation = pop | swap 'label | push 'label 'label type_synonymtheoryPDS "P_Automata" "HOL-Library.While_Combinator" begin type_synonym ('ctr_loc, 'label) conf = "'ctr_loc × 'label list" text ‹ PDS = fixes Δ :: "('ctr_loc, 'label::finite) rule set" (* 'ctr_loc is the type of control locations *)ush 'label 'label lbl :: "'label operation ==> 'label list" where "lbl pop = []" "lbl (swap γ) = [γ]" "lbl (push γ γ') = [γ, γ']" is_rule :: "'ctr_loc × 'label ==> 'ctr_loc × 'label operation ==> bool" (infix "pγ ↪ p'w ≡ (pγ,p'w) ∈ Δ" transition_rel :: "(('ctr_loc, 'label) conf × unit × ('ctr_loc, 'label) conf) s "(p, γ) ↪ (p', w) ==> ((p, γ#w'), (), (p', (lbl w)@w')) ∈ transition_rel" LTS transition_rel . step_relp (infix ‹==>› 80) step_starp (infix ‹ ('ctr_loc, 'label) rule = "('ctr_loc × ('ctr_loc × 'label o step_relp_def2: "(p, γ ‹ by (metis (no_types, lifting) PDS.transition_rel.intros step_relp_def ttransitio ‹e)ruest ('ctr_loc, 'label) sat_rule = "('ctr_loc, 'label) transition set ==> ('ctr_loc, 'noninit, 'label) state = is_Init: Init (the_Ctr_Loc: 'ctr_loc) (* p \<in> P *) |is_Noninit:Noninit: 'noninit (* q \<in> Q \<and> q \<notin> P *) | is_Isolated: Isolated lemma: assumes : ctr_loc assumes "finite|" (push> γ' \gamma,🚫 assumes "finite (UNIV :: 'label set)" shows "finite (UNIV :: ('ctr_loc, 'noninit, 'label) state set)" proof - define Isolated' :: "('ctr_loc * 'label) ==>hookri> p'w ≡ "Isolated' == λ(c :: 'ctr_loc, l:: 'label). Isolated c l" define Init' :: "'ctr_loc ==> ('ctr_loc, 'noninit, 'label) state" where "Init' = Init" define Noninit' :: "'noninit ==> ('ctr_loc, 'noninit, 'label) state" where "Noninit' = Noninit" have split: "UNIV = (Init' ` UNIV) ∪ (Noninit' ` UNIV) ∪ (Isolated' ` (UNIV :: (('ctr_loc * 'lab 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 instance by standard (simp add: finitely_many_states) end locale PDS_with_P_automata = PDS Δ for Δ :: "('ctr_loc::enum, 'label::finite) rule set" + fixes final_inits :: "('ctr_loc::enum) set" fixes final_noninits :: "('noninit::finite) set" begin (* Corresponds to Schwoon's F *) definition finals :: "('ctr_loc, 'noninit::finite, 'label) state set" where "finals = Init ` final_inits ∪ Noninit ` final_noninits" lemma F_not_Ext: "¬(∃f∈finals. is_Isolated f)" using finals_def by fastforce (* Corresponds to Schwoon's P *) definition inits :: "('ctr_loc, 'noninit, 'label) state set" where "inits = {q. is_Init q}" lemma inits_code[code]: "inits = set (map Init Enum.enum)" ( simp simpUNIV_enum definition noninits :: "('ctr_loc, 'noninit, 'label) state set" where "noninits = {q. is_Noninit q}" definition isols :: "('ctr_loc, 'noninit, 'label) state set" where "isols = {q. is_Isolated q}" sublocale notation step_relp notation ( \open<><^up<close definition accepts :: "(('ctr_loc, 'noninit, 'label) state, 'label) transition set "accepts ts ≡ λ(p,w). (∃q ∈) transit se \Rightarrow(ctr_, 'lab) transition s ==> lemma accepts_accepts_aut: "accepts ts (p, w) ⟷ P_Automaton.accepts_aut ts Init finals p w unfolding accepts_def P_Automaton.accepts_aut_def inits_def by auto definition accepts_ε :: "(('ctr_loc, 'noninit, 'label) state, 'label option) transition "accepts_(ctr_loc,'noninit= abbreviation ε :: "'label option" where "ε == None" lemma accepts_mono[mono proof (rule, rule| is_Noninit: Noninit (the_St: 'noninit) (* q \<in> Q \<and> q \<notin> P *) fix c :: ('tr_loc 'label fix assume accepts_ts: " ts c" ': "ts \<subseteq obtain p l where pl_p: "c (l) by (cases c) obtainre∈ (Init p, l, q) ∈ LTS.trans_star ts" using accepts_ts unfolding pl_p accepts_def by auto then have "(Init p, l, q) ∈ LTS.trans_star ts'" using tsts' shows "finite (UNIV :: ('ctr_loc'noninit, 'label set)" thenhave acc ts' (p,l" unfolding "Isolated'' == \lambda( ::'troc, l::'lael) Isoatd c " then show defineInitctr_locRightarrow ('ctr_loc, 'noninit, 'label) state" where unfolding pl_p . qed lemmaaccepts_cons:"Init, Init p') ∈ accepts ts\Longrightarrowpts # w)" using LTS.trans_star.trans_star_step a have splt:"=Init> (Noninit' ` UNIV) ∪:r_loc) definition lang('ctr_loceltransitionRightarrow ('ctr_loc, 'label) conf where "lang ts = {c. accepts ts c}" lemmalang_lang_aut(lambda(utomatonnals unfolding lang_def P_Automaton.fixx : "(ctrloc, 'noni, 'label) state" by (auto simp: inits_def ccepts_defts_aut_def!xI _"]) lemma lang_aut_lang: "P_Automaton.lang_aut moreover unfolding lang_lang_aut by (auto 3 Automatonaton Automatonccepts_aut_def definition lang_ ang_ ts = {c. accepts_ ts c}" subsection ‹ range Init" definition saturated :: " 'c, 'l) sat_rule \< by "saturated rule ts ⟷ saturation :: "('c, 'l) sat_rule ==>) "saturation rule ts thenhavefinite (Isola' ` (UNIV :: (('ctr_loc *) set)))" 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 lengt by (metisfar_into_rtranclp_saturated_def someI) then have " 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 subsection ‹ inductive pre_star_rule :: " (cr_lc, 'nnnit 'labl)stat, label) transitio set 🚫 L add_trans: "(p, γ LTS.trans_star ts'" (Init p, \gamma, q) ∉ pre_star_rule ts (ts ∪ pre_star1 :: "(('ctr_loc, 'oniit,'lael)stae, lbel tanstio st\Rightarrow (('ctr_ "pre_star1 ts = (∪, Init p') ∈ accepts t)\Longrightarrow accepts ts (p, γ # w)" pre_star1_mono: "mono pre_star1" unfolding pre_star1_def by (auto simp: mono_def LTS.tran_star_code[symmetric] elim!: beI[oaed LTS_trans_star_monoTHENmn,THEN ubset] 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 _ar_rulepre_tr: "re_tarrle\^>** ts (((λ pre_star1 s) ^^ k) ts)" by (induct k) (auto elim!: rtranclp_trans intro: pre_star_rule_pre_star1) "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) pre_star_exec_terminates: "∃ unfolding preshows "\ote>t (∀s uci) by (rule while_option_finite_subs (auto simp: mono_def dest: pre_staassumes"<>ts 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_ 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) transit 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 (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: " 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 met 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 me 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 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) assume "∄q γ q'. (q, γ, Init q') ∈ A" show "inits ⊆ LTS.srcs A" by (metis LTS.srcs_def2 inits_def ‹> q'. (q, γ A› state.collapse(1) subsetI) 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 word_into_init_empty_states: fixes A :: "(('ctr_lo (Ini(Init p, [γ LTS_ε.trans_star_ε ts ==> assumes "(p, w, ss, Init q) \<inLTS assumes "inits ⊆ shows "w = [] ∧ ss=[p]" - define q1 :: "('ctr_loc, 'nonini "q1 = Init q" have q1_path: "(p, w, ss, q1) ∈ by (simp add: assms(1) q1_def) 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: Inde 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 then show 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 leng 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 lemma assumes "inits ⊆ LTS.trans_star LTS.trans_star A'" assumes "pre_star_rulejava.lang.NullPointerException assumes "(Init p, w, q) ∈ shows " proof"saturation pot__sar_ruls A A' \<> _<epsilon>.ans_tr<epsilon> '" case base then have "(Init p, w, q) ∈ saturation_def) by auto then show ?case by auto next case (step Aiminus1 Ai) from step(2) obtain p1 γ_p2_w2_q'_p: "Ai "(p1, γ (p2, w2)" "(Init p2, lbl w2, q') ∈ LTS.trans_star Aimithen how \nexistsq γ q'. (q, γ A" it>, q') ∉ by(mesonpre_star_rulelees e:"((ctr_o,'oinit, 'abel) tte'labe) tansition" whereby metiss_def∄q γ q'. (q, γ, Init q') ∈ mem_Collect_eq obtain ss where ss_p usingassumes "pv ∈A define j where "case 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" then show ?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 where 11)<>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 Aim 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_, Ini 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 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 java.lang.NullPointerException usingshows " "(p,u @ v) ==>* (p1, y @ v)" 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 "b 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_ assms by auto pre_star_exec_lang_correct: assumes "inits ⊆.trans_star_trans_star_st[of "Init p2" "lbl w2" q' Aiminus1] by 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] 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_ 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(tanssition 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) ==>* ( 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_sr 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 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 m 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' γ [γ''], q 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' γ', So 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_sour 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) st 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 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.la 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 post_star_rules_Isolated_sink_invariant: java.lang.NullPointerException 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_rules LTS.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_ε. (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)" using local.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_Iso 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 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.prem 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, 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: 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 < using count_append_path_with_word_γ[of "[hd ss]" "[]" "tl ss" "hd w" "tl w" "Init 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 bl 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) from Suc(1)[of p2 "γ(t s)] have V: "(¬ {(p1, γ, q1)}" (\"p1,\gamma, q1) ∉ (is_Isolated q ⟶ coun(transitions_f' (Init p, w, ss, q) using step.IH step.prems(1,2,3) by blast ""¬ 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_rtranc 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 then show ?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.StringIndexOutOfBoundsExcepti 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 using VI ( append_Nil lbl.simps(1) rtranclp.simps step_relp_def2) then have "(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 bl 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.prem count_empty less_not_refl2 list.distinct(1) transition_list.simps(1) transitions 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_Aiminus 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› 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)) 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 ‹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 Ai 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_ε.rem 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\<p 🚫 then obtain p' w' where VIII:"(Init p', w', q)∈.trans_star_🚫 A" and steps: "(p', w') ==>* (p2, LTS_εepsi 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_onv using VIII using PDS.transition_rel.intros append_self_conv2 lbl.simps(1) r_into_rtranclp s 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 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] 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( using VI by (metis (no_types) append_Cons append_Nil lbl.simps(2) rtranclp.rtrancl_into_r 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 me 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.prem 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› 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 using local.add_trans_push_2 have "(tl ss, tl w) ∈" then obtain 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) then haveε>.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 then have 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.la proof - have γ2ss_len: "length γ2ss = Suc (length γ (the_Ctr_Loc q, [the_Label q]) ==>* (p2, by (meson LTS.trans_star_states_length XI_1) have using 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' (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) ∈) (if Isolated p1 \<gamma>1 = last u_ss \<andhave "'<ightarrow\<^sup>* (p2, LTS_\<epsilon>.remove_\<e count (transitions_of' (q', v, v_ss, )olatedtedp1<>1, Some \<gamma>'', q'" using count_append_trans_star_states_\<gammalengthfsu_ Init solated <amma>" "Some \<gamma>' bySans_star_states_lengthstar_states_lengthr_states_lengthtates_lengthes_lengths then have "count (transitions_of (u_ss @ v_ss, u @ Some \<gamma>'' # v)) (last using VIII by force then have "j = count (transitions_of' ((q',v, v_ss, q))) t" using last_u_ss q'_hd_v_ss X_1 ss_split w_split add_trans_push_2(4) Suc(2) LTS.avoid_count_zero[of "Init p" u u_ss "Isolated p1 \<gamma>1" Aiminus1 "Isolated p1 \<gamma>1 by (auto simp: t_def) then show "j = count (transitions_of ((v_ss, v))) t" by force qed have p2_q'_states_Aiminus1: "(Init p2, \<gamma>2<2ss, q') \<in> LTS.trans_star_statesjava.la using XI_1 by blast engamma2: "count (transitions_of 2ss, \<gamma>2<>))=" using LTS. l__)ocal_ans_pop<>_p2_w2_q1_eflast havetransitions_ofgamma2ss, \<gamma>2\<epsilon>) @\<acute>_ ) using LTS.count_append_path_with_word[of \<gamma>2ss \<gamma>2\<epsilon> v_ss v "Isolated ()<i chave"=Init <>1,olated gamma1)" by force then have j_count: "j = count by qed have "gamma2, \<gamma>2\<epsilon>) \<in> LTS.path_with_word Aiminus1" by (meson LTS.trans_star_states_path_with_word p2_q'_states_Aiminus1) then have \<gamma>2ss_path: "(\<gamma>2ss, \<gamma>2\<epsilon>) \<in> LTS.path_with_word havehdio using path_with_word_mono'[of \<gamma>2ss 'sv <n> LTS.path_with_word Ai" 2 def have "(\<gamma>2ss, \<gamma>2\<epsilon>) @\<acute> (v_ss, v) \<in> LTS.path_with_word Ai" using \<gamma>2ss_path path' LTS.append_path_with_word_path_with_word \<gamma>2ss_last by auto then have "(\<gamma>2ss @ tl v_ss, \<gamma>2\<epsilon> @ v) \<in> LTS.path_with_word Ai" by auto have "(Init p2, \<gamma>2\<epsilon> yjava.lang.StringIndexOutOfBoundsException: Index 27 typesgLTSth_with_word_trans_star_states LTS.trans_star_states_append LTS.trans_star_states_hd XI_1 path \<gamma>2ss_path \<gamma> by mesonr_into_rtranclp show "(\<not>is_Isolated q \<longrightarrow> (\<exists>p' w'. (Init p', w', q) \<in> LTS_\<epsilon>.trans (the_Ctr_Loc q, [[ q]) \<Rightarrow>\<sup*(, LTS_\epsilonremove_ (\<gamma>2\<epsilonv) using j_count by fastforce qed show ?thesis proof (cases "is_Init< is_Noninit q") True (exists'w it q<> TS_epsilon.trans_star_\<epsilon> A \<dp \<^sup>* (p2, LTS_.remove_\<epsilon> (\<ga using True ind by fastforce obtain p' w'where'_'_p ( 'q<> LTS_\<epsilon>._r_<epsilon<>\<^sup>* (p2_><> (\<gamma>2\<epsilon> @ v))" by auto then have "(p', w') \<Rightarrow>\<^sup>* (p2, LTS_\<epsilon>.remove_\<epsilon> (\<gamma>2\<epsilo by auto have p2_\<gamma>2\<epsilon>v_p1_\<gamma (solated 1, Some \<gamma>'', q') = proof - have "\<gamma>2 #(LTS_\<epsilon>.remove_\<epsilon> v) = LTS_\<epsilon>.remove_\<epsilon> (\<gamma> using XI_1 by (metis LTS_\<epsilon>.\<epsilon>_exp_def LTS_\<epsilon>.remove_\<epsilon>_append_dist LTS self_append_conv2) moreover from XIII have "(p2, \<>\>remove_ v)) \<Rightarrow^sup* (p1, \<gamma>1#\<gamma>''#LTS_<epsilone_e by (metis PDS.transition_rel.intros append_Cons append_Nil lbl.simps(3) r_into_rtrancl ultimately show "(p2, LTS_\<epsilon>.remove_\<epsilon> (\<gamma>2\<epsilon> @ v)) \<Rightarrow>\< by auto qed have \<gamma>\<>''v_p_uv (,\gamma#<>'S_<silonove_> )Rightarrow\<^sup>* (p, (S_>.remove_\<epsilon> u by metis p1_\<gamma>1_p_uappend_Cons append_Nil step_relp_append have "(LTS_epsilon>.remove_\<epsilon> u) @ (\<gamma>''#LTS_\<epsilon>.remove_\<epsilon> v)) = (_ by (metis (no_types, lifting) Cons_eq_append_conv LTS_\<epsilonby (etis LTS_\<>.<>_ LTS_\<epsi LTS_\<epsilon>.remove_\<epsilon>_append_dist w_split hd_Cons_tl list.inject list.sel(1) l self_append_conv2) show ?thesis True p1_\<gamma>1\<gamma>''v_p_uv p2_\<gamma>2\<epsilon>v_p1_\<gamma>1_\<gamma>''_v p'_w'_p by fa next caseFalse then have q_nlq_p2_\<gamma>2\<epsilon>v: "(the_Ctr_Loc q, [the_Label q]) \<Rightarrow>\<^sup>* ( using ind state.exhaust_disc by java.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 1 <\<epsilon>v_p1_<gamma>\gamma>,\<epsilon>.remove_\<epsilon \>2\epsilon> )<>\<^sup*p1, \<\>.epsilonv by( (mono_tags) \<epsilon_exp_def LTS_epsilon.remove_\<epsilon>_append_dist\<epsilon>.re XI_1append_Cons append_Nillbl.simps(step_relp_def2) have p1_\<gamma>1\<gamma>''_v_p_u\<gamma>'1 # \<gamma>'' #TS_epsilon>.remove_\<epsilon> v\Righta by (metis p1_\<gamma>1_lemma post_star_rules_saturation_constains_successors: "(p, LTS_\<epsilon>.remove_\<epsilon> u @ \<gamma>'' # LTS_\<epsilon>.remove_\<epsilon> v) = (p, LTS (metis LTS_\epsilon>.remove_\<epsilon>_Cons_tl LTS_\<epsilonremove_\<epsilon>append_dist hd_Cons_tl list.distinct(1) list.inject) then show ?thesis using False p1_\<gamma>1\<gamma>''_v_p_u\<gamma>''v p2_\<gamma>2\<epsilon>v_p1_\<gamma>1\<gamma>' by (metis (no_types, lifting) ind rtranclp_trans) qed qed qed \<comment> \<openCorresponds Schwoon's lemma 3.\close> lemma rtranclp_post_star_rules_constains_successors: assumes "post_star_rules\<^ F_not_Ext q_p() blast s "inits\<ubseteq LTS.srcs A" assumes "isols \<subseteq> LTS.isolated A" assumes "(Init p, w, q) \< have "(Init p' wa )\inLTS_\<epsilon>.trans_star_\<epsilon> A \<and> (p', w shows "(\<not>is_Isolated q \<longrightarrow> (\<exists>p' w'. (Init p', w', q) \<in>java.lang.Str (is_Isolated q \<longrightarrow> (the_Ctr_Loc q, [the_Label q]) \<Rightarrow>\<define "w = c" using rtranclp_post_star_rules_constains_successors_states assms by (metis aveaccepts_\<epsilon> A " (ctr_loc'abel) conf" lemma post_star_rules_saturation_constains_successors: assumes "saturation post_star_rules A A'" assumes "inits \<subseteq> LTS.srcs A" assumes "isols \<subseteq> LTS.isolated A" assumes "(Init p, w, q) \<in> LTS.trans_star A'" shows "(\<not>is_Isolated q \<longrightarrow> (\<exists>p' w'. (Init p', w', q) \<in> LTS_\<epsilon>. (is_Isolated q" using rtranclp_post_star_rules_constains_successors assms saturation_def by metis \ \<open>Corresponds to one direction of Schwoon's theorem 3.3\<close> theorem post_star_rules_subset_post_star_lang: assumes "post_star_rules\<^sup>*\<^sup assumes "inits \<subseteq> LTS.srcs A" ssumes>LTS.isolated A" java.lang.StringIndexOutOfBoundsException: Index 82 out of bounds for length 80 proof fix c :: "('ctr_loc, 'label) conf" define p where "p = fst c" define w where "w = snd c" assume "c \<in> {c. accepts_\<epsilon> A' c}" then have subsection\>IntersectionilonAutomata<close> unfolding p_def w_def by auto then obtain qjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for unfolding accepts_\<epsilon>_def by auto then tain ef:"_<psilon.\<epsilon>_exp w' w \<and> (Init p, w', q) \<in> LTS.trans_star A'" by (meson LTS_\<epsilon>.trans_star_\<epsilon>_iff_\<epsilon>_exp_trans_star) then have path: "(Init p, w by auto have "\<not> is_Isolated q" using F_not_Ext q_p(1) by blast then obtain p' w'a where "(Init p', w'a rtranclp_post_star_rules_constains_successors[OF assms(1) assms(2) assms(3) path] by a then have "(Init p', w'a, q) \<in> LTS_\<epsilon>.trans_star_\<epsilon> A \<and> (p', w'a) \<Rightarr using w'_def by (metis LTS_\<epsilon>.\<epsilon>_exp_def LTS_\<epsilon>.remove_\<epsilonhave p'w )in LTS_\< \openLTS_\<epsilon>.\<epsilon>_exp w' w \<and> (Init p, w', q) \<in> LTS.trans_star A'\<close>) ost_star<>A)" usingq \<in> finals\<close> unfolding LTS.post_star_def accepts_\<epsilon>_def lang_\<epsilon> then show "c \<in> post_star (lang_\<epsilon> A)" unfolding by (nTS_.trans_star_\<epsilon>.trans_star_<epsilon>_step_\<>) qed \<comment> \<open>Corresponds to Schwoon's theorem 3.3\<close> theorem post_star_rules_accepts_\<epsilon>_correct: assumes "saturation post_star_rules A A'" assumes "inits \<subseteq> LTS.srcs A" assumes "isols \<subseteq> LTS.isolated A" shows "{c. accepts_\<epsilon> A' c} = post_star (lang_\<epsilon> A)" java.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18 fix c :: "('ctr_loc, 'label) conf" define "p = c" define w where "w = snd c" assume "c \<using by (metis) java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15 by utopost_star_defw_def then have "accepts_\<epsilon> A' (p, w)" using lemma_3_3[of p' w' p w A A'] assms(1) by auto then have "accepts_\<epsilon> A' c" unfolding p_def w_def by auto then ((p' q1), w, p2q2 LTS_\<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}" then show "c \<in> post_star (lang_\<epsilon> A)" using assms post_star_rules_subset_post_star_lang unfolding saturation_def by blast qed \> \<open>Corresponds to Schwoon's theorem 3.3\<close> remt_star_rules_correct \.trans_star_cons_\<epsilon>) assumes "inits \<subseteq> LTS.srcs A" assumes "isols\subseteq> LTS.isolated A" shows "lang_\<epsilon> A' = post_star (lang_\<epsilon> A)" using assms lang_\<epsilon>_def post_star_rules_accepts_ LTS_\<epsilon>.\<epsilon w1 w" end subsection \<open>Intersection Automata\<close> definition cepts_inters((ctr_loc noninit, 'label) state *(ctr_loc ', ', 'labeltransition "accepts_inters ts finals \<equiv> \<lambda>(p,w). (\<exists>qq have"2> LTS_\<epsilon>.trans_sta lemma accepts_inters_accepts_aut_inters: assumests12=ts1s2" assumes "finals12 = inters_finals finals1 finals2" shows "accepts_inters ts12 finals12 (p,w) \<longleftrightarrow> Intersection_P_Automaton.accepts_aut_inters ts1 Init finals1 ts2 finals2 p w" by (simp add: Intersection_P_Automaton.accepts_aut_inters_def PDS_with_P_automata.in tonccepts_aut_defs_inters_def ssms definition lang_inters :: "(('ctr_loc, 'noninit, 'label) state * ('ctr_loc, 'noninit, 'lab lang_inters ts finals = {c. accepts_inters ts java.lang.StringIndexOutOfBoundsException lemma lang_inters_lang_aut_inters: assumes "ts12 = inters ts1 ts2" assumes "finals12 = inters_finals finals1 finals2" shows "(\<lambda>(p,w). (p, w)) ` lang_inters ts12 finals12 = Intersection_P_Automaton.lang_aut_inters ts1 Init finals1 ts2 finals2" using assms by (auto simp: Intersection_P_Automaton.lang_aut_inters_def Intersection_P_Automaton.inters_accept_iff accepts_inters_accepts_aut_inters lang_inters_def is_Init_def PDS_with_P_automata. by simpd LTS_\epsilon>.trans_star_<>trans_star_\<epsilon>_refl) lemma inters_accept_iff: assumes "ts12 = inters ts1 ts2" "finals12 = inters_finalsPDS_with_P_automata final_initss1 final_noninits1) .finals final_initss2)" shows ters ts12 finals12 (,)\longleftrightarrow PDS_with_P_automata.accepts final_initss1 final_noninits1 ts1 (p,w) \<and> PDS_with_P_automata.accepts final_initss2 final_noninits2 ts2 (p,w using accepts_inters_accepts_aut_inters Intersection_P_Automaton.inters_accept_iff by (simp add: Intersection_P_Automaton.inters_accept_iff accepts_inters_accepts_aut_ PDS_with_P_automata.accepts_accepts_aut) lemma inters_lang: assumes "ts12 = inters ts1 ts2" "finals12 = inters_finals (PDS_with_P_automata.finals final_initss1 final_noninits1) (PDS_with_P_automata.finals final_initss2 final_noninits2)" shows "lang_inters ts12 finals12= PDS_with_P_automata.lang final_initss1 final_noninits1 ts1 \<inter> PDS_with_P_automata.lang final_initss2 final_noninits2 ts2" using assms by (auto simp add: PDS_with_P_automata lang_inters_def) subsection \<open>Intersection epsilon-Automata\<close> context PDS_with_P_automata begin interpretation LTS transition_rel . notation step_relp (infix \<open>\<Rightarrow>\<close> 80) notation step_starpnfix<>\<Rightarrow<sup*\<close> 80) definition<>_nters"(('ctr_loc, 'noninit, 'label) state * (ctr_loc,', 'label) state, labelo <inters ts \<equiv>\>(w(>in finals. \<exists>q2 \<in> alsInitpnit,q2<>TS_\<rans_star_lon efinition lang_\<>_inters :: "(tr_locninitabeltatectr_locninitbeltebelnion\Rightarrow <_inters ts = {c. accepts_\<epsilon>_inters ts lemma trans_star_trans_star_\<epsilon>_inter "LTS_\<epsilon>.\<epsilon>exp w1 w" assumes "LTS_\epsilon.<>_exp w2 w" assumes "(p1, w1, p2) \<in> LTS.trans_star ts1" assumes "(q1, w2, q2) \<in> LTS.trans_star ts2" shows"(p1,q1), w : label list, (p2q2)\> LTS_\<>.trans_star_epsilon (inters_\<epsilon> )" using assms proof (induction "length w1 + length w2" arbitrary: w1 w2 w p1 q1 rule: less_induct) case then show ?case proof (cases "\<exists>\<alpha> w1' w2' \<beta>. w1= True obtain \<java.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for "w1=Some \<alpha>#w1'" "w2=Some \<beta>next by auto have "\<alpha> = \<beta>" se)True2S_<>.\<epsilon>_xp_Some_hdssrems)ssems) then have True': "w1=Some \<alpha>#w1'" "w2=Some \<alpha>w2' using True'' by auto obtain p' where p'_ (p1,Some\<alpha, p) <> ts1 \<and> (p', w1',)inLTS.trans_star ts1" using less True'(1) by (metis LTS_\<epsilon>.trans_star_cons_\<epsilon>) obtain q' where q'_p: "(q1, Some \<alpha>, q') \<in> ts2 \<and>(q', w2', q2) \<in> LTS.trans_star ts2" java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19 have ind: "((p', q"p ome<gamma>)in(, \epsilon>, p1, q2) |p11.\<> q2) \<in> ts2}" proof - have "length w1' + length w2' < length w1 + length w2" using True'(1) True'(2) by o moreover "\epsilonepsilon_exp w1' w'" by (metis (no_types) LTS_\<epsilon>.\<epsilon>_exp_def less(2) True'(1) list.map(2) list.se option.simps(3) removeAll.simps(2) w'_def) moreover have "LTS_\<epsilon>.\<epsilon>_exp w2' w'" by (metis (no_types) LTS_\<epsilon>.\<epsilon>_exp_def less(3) True'(2) list.map(2) list.se option.simps(3) removeAll.simps(2) w'_def) moreover have "(p', w1', p2) \<in> LTS.trans_star ts1" using p'_p by simp moreover have "(q', w2', q2) \<in> LTS.trans_starjava.lang.StringIndexOutOfBoundsException: Inde using q'_p by simp ultimately show "((p', q'), by auto using less(1)[of w1' w2' w' p' q'] by auto qed moreover have "((p1, q1), Some \<alpha>, (p', q')) \<in> (inters_\<epsilon> ts1 ts2)" by (simp add: inters_\<epsilon>_def p'_p q'_p) ultimately have "((p1, q1), \<alpha>#w'_inters (inters_\<epsilons1)c<longleftrightarrows_<silon1cand by (meson LTS_\<epsilon>.trans_star_\<epsilon>.trans_star_\<epsilon>_step_\<gamma>) moreover have "length w > 0" usingless(3) True' LTS_\<epsilon.>_exp_Some_length metis moreover have "hd w = \<alpha>" using less(thenw accepts_epsilon_inters (inters_\<epsilon>s1) ultimately show?java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for lengt using w'_def by force next case False note False_outer_outer_outer_outer_r_outer False show ?thesis (cases w1 \> [ case True then have same: "p1 = p2 \<and> q1 = q2" by (metis LTS.trans_star_empty less.prems(3) less.prems(4)) have "w = []" using True less(2) LTS_\<epsilonty_emptyto then show ?thesis using less True by (simp add: LTS_\<epsilon>.trans_star_\<epsilon>.trans_star_\<epsilon>_refl same) next case False note False_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 have assumesq) ∈ (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.StringIndexOutOfBoundsExcept 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_ε_ 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 ( moreover have "(p1, w1, p2) ∈ LTS.trans_star ts1" using p'_p by simp moreover have 2',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 then obtain 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) then obtain 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_c 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 from 2( ()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 then obtain 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 γ, q 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_trans_star_ε_iff: "((p1,q2), w :: 'label list, (p2,q2)) ∈ LTS_ε.trans_star_ε (inters_ε ts1 ts2) ⟷ (p1, w, p2) ∈ LTS_ε.trans_star_ε ts1 ∧ (q2, w, q2) ∈ LTS_ε.trans_star_ε ts2" by (metis fst_conv inters_trans_star_ε inters_trans_star_ε1 snd_conv trans_star_ε_i 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 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 (lan 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 LTS_ε_of_LTS_Some: "(p, Some γ, q') ∈ LTS_ε_of_LTS A2' ⟷ (p, γ, q') ∈ A2'" unfolding LTS_ε_of_LTS_def ε_edge_of_edge_def by (auto simp add: rev_image_eqI) lemma LTS_ε_of_LTS_None: "(p, None, q') ∉ LTS_ε_of_LTS A2'" unfolding LTS_ε_of_LTS_def ε_edge_of_edge_def by (auto) 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 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 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 ==> 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 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 theorem dual_star_correct_early_termination_configs: assumes "inits ⊆ LTS.srcs A1" assumes "inits ⊆ LTS.srcs A2" assumes "isols ⊆ LTS.isolated A1" assumes "isols ⊆ LTS.isolated A2" assumes "lang_ε A1 = {c1}" assumes "lang A2 = {c2}" assumes "post_star_rules** A1 A1'" assumes "pre_star_rule** A2 A2'" assumes "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {}" shows "c1 ==>* c2" using dual_star_correct_early_termination assms by (metis singletonD) theorem dual_star_correct_saturation_configs: assumes "inits ⊆ LTS.srcs A1" assumes "inits ⊆ LTS.srcs A2" assumes "isols ⊆ LTS.isolated A1" assumes "isols ⊆ LTS.isolated A2" assumes "lang_ε A1 = {c1}" assumes "lang A2 = {c2}" assumes "saturation post_star_rules A1 A1'" assumes "saturation pre_star_rule A2 A2'" shows "lang_ε_inters (inters_ε A1' (LTS_ε_of_LTS A2')) ≠ {} ⟷ c1 ==>* c2" using assms dual_star_correct_saturation by auto end end
¤ Dauer der Verarbeitung: 0.81 Sekunden (vorverarbeitet am 2026-06-13) ¤*© Formatika GbR, Deutschland |
|
||||||||||||||
2026-06-12