sig
  type var = char
  type gstring = (Kat.var, Bdd.key) Common.gstring
  val print_gstring : Kat.gstring Common.formatter
  type 's mem = ('s, Bdd.key) Bdd.mem
  type 's node = ('s, Bdd.key) Bdd.node
  type 'a span = (Kat.var, 'a) Common.span
  type test =
      Dsj of Kat.test * Kat.test
    | Cnj of Kat.test * Kat.test
    | Neg of Kat.test
    | Top
    | Bot
    | Prd of Bdd.key
  val test_to_formula : Kat.test -> Bdd.formula
  type ('o, 'e) expr_ =
      Pls of 'e * 'e
    | Dot of 'e * 'e
    | Str of 'e
    | Tst of 'o
    | Var of Kat.var
  type expr = (Kat.test, Kat.expr) Kat.expr_
  type abstr
  type expr' = Kat.abstr Common.hval
  type expr'_set = Kat.abstr Common.hset
  val hash : Kat.expr' -> int
  val head : Kat.expr' -> (Bdd.formula, Kat.expr') Kat.expr_
  val subst : (Kat.var -> Kat.expr') -> Kat.expr' -> Kat.expr'
  val vars : Kat.expr' -> Kat.var Common.set
  val pls : Kat.expr' -> Kat.expr' -> Kat.expr'
  val dot : Kat.expr' -> Kat.expr' -> Kat.expr'
  val tod : Kat.expr' -> Kat.expr' -> Kat.expr'
  val str : Kat.expr' -> Kat.expr'
  val tst : Bdd.formula -> Kat.expr'
  val var : char -> Kat.expr'
  val zer : Kat.expr'
  val one : Kat.expr'
  val expr' : Kat.expr -> Kat.expr'
  val epsilon : Kat.expr' -> Bdd.formula
  val ssf : Kat.expr' -> Kat.expr'
  val print_test : Format.formatter -> Kat.test -> unit
  val print_expr : Format.formatter -> Kat.expr -> unit
  val print_expr' : Format.formatter -> Kat.expr' -> unit
  val random_expr : Bdd.key list -> Kat.var list -> int -> unit -> Kat.expr
  val random_full_expr :
    Bdd.key list -> Kat.var list -> int -> unit -> Kat.expr
end