ata.mli

   1 type state = int
   2 val mk_state : unit -> state
   3
   4 type formula_expr =
   5     False
   6   | True
   7   | Or of formula * formula
   8   | And of formula * formula
   9   | Atom of ([ `Left | `Right | `LLeft | `RRight ] * bool * state)
  10 and formula = { fid : int; fkey : int; pos : formula_expr; neg : formula; st : (Ptset.t*Ptset.t*Ptset.t)*(Ptset.t*Ptset.t*Ptset.t); size: int;}
  11 val true_ : formula
  12 val false_ : formula
  13 val atom_ : [`Left | `Right | `LLeft | `RRight ] -> bool -> state -> formula
  14 val and_ : formula -> formula -> formula
  15 val or_ : formula -> formula -> formula
  16 val not_ : formula -> formula
  17 (*val equal_form : formula -> formula -> bool *)
  18 val pr_frm : Format.formatter -> formula -> unit
  19
  20
  21 module HTagSet : Hashtbl.S with type key = Ptset.t*Tag.t
  22
  23
  24 type 'a t = {
  25   id : int;
  26   mutable states : Ptset.t;
  27   init : Ptset.t;
  28   mutable final : Ptset.t;
  29   universal : Ptset.t;
  30   starstate : Ptset.t option;
  31   (* Transitions of the Alternating automaton *)
  32   phi : (state,(TagSet.t*(bool*formula*bool)) list) Hashtbl.t;
  33   sigma : (int,('a t -> Tree.t -> Tree.t -> Ptset.t*'a)) Hashtbl.t;
  34 }
  35
  36 val dump : Format.formatter -> 'a t -> unit
  37
  38 module Transitions : sig
  39 type t = state*TagSet.t*bool*formula*bool
  40 (* Doing this avoid the parenthesis *)
  41 val ( ?< ) : state -> state
  42 val ( >< ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
  43 val ( ><@ ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
  44 val ( >=> ) : state*(TagSet.t*bool*bool) -> formula -> t
  45 val ( +| ) : formula -> formula -> formula
  46 val ( *& ) : formula -> formula -> formula
  47 val ( ** ) : [`Left | `Right | `LLeft | `RRight ] -> state -> formula
  48
  49 end
  50 type transition = Transitions.t
  51 val equal_trans : transition -> transition -> bool
  52
  53
  54   module type ResultSet =
  55   sig
  56     type t
  57     val empty : t
  58     val cons : Tree.t -> t -> t
  59     val concat : t -> t -> t
  60     val iter : (Tree.t -> unit) -> t -> unit
  61     val fold : (Tree.t -> 'a -> 'a) -> t -> 'a -> 'a
  62     val map : (Tree.t -> Tree.t) -> t -> t
  63     val length : t -> int
  64   end
  65
  66   module IdSet : ResultSet
  67
  68   val top_down_count : 'a t -> Tree.t -> int
  69   val top_down : 'a t -> Tree.t -> IdSet.t
  70   val bottom_up_count_contains : 'a t -> Tree.t -> int
  71   val bottom_up_count : 'a t -> Tree.t -> Tag.t -> int