-(* module Ptset : sig
- include Set.S with type elt = int
- val from_list : elt list -> t
- end
- *)
-
type state = int
val mk_state : unit -> state
-type predicate = [ `Left of (Tree.Binary.t -> bool) | `Right of (Tree.Binary.t -> bool) |
- `True
- ]
-
-
-val eval_pred : Tree.Binary.t -> predicate -> bool
-
type formula_expr =
False
| True
| Or of formula * formula
| And of formula * formula
| Atom of ([ `Left | `Right | `LLeft | `RRight ] * bool * state)
-and formula = { fid : int; fkey : int; pos : formula_expr; neg : formula; st : (Ptset.t*Ptset.t)*(Ptset.t*Ptset.t); size: int;}
+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;}
val true_ : formula
val false_ : formula
val atom_ : [`Left | `Right | `LLeft | `RRight ] -> bool -> state -> formula
module HTagSet : Hashtbl.S with type key = Ptset.t*Tag.t
-type t = {
+
+type 'a t = {
id : int;
mutable states : Ptset.t;
init : Ptset.t;
mutable final : Ptset.t;
universal : Ptset.t;
- phi : (state,(TagSet.t*(bool*formula*predicate)) list) Hashtbl.t;
- delta : (state*Tag.t, (bool*formula*predicate)) Hashtbl.t;
-(* delta : (state,(bool*formula*predicate) TagMap.t) Hashtbl.t; *)
- sigma : (bool*formula*(predicate list*predicate list)*bool) HTagSet.t;
-
+ starstate : Ptset.t option;
+ (* Transitions of the Alternating automaton *)
+ phi : (state,(TagSet.t*(bool*formula*bool)) list) Hashtbl.t;
+ sigma : (int,('a t -> Tree.t -> Tree.t -> Ptset.t*'a)) Hashtbl.t;
}
-val dump : Format.formatter -> t -> unit
+
+val dump : Format.formatter -> 'a t -> unit
module Transitions : sig
-type t = state*TagSet.t*bool*formula*predicate
+type t = state*TagSet.t*bool*formula*bool
(* Doing this avoid the parenthesis *)
val ( ?< ) : state -> state
-val ( >< ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*predicate)
-val ( ><@ ) : state -> TagSet.t*bool*predicate -> state*(TagSet.t*bool*predicate)
-val ( >=> ) : state*(TagSet.t*bool*predicate) -> formula -> t
+val ( >< ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
+val ( ><@ ) : state -> TagSet.t*bool -> state*(TagSet.t*bool*bool)
+val ( >=> ) : state*(TagSet.t*bool*bool) -> formula -> t
val ( +| ) : formula -> formula -> formula
val ( *& ) : formula -> formula -> formula
val ( ** ) : [`Left | `Right | `LLeft | `RRight ] -> state -> formula
type transition = Transitions.t
val equal_trans : transition -> transition -> bool
-module TS : sig
- type t
- val empty : t
- val cons : Tree.Binary.t -> t -> t
- val append : Tree.Binary.t -> t -> t
- val concat : t -> t -> t
- val to_list_rev : t -> Tree.Binary.t list
- val length : t -> int
- val iter : (Tree.Binary.t -> unit) -> t -> unit
- val rev_iter : (Tree.Binary.t -> unit) -> t -> unit
- val find : (Tree.Binary.t -> bool) -> t -> Tree.Binary.t
-end
-(*module BottomUpJumpNew :
-sig *)
- val run : t -> Tree.Binary.t -> TS.t
- val run_time : t -> Tree.Binary.t -> TS.t
-(*end *)
+ module type ResultSet =
+ sig
+ type t
+ val empty : t
+ val cons : Tree.t -> t -> t
+ val concat : t -> t -> t
+ val iter : (Tree.t -> unit) -> t -> unit
+ val fold : (Tree.t -> 'a -> 'a) -> t -> 'a -> 'a
+ val map : (Tree.t -> Tree.t) -> t -> t
+ val length : t -> int
+ end
+
+ module IdSet : ResultSet
+
+ val top_down_count : 'a t -> Tree.t -> int
+ val top_down : 'a t -> Tree.t -> IdSet.t
+ type jump_kind = [ `TAG of Tag.t | `CONTAINS of string | `NOTHING ]
+ val bottom_up_count : 'a t -> Tree.t -> jump_kind -> int