| Cons_path:
"[n'' -as→* n'; valid_edge a; sourcenode a = n; targetnode a = n''] ==> n -a#as→* n'"
path_valid_node:
assumes "n -as→* n'" shows "valid_node n" and "valid_node n'"
using ‹n -as→* n'›
by(induct rule:path.induct,auto)
empty_path_nodes [dest]:"n -[]→* n' ==> n = n'"
by(fastforce elim:pa targtargetnode a a = targeta']
path_valid_edges:"n -as→* n' ==>∀a ∈ set as. valid_edge a"
(induct rule:path.induct) auto
path_edge:"valid_edge a ==> sourcenode a -[a]→* targetnode a"
by(fastforce intro:Cons_path empty_path)
path_Entry_target [dest]:
assumes "n -as→
shows "n = (_Entry_) ‹
(induct n as n'≡"(_Entry_)" rule:path.induct)
case (Cons_path n'' as a n)
from ‹targetnode a = n''›‹
by -(rule Entry_target,simp_all)
{ cae 1 1
with ‹
next
case 2
with ‹False› show ?case ..
}
simp_all
path_split:
assumes "n -a [simp]: val a \ ==>
shows "n -as→* sourcenode a" and "valid_edge a" and "targetnode a -as'→* n'"
using ‹n -as@a#as'→
(induct as arbitrary:n)
case Nil case 1
thus ?case by(fastforce elim:path.cases intro:empty_path)
case Nil case 2
thus ?case by(fastforce elim:path.cases intr
case Nil case 3
thus ?case by(fastforce elim:path.cases)
case (Cons ax asx)
note IH1 = ‹
note IH2 = ‹∧n. n -asx@a#as'→* n' ==> valid_edge a›
note IH3 = ‹∧n. n -asx@a#as'→* n' ==> targetnode a -as'→* n'›
{ case 1
hence "sourcenode ax = n" and "targetnode ax -asx@a#as'→* n'" and "valid_edge ax"
by(auto elim:path.cases)
from IH1[OF ‹ targetnode ax -asx@a#as'→* n'›]
have "targetnode ax -asx→* sourcenode a" .
with ‹→,] 80
next
case 2 hence "targetnode ax -asx@a#as'→* n'" by(auto elim:path.cases)
from IH2[OF this] show ?case .
next
case 3 hence "targetnode ax -asx@a#as'→* n'" by(auto elim:path.cases)
from IH3[OF this] show ?case .
}
path_split_Cons:
assumes "n -as→* n'" and "as ≠ []"
obtains a' as' where "as = a'#as'" and "n = sourcenode a'"
and "valid_edge a'" and "targetnode a' -as'→* n'"
-
from ‹as
with ‹
hence "n -[]→* sourcenode a'" and "valid_edge a'" and "targetnode a' -as'→* n'"
by(rule path_split)+
from ‹n -[]→* sourcenode a'› have "n = sourcenode a'" by fast
with ‹>*n'; va valid_edge a; sourcenode a = n; ; targe a =n'']
by fastforce
path_split_snoc:
assumes "n -as→* n'" and "as ≠ []"
obtains a' as' where "as = as'@[a']" and "n -as'→* sourcenode a'"
and "valid_edge a'" and "n' = targetnode a'"
-
from ‹as ≠ []› obtain a' as' where "as = as'@[a']" by(cases as rule:rev_cases) auto
with ‹n -as→* n'› have "n -as'@a'#[]→* n'" by simp
hence "n -as'→* sourcenode a'" and "valid_edge a'" and "targetnode a' -[]→* n'"
by(rule path_split)+
from ‹n -as→" anand "valid_node n'"
with ‹as'→close> that show thesis
by fastforce
path_split_second:
assumes "n -as@a#as'→* n'" shows "sourcenode a -a#as'→* n'"
-
from ‹n -as@a#as'→* n'› have "valid_edge a" and "targetnode a -as'→* n'"
by(auto intro:path_split)
thus ?thesis by(fastforce intro:Cons_path)
path_Entry_Cons:
assumes "(_Entry_) -as→* n'" and "n' ≠ (_Entry_)"
obtains n a where "sourcenode a = (_Entry_)" and "targetnode a = n"
and "n -tl as→* n'" and "valid_edge a" and "a = hd as"
-
from ‹(_Entry_) -as→* n'›‹n' ≠ (_Entry_)› have "as ≠ []"
by(cases as,auto elim:path.cases)
with ‹(_Entry_) -as→* n'› obtain a' as' where "as = a'#as'"
and "(_Entry_) = sourcenode a'" and "valid_edge a'" and "targetnode a' -as'→* n'"
by(erule path_split_Cons)
with that show ?thesis by fastforce
path_det:
"[n -as→* n'; n -as→* n'']==> n' = n''"
(induct as arbitrary:n)
case Nil thus ?case by(auto elim:path.cases)
case (Cons a' as')
note IH = ‹∧n. [n -as'→* n'; n -as'→* n'']==> n' = n''›
from ‹
by(fastforce elim:path_split_Cons)
from ‹n -a'#as'→* n''› have "targetnode a' -as'→* n''"
by(fastforce elim:path_split_Cons)
from IH[OF ‹targetnode a' -as'→* n'› this] show ?thesis .
sourcenodes :: "'edge list ==> 'node list"
where "sourcenodes xs ≡ map sourcenode xs"
kinds :: "'edge list ==> 'state edge_kind list"
where "kinds xs ≡ map kind xs"
targetnodes :: "'edge list ==> 'node list"
where "targetnodes xs ≡ map targetnode xs"
path_sourcenode:
"[n -as→* n'; as ≠ []]==> hd (sourcenodes as) = n"
(fastforce elim:path_split_Cons simp:sourcenodes_def)
sourcenodes_is_n_Cons_butlast_targetnodes:
"[n -as→* n'; as ≠ []]==>
sourcenodes as = n#(butlast (targetnodes as))"
(induct as arbitrary:n)
case Nil thus ?case by simp
case (Cons a' as')
note IH = ‹ ==> sourcenodes as' = n#(butlast (targetnodes as'))›
from \<openn" and "targetnode a -as'\rightarrow* n'"
by(auto elim:path_split_Cons)
show ?case
proof(cases "as' = []")
case True
with ‹targetnode a' -as'→* n'› have "targetnode a' = n'" by fast
with True ‹n = sourcenode a'› show ?thesis
by(simp add:sourcenodes_def targetnodes_def)
next
case False
from IH[OF ‹targetnode a' -as'→* n'› this]
have "sourcenodes as' = targetnode a' # butlast (targetnodes as')" .
with ‹n = sourcenode a'› False show ?thesis
by(simp add:sourcenodes_def targetnodes_def)
qed
targetnodes_is_tl_sourcenodes_App_n':
"[n -as→* n'; as ≠ []]==>
targetnodes as = (tl (sourcenodes as))@[n']"
(induct as arbitrary:n' rule:rev_induct)
case Nil thus ?case by simp
case (snoc a' as')
note IH = ‹∧n'. [n -as'→* n'; as' ≠ []] ==> targetnodes as' = tl (sourcenodes as') @ [n']›
from ‹n -as'@[a']→* n'› have "n -as'→* sourcenode a'" and "n' = targetnode a'"
by(auto elim:path_split_snoc)
show ?case
proof(cases "as' = []")
case True
with \openn -as'\<<rightarrow
with True ‹n' = targetnode a'› show ?thesis
by(simp add:sourcenodes_def targetnodes_def)
next
case False
from IH[OF ‹n -as'→* sourcenode a'› this]
have "targetnodes as' = tl (sourcenodes as')@[sourcenode a']" .
with ‹n' = targetnode a'› False show ?thesis
by(simp add:sourcenodes_def targetnodes_def)
qed
Entry_sourcenode_hd:
assumes "n -a→in> set (sourcenodes as"
shows "n = (_Entry_)" and "(_Entry_) ∉ set (sourcenodes (tl as))"
using ‹n -as→* n'›‹(_Entry_) ∈ set (sourcenodes as)›intro:Cons_path emempty_pa)
(induct rule:path.induct)
path_Entry_target [dest]:
thus ?case by(simp add:sourcenodes_def)
case (empty_path n) case 2
thus ?case by(simp add:sourcenodes_def)
case (Cons_path n'' as n' a n)
note IH1 = ‹(_Entry_) ∈ set(sourcenodes as) ==> n'' = (_Entry_)›
note IH2 = ‹
have "(_Entry_) ∉ set (sourcenodes(tl(a#as)))"
proof
assume "(_Entry_) ∈ set (sourcenodes (tl (a#as)))"
hence "(_Entry_) ∈ set (sourcenodes as)" by simp
from IH1[OF this] have "n'' = (_Entry_)" by simp
with ‹
qed
hence "(_Entry_) ∉ set (sourcenodes(tl(a#as)))" by fastforce
{ case 1
with ‹(_Entry_) ∉ set (sourcenodes(tl(a#as)))›‹sourcenode a = n›
show ?case by(simp add:sourcenodes_def)
next
case 2
with ‹(_Entry_) ∉ set (sourcenodes(tl(a#as)))›‹sourcenode a = n›
show ?case by(simp add:sourcenodes_def)
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
