ata.mli

   1 module TS : sig
   2   type t
   3   val empty : t
   4   val cons : Tree.t -> t -> t
   5   val append : Tree.t -> t -> t
   6   val concat : t -> t -> t
   7   val length  : t -> int
   8   val iter : (Tree.t -> unit) -> t -> unit
   9 end
  10
  11 type state = int
  12 val mk_state : unit -> state
  13
  14 type formula_expr =
  15     False
  16   | True
  17   | Or of formula * formula
  18   | And of formula * formula
  19   | Atom of ([ `Left | `Right | `LLeft | `RRight ] * bool * state)
  20 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;}
  21 val true_ : formula
  22 val false_ : formula
  23 val atom_ : [`Left | `Right | `LLeft | `RRight ] -> bool -> state -> formula
  24 val and_ : formula -> formula -> formula
  25 val or_ : formula -> formula -> formula
  26 val not_ : formula -> formula
  27 (*val equal_form : formula -> formula -> bool *)
  28 val pr_frm : Format.formatter -> formula -> unit
  29
  30
  31 module HTagSet : Hashtbl.S with type key = Ptset.t*Tag.t
  32
  33 type dispatch = { first : Tree.t -> Tree.t;
  34                   flabel : string;
  35                   next : Tree.t -> Tree.t -> Tree.t;
  36                   nlabel : string;
  37                   consres : Tree.t -> TS.t -> TS.t -> bool -> bool -> TS.t;
  38                 }
  39
  40 type formlist = Nil | Cons of state*formula*int*formlist
  41
  42 type t = {
  43     id : int;
  44     mutable states : Ptset.t;
  45     init : Ptset.t;
  46     mutable final : Ptset.t;
  47     universal : Ptset.t;
  48     starstate : Ptset.t option;
  49     (* Transitions of the Alternating automaton *)
  50     phi : (state,(TagSet.t*(bool*formula*bool)) list) Hashtbl.t;
  51     sigma : (dispatch*bool*formlist*Ptset.t*Ptset.t) HTagSet.t;
  52 }
  53 val dump : Format.formatter -> t -> unit
  54
  55 module Transitions : sig
  56 type t = state*TagSet.t*bool*formula*bool
  57 (* Doing this avoid the parenthesis *)
  58 val ( ?< ) : state -> state
  59 val ( >< ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
  60 val ( ><@ ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
  61 val ( >=> ) : state*(TagSet.t*bool*bool) -> formula -> t
  62 val ( +| ) : formula -> formula -> formula
  63 val ( *& ) : formula -> formula -> formula
  64 val ( ** ) : [`Left | `Right | `LLeft | `RRight ] -> state -> formula
  65
  66 end
  67 type transition = Transitions.t
  68 val equal_trans : transition -> transition -> bool
  69
  70
  71
  72 (*module BottomUpJumpNew :
  73 sig *)
  74   val run : t -> Tree.t -> TS.t*int
  75   val run_count : t -> Tree.t -> int
  76   val run_time :  t -> Tree.t -> TS.t*int
  77 (*end *)
  78