Theory TIGER_Lexer.TIGER_Pred_Algebra
theory TIGER_Pred_Algebra
imports TIGER_Regex
begin
section ‹Effective Boolean algebras of predicates›
text ‹An effective Boolean algebra on the predicates ‹'p› has a top and a bottom
predicate, conjunction, disjunction, negation and a satisfiability test, all sound for
the denotation ‹sem› \<^cite>‹‹Sect.~2› in "dantoni2014-minimization-symbolic-automata"›.
The generator needs it to compute the minterms of the atoms of a mode.
Equality of predicates is HOL equality, so it is syntactic. Equal predicates denote the
same set, but predicates with the same denotation need not be equal (the generator
never needs the converse).›
locale eba = symbolic sem
for sem :: ‹'p ⇒ 'ch ⇒ bool› +
fixes top :: 'p
and bot :: 'p
and conj :: ‹'p ⇒ 'p ⇒ 'p›
and disj :: ‹'p ⇒ 'p ⇒ 'p›
and neg :: ‹'p ⇒ 'p›
and sat :: ‹'p ⇒ bool›
assumes sem_top[simp]: ‹sem top c›
and sem_bot[simp]: ‹¬ sem bot c›
and sem_conj[simp]: ‹sem (conj p q) c ⟷ sem p c ∧ sem q c›
and sem_disj[simp]: ‹sem (disj p q) c ⟷ sem p c ∨ sem q c›
and sem_neg[simp]: ‹sem (neg p) c ⟷ ¬ sem p c›
and sat_iff: ‹sat p ⟷ (∃c. sem p c)›
begin
text ‹The test ‹sat› is dv14's ‹IsSat›. A minterm is satisfiable when some character
satisfies all its conjuncts:›
lemma sat_conj_iff: ‹sat (conj p q) ⟷ (∃c. sem p c ∧ sem q c)›
by (simp add: sat_iff)
subsection ‹Minterms›
text ‹The minterms of a list ‹P› of predicates are the satisfiable conjunctions of
each predicate of ‹P› or its negation. Each entry pairs its signature (the
predicates taken positively) with the conjunction. The recursion is the minterm tree
of \<^cite>‹‹Fig.~2› in "dantoni2014-minimization-symbolic-automata"›, refined by the
predicates from the last to the first. A leaf is split by ‹p› into ‹p ∧ μ› and
‹¬ p ∧ μ›, and the unsatisfiable parts are pruned (the paper keeps an unsplit
leaf instead, which denotes the same set).›
primrec minterms :: ‹'p list ⇒ ('p set × 'p) list› where
minterms_Nil: ‹minterms [] = [({}, top)]›
| minterms_Cons: ‹minterms (p # P) = concat (map (λ(S, μ).
filter (sat ∘ snd) [(insert p S, conj p μ), (S, conj (neg p) μ)]) (minterms P))›
lemma mem_minterms_Cons[simp]:
‹(S, μ) ∈ set (minterms (p # P)) ⟷ (∃S⇩0 μ⇩0. (S⇩0, μ⇩0) ∈ set (minterms P) ∧
((S, μ) = (insert p S⇩0, conj p μ⇩0) ∧ sat (conj p μ⇩0) ∨
(S, μ) = (S⇩0, conj (neg p) μ⇩0) ∧ sat (conj (neg p) μ⇩0)))›
by (auto split: if_splits)
declare minterms_Cons[simp del]
text ‹An entry denotes exactly the characters whose signature in ‹P› is its own.
This is the invariant behind the four properties below:›
lemma sem_minterm_iff:
assumes ‹(S, μ) ∈ set (minterms P)›
shows ‹sat μ ∧ S ⊆ set P ∧ (∀c. sem μ c ⟷ S = {p ∈ set P. sem p c})›
using assms
proof (induction P arbitrary: S μ)
case (Cons p P)
then obtain S⇩0 μ⇩0 where ‹(S⇩0, μ⇩0) ∈ set (minterms P)›
and new: ‹(S, μ) = (insert p S⇩0, conj p μ⇩0) ∧ sat (conj p μ⇩0) ∨
(S, μ) = (S⇩0, conj (neg p) μ⇩0) ∧ sat (conj (neg p) μ⇩0)›
by auto
with Cons.IH have old: ‹S⇩0 ⊆ set P› ‹∀c. sem μ⇩0 c ⟷ S⇩0 = {q ∈ set P. sem q c}›
by auto
from new show ?case
proof (elim disjE conjE)
assume ‹(S, μ) = (insert p S⇩0, conj p μ⇩0)› ‹sat (conj p μ⇩0)›
moreover from ‹sat (conj p μ⇩0)› old obtain e
where ‹sem p e› ‹S⇩0 = {q ∈ set P. sem q e}›
by (auto simp: sat_iff)
ultimately show ?thesis
using old by (auto simp: set_eq_iff)
next
assume ‹(S, μ) = (S⇩0, conj (neg p) μ⇩0)› ‹sat (conj (neg p) μ⇩0)›
moreover from ‹sat (conj (neg p) μ⇩0)› old obtain e
where ‹¬ sem p e› ‹S⇩0 = {q ∈ set P. sem q e}›
by (auto simp: sat_iff)
ultimately show ?thesis
using old by (auto simp: set_eq_iff)
qed
qed (auto simp: sat_iff[of top])
text ‹The minterms cover the alphabet, are pairwise disjoint, have exact signatures and
are satisfiable. Together they make the minterms a partition of the alphabet into the
classes of characters with the same signature
\<^cite>‹‹Sect.~4, Fig.~2› in "dantoni2014-minimization-symbolic-automata"›:›
lemma minterms_cover: ‹∃S μ. (S, μ) ∈ set (minterms P) ∧ sem μ c›
proof (induction P)
case (Cons p P)
then obtain S μ where ‹(S, μ) ∈ set (minterms P)› ‹sem μ c›
by blast
then show ?case
proof (cases ‹sem p c›)
case True
with ‹(S, μ) ∈ set (minterms P)› ‹sem μ c›
have ‹(insert p S, conj p μ) ∈ set (minterms (p # P))›
unfolding mem_minterms_Cons sat_conj_iff by blast
with True ‹sem μ c› show ?thesis
by (metis sem_conj)
next
case False
with ‹(S, μ) ∈ set (minterms P)› ‹sem μ c›
have ‹(S, conj (neg p) μ) ∈ set (minterms (p # P))›
unfolding mem_minterms_Cons sat_conj_iff sem_neg by blast
with False ‹sem μ c› show ?thesis
by (metis sem_conj sem_neg)
qed
qed simp
lemma sorted_wrt_concat_map:
assumes ‹sorted_wrt R xs› ‹⋀x. x ∈ set xs ⟹ sorted_wrt R (f x)›
and ‹⋀x y u v. ⟦ R x y; u ∈ set (f x); v ∈ set (f y) ⟧ ⟹ R u v›
shows ‹sorted_wrt R (concat (map f xs))›
using assms by (induction xs) (auto simp: sorted_wrt_append)
lemma minterms_sorted_wrt:
‹sorted_wrt (λx y. ∀c. ¬ (sem (snd x) c ∧ sem (snd y) c)) (minterms P)›
proof (induction P)
case (Cons p P)
let ?R = ‹λx y. ∀c. ¬ (sem (snd x) c ∧ sem (snd y) c)›
let ?f = ‹λ(S, μ). filter (sat ∘ snd) [(insert p S, conj p μ), (S, conj (neg p) μ)]›
have sub: ‹⟦ u ∈ set (?f x); sem (snd u) c ⟧ ⟹ sem (snd x) c› for u x c
by (cases x) (auto split: if_splits)
have sorted_f: ‹sorted_wrt ?R (?f x)› for x
by (cases x) (auto intro!: sorted_wrt_filter)
have cross: ‹⟦ ?R x y; u ∈ set (?f x); v ∈ set (?f y) ⟧ ⟹ ?R u v› for x y u v
using sub by blast
show ?case
using sorted_wrt_concat_map[OF Cons.IH sorted_f cross] by (simp add: minterms_Cons)
qed simp
lemma minterms_disjoint:
assumes ‹i < length (minterms P)› ‹j < length (minterms P)›
and ‹sem (snd (minterms P ! i)) c› ‹sem (snd (minterms P ! j)) c›
shows ‹i = j›
using minterms_sorted_wrt[of P] assms
by (cases i j rule: linorder_cases; auto simp: sorted_wrt_iff_nth_less)
lemma minterms_exact: ‹⟦ (S, μ) ∈ set (minterms P); sem μ c ⟧ ⟹ S = {p ∈ set P. sem p c}›
using sem_minterm_iff by blast
lemma minterms_sat: ‹(S, μ) ∈ set (minterms P) ⟹ sat μ›
using sem_minterm_iff by blast
text ‹The partial derivatives by all characters of one minterm are equal, and equal
to the partial derivative by its signature, as long as the minterms are taken over a
superset of the atoms \<^cite>‹‹Lemma~9, Thm.~12› in "keil2014-symbolic-regex-inequalities"›:›
lemma pderiv_eq_pderiv_cls_minterm:
assumes ‹atoms r ⊆ set P› ‹(S, μ) ∈ set (minterms P)› ‹sem μ c›
shows ‹pderiv c r = pderiv_cls S r›
proof -
from assms have ‹sig r c = S ∩ atoms r›
by (auto simp: sig_def dest: minterms_exact)
then show ?thesis
by (simp add: pderiv_eq_pderiv_cls_sig pderiv_cls_Int_atoms)
qed
text ‹The number of minterms is exponential in the length of ‹P› in the worst case.
For the bit predicates ‹β⇩i› (the characters whose ‹i›-th bit is set), every
signature is realized by exactly one character, so ‹k› predicates have ‹2⇧k›
minterms \<^cite>‹‹Ex.~2› in "dantoni2014-minimization-symbolic-automata"›. A mode with
many overlapping classes needs local minterms (minterms of the atoms that a DFA state
can read, rather than of the whole mode). D'Antoni and Veanes compute local minterms to
avoid the global partition when they minimize a symbolic automaton
\<^cite>‹‹Sect.~5› in "dantoni2014-minimization-symbolic-automata"›; here they
would serve DFA construction.›
end
end