Theory ParityGame
section ‹Parity Games›
theory ParityGame
imports
Main
MoreCoinductiveList
begin
subsection ‹Basic definitions›
text ‹@{typ "'a"} is the node type. Edges are pairs of nodes.›
type_synonym 'a Edge = "'a × 'a"
text ‹A path is a possibly infinite list of nodes.›
type_synonym 'a Path = "'a llist"
subsection ‹Graphs›
text ‹
We define graphs as a locale over a record.
The record contains nodes (AKA vertices) and edges.
The locale adds the assumption that the edges are pairs of nodes.
›
record 'a Graph =
verts :: "'a set" ("Vı")
arcs :: "'a Edge set" ("Eı")
abbreviation is_arc :: "('a, 'b) Graph_scheme ⇒ 'a ⇒ 'a ⇒ bool" (infixl "→ı" 60) where
"v →⇘G⇙ w ≡ (v,w) ∈ E⇘G⇙"
locale Digraph =
fixes G (structure)
assumes valid_edge_set: "E ⊆ V × V"
begin
lemma edges_are_in_V [intro]: "v→w ⟹ v ∈ V" "v→w ⟹ w ∈ V" using valid_edge_set by blast+
text ‹A node without successors is a \emph{deadend}.›
abbreviation deadend :: "'a ⇒ bool" where "deadend v ≡ ¬(∃w ∈ V. v → w)"
subsection ‹Valid Paths›
text ‹
We say that a path is \emph{valid} if it is empty or if it starts in @{term V} and walks along edges.
›
coinductive valid_path :: "'a Path ⇒ bool" where
valid_path_base: "valid_path LNil"
| valid_path_base': "v ∈ V ⟹ valid_path (LCons v LNil)"
| valid_path_cons: "⟦ v ∈ V; w ∈ V; v→w; valid_path Ps; ¬lnull Ps; lhd Ps = w ⟧
⟹ valid_path (LCons v Ps)"
inductive_simps valid_path_cons_simp: "valid_path (LCons x xs)"
lemma valid_path_ltl': "valid_path (LCons v Ps) ⟹ valid_path Ps"
using valid_path.simps by blast
lemma valid_path_ltl: "valid_path P ⟹ valid_path (ltl P)"
by (metis llist.exhaust_sel ltl_simps(1) valid_path_ltl')
lemma valid_path_drop: "valid_path P ⟹ valid_path (ldropn n P)"
by (simp add: valid_path_ltl ltl_ldrop)
lemma valid_path_in_V: assumes "valid_path P" shows "lset P ⊆ V" proof
fix x assume "x ∈ lset P" thus "x ∈ V"
using assms by (induct rule: llist.set_induct) (auto intro: valid_path.cases)
qed
lemma valid_path_finite_in_V: "⟦ valid_path P; enat n < llength P ⟧ ⟹ P $ n ∈ V"
using valid_path_in_V lset_lnth_member by blast
lemma valid_path_edges': "valid_path (LCons v (LCons w Ps)) ⟹ v→w"
using valid_path.cases by fastforce
lemma valid_path_edges:
assumes "valid_path P" "enat (Suc n) < llength P"
shows "P $ n → P $ Suc n"
proof-
define P' where "P' = ldropn n P"
have "enat n < llength P" using assms(2) enat_ord_simps(2) less_trans by blast
hence "P' $ 0 = P $ n" by (simp add: P'_def)
moreover have "P' $ Suc 0 = P $ Suc n"
by (metis One_nat_def P'_def Suc_eq_plus1 add.commute assms(2) lnth_ldropn)
ultimately have "∃Ps. P' = LCons (P $ n) (LCons (P $ Suc n) Ps)"
by (metis P'_def ‹enat n < llength P› assms(2) ldropn_Suc_conv_ldropn)
moreover have "valid_path P'" by (simp add: P'_def assms(1) valid_path_drop)
ultimately show ?thesis using valid_path_edges' by blast
qed
lemma valid_path_coinduct [consumes 1, case_names base step, coinduct pred: valid_path]:
assumes major: "Q P"
and base: "⋀v P. Q (LCons v LNil) ⟹ v ∈ V"
and step: "⋀v w P. Q (LCons v (LCons w P)) ⟹ v→w ∧ (Q (LCons w P) ∨ valid_path (LCons w P))"
shows "valid_path P"
using major proof (coinduction arbitrary: P)
case valid_path
{ assume "P ≠ LNil" "¬(∃v. P = LCons v LNil ∧ v ∈ V)"
then obtain v w P' where "P = LCons v (LCons w P')"
using neq_LNil_conv base valid_path by metis
hence ?case using step valid_path by auto
}
thus ?case by blast
qed
lemma valid_path_no_deadends:
"⟦ valid_path P; enat (Suc i) < llength P ⟧ ⟹ ¬deadend (P $ i)"
using valid_path_edges by blast
lemma valid_path_ends_on_deadend:
"⟦ valid_path P; enat i < llength P; deadend (P $ i) ⟧ ⟹ enat (Suc i) = llength P"
using valid_path_no_deadends by (metis enat_iless enat_ord_simps(2) neq_iff not_less_eq)
lemma valid_path_prefix: "⟦ valid_path P; lprefix P' P ⟧ ⟹ valid_path P'"
proof (coinduction arbitrary: P' P)
case (step v w P'' P' P)
then obtain Ps where Ps: "LCons v (LCons w Ps) = P" by (metis LCons_lprefix_conv)
hence "valid_path (LCons w Ps)" using valid_path_ltl' step(2) by blast
moreover have "lprefix (LCons w P'') (LCons w Ps)" using Ps step(1,3) by auto
ultimately show ?case using Ps step(2) valid_path_edges' by blast
qed (metis LCons_lprefix_conv valid_path_cons_simp)
lemma valid_path_lappend:
assumes "valid_path P" "valid_path P'" "⟦ ¬lnull P; ¬lnull P' ⟧ ⟹ llast P→lhd P'"
shows "valid_path (lappend P P')"
proof (cases, cases)
assume "¬lnull P" "¬lnull P'"
thus ?thesis using assms proof (coinduction arbitrary: P' P)
case (step v w P'' P' P)
show ?case proof (cases)
assume "lnull (ltl P)"
thus ?case using step(1,2,3,5,6)
by (metis lhd_LCons lhd_LCons_ltl lhd_lappend llast_singleton
llist.collapse(1) ltl_lappend ltl_simps(2))
next
assume "¬lnull (ltl P)"
moreover have "ltl (lappend P P') = lappend (ltl P) P'" using step(2) by simp
ultimately show ?case using step
by (metis (no_types, lifting)
lhd_LCons lhd_LCons_ltl lhd_lappend llast_LCons ltl_simps(2)
valid_path_edges' valid_path_ltl)
qed
qed (metis llist.disc(1) lnull_lappend ltl_lappend ltl_simps(2))
qed (simp_all add: assms(1,2) lappend_lnull1 lappend_lnull2)
text ‹A valid path is still valid in a supergame.›
lemma valid_path_supergame:
assumes "valid_path P" and G': "Digraph G'" "V ⊆ V⇘G'⇙" "E ⊆ E⇘G'⇙"
shows "Digraph.valid_path G' P"
using ‹valid_path P› proof (coinduction arbitrary: P
rule: Digraph.valid_path_coinduct[OF G'(1), case_names base step])
case base thus ?case using G'(2) valid_path_cons_simp by auto
qed (meson G'(3) subset_eq valid_path_edges' valid_path_ltl')
subsection ‹Maximal Paths›
text ‹
We say that a path is \emph{maximal} if it is empty or if it ends in a deadend.
›
coinductive maximal_path where
maximal_path_base: "maximal_path LNil"
| maximal_path_base': "deadend v ⟹ maximal_path (LCons v LNil)"
| maximal_path_cons: "¬lnull Ps ⟹ maximal_path Ps ⟹ maximal_path (LCons v Ps)"
lemma maximal_no_deadend: "maximal_path (LCons v Ps) ⟹ ¬deadend v ⟹ ¬lnull Ps"
by (metis lhd_LCons llist.distinct(1) ltl_simps(2) maximal_path.simps)
lemma maximal_ltl: "maximal_path P ⟹ maximal_path (ltl P)"
by (metis ltl_simps(1) ltl_simps(2) maximal_path.simps)
lemma maximal_drop: "maximal_path P ⟹ maximal_path (ldropn n P)"
by (simp add: maximal_ltl ltl_ldrop)
lemma maximal_path_lappend:
assumes "¬lnull P'" "maximal_path P'"
shows "maximal_path (lappend P P')"
proof (cases)
assume "¬lnull P"
thus ?thesis using assms proof (coinduction arbitrary: P' P rule: maximal_path.coinduct)
case (maximal_path P' P)
let ?P = "lappend P P'"
show ?case proof (cases "?P = LNil ∨ (∃v. ?P = LCons v LNil ∧ deadend v)")
case False
then obtain Ps v where P: "?P = LCons v Ps" by (meson neq_LNil_conv)
hence "Ps = lappend (ltl P) P'" by (simp add: lappend_ltl maximal_path(1))
hence "∃Ps1 P'. Ps = lappend Ps1 P' ∧ ¬lnull P' ∧ maximal_path P'"
using maximal_path(2) maximal_path(3) by auto
thus ?thesis using P lappend_lnull1 by fastforce
qed blast
qed
qed (simp add: assms(2) lappend_lnull1[of P P'])
lemma maximal_ends_on_deadend:
assumes "maximal_path P" "lfinite P" "¬lnull P"
shows "deadend (llast P)"
proof-
from ‹lfinite P› ‹¬lnull P› obtain n where n: "llength P = enat (Suc n)"
by (metis enat_ord_simps(2) gr0_implies_Suc lfinite_llength_enat lnull_0_llength)
define P' where "P' = ldropn n P"
hence "maximal_path P'" using assms(1) maximal_drop by blast
thus ?thesis proof (cases rule: maximal_path.cases)
case (maximal_path_base' v)
hence "deadend (llast P')" unfolding P'_def by simp
thus ?thesis unfolding P'_def using llast_ldropn[of n P] n
by (metis P'_def ldropn_eq_LConsD local.maximal_path_base'(1))
next
case (maximal_path_cons P'' v)
hence "ldropn (Suc n) P = P''" unfolding P'_def by (metis ldrop_eSuc_ltl ltl_ldropn ltl_simps(2))
thus ?thesis using n maximal_path_cons(2) by auto
qed (simp add: P'_def n ldropn_eq_LNil)
qed
lemma maximal_ends_on_deadend': "⟦ lfinite P; deadend (llast P) ⟧ ⟹ maximal_path P"
proof (coinduction arbitrary: P rule: maximal_path.coinduct)
case (maximal_path P)
show ?case proof (cases)
assume "P ≠ LNil"
then obtain v P' where P': "P = LCons v P'" by (meson neq_LNil_conv)
show ?thesis proof (cases)
assume "P' = LNil" thus ?thesis using P' maximal_path(2) by auto
qed (metis P' lfinite_LCons llast_LCons llist.collapse(1) maximal_path(1,2))
qed simp
qed
lemma infinite_path_is_maximal: "⟦ valid_path P; ¬lfinite P ⟧ ⟹ maximal_path P"
by (coinduction arbitrary: P rule: maximal_path.coinduct)
(cases rule: valid_path.cases, auto)
end
subsection ‹Parity Games›
text ‹Parity games are games played by two players, called \Even and \Odd.›
datatype Player = Even | Odd
abbreviation "other_player p ≡ (if p = Even then Odd else Even)"
notation other_player ("(_**)" [1000] 1000)
lemma other_other_player [simp]: "p**** = p" using Player.exhaust by auto
text ‹
A parity game is tuple $(V,E,V_0,\omega)$, where $(V,E)$ is a graph, $V_0 \subseteq V$
and @{term ω} is a function from $V \to \mathbb{N}$ with finite image.
›
record 'a ParityGame = "'a Graph" +
player0 :: "'a set" ("V0ı")
priority :: "'a ⇒ nat" ("ωı")
locale ParityGame = Digraph G for G :: "('a, 'b) ParityGame_scheme" (structure) +
assumes valid_player0_set: "V0 ⊆ V"
and priorities_finite: "finite (ω ` V)"
begin
text ‹‹VV p› is the set of nodes belonging to player @{term p}.›
abbreviation VV :: "Player ⇒ 'a set" where "VV p ≡ (if p = Even then V0 else V - V0)"
lemma VVp_to_V [intro]: "v ∈ VV p ⟹ v ∈ V" using valid_player0_set by (cases p) auto
lemma VV_impl1: "v ∈ VV p ⟹ v ∉ VV p**" by auto
lemma VV_impl2: "v ∈ VV p** ⟹ v ∉ VV p" by auto
lemma VV_equivalence [iff]: "v ∈ V ⟹ v ∉ VV p ⟷ v ∈ VV p**" by auto
lemma VV_cases [consumes 1]: "⟦ v ∈ V ; v ∈ VV p ⟹ P ; v ∈ VV p** ⟹ P ⟧ ⟹ P" by auto
subsection ‹Sets of Deadends›
definition "deadends p ≡ {v ∈ VV p. deadend v}"
lemma deadends_in_V: "deadends p ⊆ V" unfolding deadends_def by blast
subsection ‹Subgames›
text ‹We define a subgame by restricting the set of nodes to a given subset.›
definition subgame where
"subgame V' ≡ G⦇
verts := V ∩ V',
arcs := E ∩ (V' × V'),
player0 := V0 ∩ V' ⦈"
lemma subgame_V [simp]: "V⇘subgame V'⇙ ⊆ V"
and subgame_E [simp]: "E⇘subgame V'⇙ ⊆ E"
and subgame_ω: "ω⇘subgame V'⇙ = ω"
unfolding subgame_def by simp_all
lemma
assumes "V' ⊆ V"
shows subgame_V' [simp]: "V⇘subgame V'⇙ = V'"
and subgame_E' [simp]: "E⇘subgame V'⇙ = E ∩ (V⇘subgame V'⇙ × V⇘subgame V'⇙)"
unfolding subgame_def using assms by auto
lemma subgame_VV [simp]: "ParityGame.VV (subgame V') p = V' ∩ VV p" proof-
have "ParityGame.VV (subgame V') Even = V' ∩ VV Even" unfolding subgame_def by auto
moreover have "ParityGame.VV (subgame V') Odd = V' ∩ VV Odd" proof-
have "V' ∩ V - (V0 ∩ V') = V' ∩ V ∩ (V - V0)" by blast
thus ?thesis unfolding subgame_def by auto
qed
ultimately show ?thesis by simp
qed
corollary subgame_VV_subset [simp]: "ParityGame.VV (subgame V') p ⊆ VV p" by simp
lemma subgame_finite [simp]: "finite (ω⇘subgame V'⇙ ` V⇘subgame V'⇙)" proof-
have "finite (ω ` V⇘subgame V'⇙)" using subgame_V priorities_finite
by (meson finite_subset image_mono)
thus ?thesis by (simp add: subgame_def)
qed
lemma subgame_ω_subset [simp]: "ω⇘subgame V'⇙ ` V⇘subgame V'⇙ ⊆ ω ` V"
by (simp add: image_mono subgame_ω)
lemma subgame_Digraph: "Digraph (subgame V')"
by (unfold_locales) (auto simp add: subgame_def)
lemma subgame_ParityGame:
shows "ParityGame (subgame V')"
proof (unfold_locales)
show "E⇘subgame V'⇙ ⊆ V⇘subgame V'⇙ × V⇘subgame V'⇙"
using subgame_Digraph[unfolded Digraph_def] .
show "V0⇘subgame V'⇙ ⊆ V⇘subgame V'⇙" unfolding subgame_def using valid_player0_set by auto
show "finite (ω⇘subgame V'⇙ ` V⇘subgame V'⇙)" by simp
qed
lemma subgame_valid_path:
assumes P: "valid_path P" "lset P ⊆ V'"
shows "Digraph.valid_path (subgame V') P"
proof-
have "lset P ⊆ V" using P(1) valid_path_in_V by blast
hence "lset P ⊆ V⇘subgame V'⇙" unfolding subgame_def using P(2) by auto
with P(1) show ?thesis
proof (coinduction arbitrary: P
rule: Digraph.valid_path.coinduct[OF subgame_Digraph, case_names IH])
case IH
thus ?case proof (cases rule: valid_path.cases)
case (valid_path_cons v w Ps)
moreover hence "v ∈ V⇘subgame V'⇙" "w ∈ V⇘subgame V'⇙" using IH(2) by auto
moreover hence "v →⇘subgame V'⇙ w" using local.valid_path_cons(4) subgame_def by auto
moreover have "valid_path Ps" using IH(1) valid_path_ltl' local.valid_path_cons(1) by blast
ultimately show ?thesis using IH(2) by auto
qed auto
qed
qed
lemma subgame_maximal_path:
assumes V': "V' ⊆ V" and P: "maximal_path P" "lset P ⊆ V'"
shows "Digraph.maximal_path (subgame V') P"
proof-
have "lset P ⊆ V⇘subgame V'⇙" unfolding subgame_def using P(2) V' by auto
with P(1) V' show ?thesis
by (coinduction arbitrary: P rule: Digraph.maximal_path.coinduct[OF subgame_Digraph])
(cases rule: maximal_path.cases, auto)
qed
subsection ‹Priorities Occurring Infinitely Often›
text ‹
The set of priorities that occur infinitely often on a given path. We need this to define the
winning condition of parity games.
›
definition path_inf_priorities :: "'a Path ⇒ nat set" where
"path_inf_priorities P ≡ {k. ∀n. k ∈ lset (ldropn n (lmap ω P))}"
text ‹
Because @{term ω} is image-finite, by the pigeon-hole principle every infinite path has at least
one priority that occurs infinitely often.
›
lemma path_inf_priorities_is_nonempty:
assumes P: "valid_path P" "¬lfinite P"
shows "∃k. k ∈ path_inf_priorities P"
proof-
text ‹Define a map from indices to priorities on the path.›
define f where "f i = ω (P $ i)" for i
have "range f ⊆ ω ` V" unfolding f_def
using valid_path_in_V[OF P(1)] lset_nth_member_inf[OF P(2)]
by blast
hence "finite (range f)"
using priorities_finite finite_subset by blast
then obtain n0 where n0: "¬(finite {n. f n = f n0})"
using pigeonhole_infinite[of UNIV f] by auto
define k where "k = f n0"
text ‹The priority @{term k} occurs infinitely often.›
have "lmap ω P $ n0 = k" unfolding f_def k_def
using assms(2) by (simp add: infinite_small_llength)
moreover {
fix n assume "lmap ω P $ n = k"
have "∃n' > n. f n' = k" unfolding k_def using n0 infinite_nat_iff_unbounded by auto
hence "∃n' > n. lmap ω P $ n' = k" unfolding f_def
using assms(2) by (simp add: infinite_small_llength)
}
ultimately have "∀n. k ∈ lset (ldropn n (lmap ω P))"
using index_infinite_set[of "lmap ω P" n0 k] P(2) lfinite_lmap
by blast
thus ?thesis unfolding path_inf_priorities_def by blast
qed
lemma path_inf_priorities_at_least_min_prio:
assumes P: "valid_path P" and a: "a ∈ path_inf_priorities P"
shows "Min (ω ` V) ≤ a"
proof-
have "a ∈ lset (ldropn 0 (lmap ω P))" using a unfolding path_inf_priorities_def by blast
hence "a ∈ ω ` lset P" by simp
thus ?thesis using P valid_path_in_V priorities_finite Min_le by blast
qed
lemma path_inf_priorities_LCons:
"path_inf_priorities P = path_inf_priorities (LCons v P)" (is "?A = ?B")
proof
show "?A ⊆ ?B" proof
fix a assume "a ∈ ?A"
hence "∀n. a ∈ lset (ldropn n (lmap ω (LCons v P)))"
unfolding path_inf_priorities_def
using in_lset_ltlD[of a] by (simp add: ltl_ldropn)
thus "a ∈ ?B" unfolding path_inf_priorities_def by blast
qed
next
show "?B ⊆ ?A" proof
fix a assume "a ∈ ?B"
hence "∀n. a ∈ lset (ldropn (Suc n) (lmap ω (LCons v P)))"
unfolding path_inf_priorities_def by blast
thus "a ∈ ?A" unfolding path_inf_priorities_def by simp
qed
qed
corollary path_inf_priorities_ltl: "path_inf_priorities P = path_inf_priorities (ltl P)"
by (metis llist.exhaust ltl_simps path_inf_priorities_LCons)
subsection ‹Winning Condition›
text ‹
Let $G = (V,E,V_0,\omega)$ be a parity game.
An infinite path $v_0,v_1,\ldots$ in $G$ is winning for player \Even (\Odd) if the minimum
priority occurring infinitely often is even (odd).
A finite path is winning for player @{term p} iff the last node on the path belongs to the other
player.
Empty paths are irrelevant, but it is useful to assign a fixed winner to them in order to get
simpler lemmas.
›
abbreviation "winning_priority p ≡ (if p = Even then even else odd)"
definition winning_path :: "Player ⇒ 'a Path ⇒ bool" where
"winning_path p P ≡
(¬lfinite P ∧ (∃a ∈ path_inf_priorities P.
(∀b ∈ path_inf_priorities P. a ≤ b) ∧ winning_priority p a))
∨ (¬lnull P ∧ lfinite P ∧ llast P ∈ VV p**)
∨ (lnull P ∧ p = Even)"
text ‹Every path has a unique winner.›
lemma paths_are_winning_for_one_player:
assumes "valid_path P"
shows "winning_path p P ⟷ ¬winning_path p** P"
proof (cases)
assume "¬lnull P"
show ?thesis proof (cases)
assume "lfinite P"
thus ?thesis
using assms lfinite_lset valid_path_in_V
unfolding winning_path_def
by auto
next
assume "¬lfinite P"
then obtain a where "a ∈ path_inf_priorities P" "⋀b. b < a ⟹ b ∉ path_inf_priorities P"
using assms ex_least_nat_le[of "λa. a ∈ path_inf_priorities P"] path_inf_priorities_is_nonempty
by blast
hence "∀q. winning_priority q a ⟷ winning_path q P"
unfolding winning_path_def using ‹¬lnull P› ‹¬lfinite P› by (metis le_antisym not_le)
moreover have "∀q. winning_priority p q ⟷ ¬winning_priority p** q" by simp
ultimately show ?thesis by blast
qed
qed (simp add: winning_path_def)
lemma winning_path_ltl:
assumes P: "winning_path p P" "¬lnull P" "¬lnull (ltl P)"
shows "winning_path p (ltl P)"
proof (cases)
assume "lfinite P"
moreover have "llast P = llast (ltl P)"
using P(2,3) by (metis llast_LCons2 ltl_simps(2) not_lnull_conv)
ultimately show ?thesis using P by (simp add: winning_path_def)
next
assume "¬lfinite P"
thus ?thesis using winning_path_def path_inf_priorities_ltl P(1,2) by auto
qed
corollary winning_path_drop:
assumes "winning_path p P" "enat n < llength P"
shows "winning_path p (ldropn n P)"
using assms proof (induct n)
case (Suc n)
hence "winning_path p (ldropn n P)" using dual_order.strict_trans enat_ord_simps(2) by blast
moreover have "ltl (ldropn n P) = ldropn (Suc n) P" by (simp add: ldrop_eSuc_ltl ltl_ldropn)
moreover hence "¬lnull (ldropn n P)" using Suc.prems(2) by (metis leD lnull_ldropn lnull_ltlI)
ultimately show ?case using winning_path_ltl[of p "ldropn n P"] Suc.prems(2) by auto
qed simp
corollary winning_path_drop_add:
assumes "valid_path P" "winning_path p (ldropn n P)" "enat n < llength P"
shows "winning_path p P"
using assms paths_are_winning_for_one_player valid_path_drop winning_path_drop by blast
lemma winning_path_LCons:
assumes P: "winning_path p P" "¬lnull P"
shows "winning_path p (LCons v P)"
proof (cases)
assume "lfinite P"
moreover have "llast P = llast (LCons v P)"
using P(2) by (metis llast_LCons2 not_lnull_conv)
ultimately show ?thesis using P unfolding winning_path_def by simp
next
assume "¬lfinite P"
thus ?thesis using P path_inf_priorities_LCons unfolding winning_path_def by simp
qed
lemma winning_path_supergame:
assumes "winning_path p P"
and G': "ParityGame G'" "VV p** ⊆ ParityGame.VV G' p**" "ω = ω⇘G'⇙"
shows "ParityGame.winning_path G' p P"
proof-
interpret G': ParityGame G' using G'(1) .
have "⟦ lfinite P; ¬lnull P ⟧ ⟹ llast P ∈ G'.VV p**" and "lnull P ⟹ p = Even"
using assms(1) unfolding winning_path_def using G'(2) by auto
thus ?thesis unfolding G'.winning_path_def
using lnull_imp_lfinite assms(1)
unfolding winning_path_def path_inf_priorities_def G'.path_inf_priorities_def G'(3)
by blast
qed
end
subsection ‹Valid Maximal Paths›
text ‹Define a locale for valid maximal paths, because we need them often.›
locale vm_path = ParityGame +
fixes P v0
assumes P_not_null [simp]: "¬lnull P"
and P_valid [simp]: "valid_path P"
and P_maximal [simp]: "maximal_path P"
and P_v0 [simp]: "lhd P = v0"
begin
lemma P_LCons: "P = LCons v0 (ltl P)" using lhd_LCons_ltl[OF P_not_null] by simp
lemma P_len [simp]: "enat 0 < llength P" by (simp add: lnull_0_llength)
lemma P_0 [simp]: "P $ 0 = v0" by (simp add: lnth_0_conv_lhd)
lemma P_lnth_Suc: "P $ Suc n = ltl P $ n" by (simp add: lnth_ltl)
lemma P_no_deadends: "enat (Suc n) < llength P ⟹ ¬deadend (P $ n)"
using valid_path_no_deadends by simp
lemma P_no_deadend_v0: "¬lnull (ltl P) ⟹ ¬deadend v0"
by (metis P_LCons P_valid edges_are_in_V(2) not_lnull_conv valid_path_edges')
lemma P_no_deadend_v0_llength: "enat (Suc n) < llength P ⟹ ¬deadend v0"
by (metis P_0 P_len P_valid enat_ord_simps(2) not_less_eq valid_path_ends_on_deadend zero_less_Suc)
lemma P_ends_on_deadend: "⟦ enat n < llength P; deadend (P $ n) ⟧ ⟹ enat (Suc n) = llength P"
using P_valid valid_path_ends_on_deadend by blast
lemma P_lnull_ltl_deadend_v0: "lnull (ltl P) ⟹ deadend v0"
using P_LCons maximal_no_deadend by force
lemma P_lnull_ltl_LCons: "lnull (ltl P) ⟹ P = LCons v0 LNil"
using P_LCons lnull_def by metis
lemma P_deadend_v0_LCons: "deadend v0 ⟹ P = LCons v0 LNil"
using P_lnull_ltl_LCons P_no_deadend_v0 by blast
lemma Ptl_valid [simp]: "valid_path (ltl P)" using valid_path_ltl by auto
lemma Ptl_maximal [simp]: "maximal_path (ltl P)" using maximal_ltl by auto
lemma Pdrop_valid [simp]: "valid_path (ldropn n P)" using valid_path_drop by auto
lemma Pdrop_maximal [simp]: "maximal_path (ldropn n P)" using maximal_drop by auto
lemma prefix_valid [simp]: "valid_path (ltake n P)"
using valid_path_prefix[of P] by auto
lemma extension_valid [simp]: "v→v0 ⟹ valid_path (LCons v P)"
using P_not_null P_v0 P_valid valid_path_cons by blast
lemma extension_maximal [simp]: "maximal_path (LCons v P)"
by (simp add: maximal_path_cons)
lemma lappend_maximal [simp]: "maximal_path (lappend P' P)"
by (simp add: maximal_path_lappend)
lemma v0_V [simp]: "v0 ∈ V" by (metis P_LCons P_valid valid_path_cons_simp)
lemma v0_lset_P [simp]: "v0 ∈ lset P" using P_not_null P_v0 llist.set_sel(1) by blast
lemma v0_VV: "v0 ∈ VV p ∨ v0 ∈ VV p**" by simp
lemma lset_P_V [simp]: "lset P ⊆ V" by (simp add: valid_path_in_V)
lemma lset_ltl_P_V [simp]: "lset (ltl P) ⊆ V" by (simp add: valid_path_in_V)
lemma finite_llast_deadend [simp]: "lfinite P ⟹ deadend (llast P)"
using P_maximal P_not_null maximal_ends_on_deadend by blast
lemma finite_llast_V [simp]: "lfinite P ⟹ llast P ∈ V"
using P_not_null lfinite_lset lset_P_V by blast
text ‹If a path visits a deadend, it is winning for the other player.›
lemma visits_deadend:
assumes "lset P ∩ deadends p ≠ {}"
shows "winning_path p** P"
proof-
obtain n where n: "enat n < llength P" "P $ n ∈ deadends p"
using assms by (meson lset_intersect_lnth)
hence *: "enat (Suc n) = llength P" using P_ends_on_deadend unfolding deadends_def by blast
hence "llast P = P $ n" by (simp add: eSuc_enat llast_conv_lnth)
hence "llast P ∈ deadends p" using n(2) by simp
moreover have "lfinite P" using * llength_eq_enat_lfiniteD by force
ultimately show ?thesis unfolding winning_path_def deadends_def by auto
qed
end
end