Theory TIGER_Lexer.TIGER_Pred_Algebra

(* 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)) ⟷ (∃S0 μ0. (S0, μ0) ∈ set (minterms P) ∧
    ((S, μ) = (insert p S0, conj p μ0) ∧ sat (conj p μ0) ∨
     (S, μ) = (S0, 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 S0 μ0 where ‹(S0, μ0) ∈ set (minterms P)›
    and new: ‹(S, μ) = (insert p S0, conj p μ0) ∧ sat (conj p μ0) ∨
      (S, μ) = (S0, conj (neg p) μ0) ∧ sat (conj (neg p) μ0)›
    by auto
  with Cons.IH have old: ‹S0 ⊆ set P› ‹∀c. sem μ0 c ⟷ S0 = {q ∈ set P. sem q c}›
    by auto
  from new show ?case
  proof (elim disjE conjE)
    assume ‹(S, μ) = (insert p S0, conj p μ0)› ‹sat (conj p μ0)›
    moreover from ‹sat (conj p μ0)› old obtain e
      where ‹sem p e› ‹S0 = {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, μ) = (S0, conj (neg p) μ0)› ‹sat (conj (neg p) μ0)›
    moreover from ‹sat (conj (neg p) μ0)› old obtain e
      where ‹¬ sem p e› ‹S0 = {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 ‹2k›
  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