(* Author: Basil Fürer *) 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