Ranked and Unranked Tree Automata Libraries (for Ocaml)


Here you can find two libraries written in Ocaml for manipulating ranked and unranked tree automata. The first one is a library for manipulating binary tree automata ( see the readme file,the bibliography and the TATA's book for more explanations ), i.e. classical tree automata which runs on binary trees. The second one is a library for manipulating unranked tree automata, called stepwise automata (see the readme file, the bibliography and the abstract for more explanations). This one uses the first one. The libraries are designed for Findlib, a package manager for Ocaml.

Author
Emmanuel Filiot
filiot xxx lifl dot fr where xxx=@

Team
MOSTRARE INRIA Futur. Laboratoire d'Informatique Fondamentale de Lille (LIFL)

Summary
  • Binary automata library

  • abstract
  • description
  • prerequisites
  • download
  • documentation
  • bibliography

  • Stepwise automata library

  • abstract
  • prerequisites
  • download
  • documentation
  • bibliography

    • Binary Tree Automata Library

    Abstract
    The Binary Tree Automata Library provides functions for using classical tree automata with binary trees ( membership, determinization, union, intersection, complementation, printing), e.g. the membership can run only with binary trees. The library also provides functors which allows the user to create new implementations of the required modules.

    Description
    The library is divided into modules. The main modules are Term, Rules and Automaton which respectively manage the binary terms, the set of rules, and the automata. The modules are implemented with string, i.e. the symbols are string, and the states are string. The type of a binary term/tree is given by : 

    type 'a term_type = L of 'a | N of 'a * 'a term_type * 'a term_type
    I give respective signatures of the three main modules : 
    module type TERM =
  sig    
    
    type symbol
    type alphabet
    type t     
	  
    val fold : (symbol -> 'a) -> ( symbol -> 'a -> 'a -> 'a) -> t -> 'a
    val height : t -> int 
    val size : t -> int   
    val to_string : t -> string
    val alphabet_check : alphabet -> t -> bool
    val save : string -> t -> unit
	
  end

 module type RULES =
 sig

   type symbol
   type state
   type states
   type args
   type t

   val debug : bool ref
   val set_debug : bool -> unit

   val create : int ->  t
   val mem :  t -> symbol -> bool
   val find :  t  -> symbol -> args ->  states
   val add :  t -> symbol -> args -> states -> int -> unit
   val remove :  t -> symbol -> args ->  unit
   val iter : ( args -> states -> unit) ->  t -> unit
   val iter3 : (symbol -> args -> states -> unit) ->  t -> unit
   val size :  t -> int
   val combine :  t -> symbol -> states list -> states
   val eval_const :  t -> symbol -> states
   val is_deterministic :  t -> bool 
   val args_to_string : args -> string
   val to_string :  t -> string
   val to_short_string :  t -> string
   val from_list : (symbol * state list * state list) list ->  t

 end


 module type AUTOMATON =
 sig

   type symbol
   type alphabet
   type term
   type states
   type rules
   type automaton

   exception Alphabets_not_equal

   val debug : bool ref
   val set_debug : bool -> unit

   val empty : unit -> automaton
   val membership : automaton -> term -> bool
   val to_string : automaton -> string
   val to_short_string : automaton -> string
   val determinize : automaton -> automaton
   val complement : automaton -> automaton
   val union : automaton -> automaton -> automaton
   val inter : automaton -> automaton -> automaton
   val emptyness : automaton -> bool
   val from_list : string list -> string list -> string list ->
       (string * (string list) * (string list)) list -> automaton
  end

    Prerequisites
    Ocaml version >=3.06
    Findlib

    Download
    You can download the beta version : .tar.gz
    .tar.gz with the documentation
    See also the README file.

    Documentation
    ps , gz .

    Biliography
     H.Comon, M. Daucher, R.Gilleron, S.Tison, and M.Tommasi.Tree Automata Techniques and Applications.1998.
    Emmanuel Filiot.Rapport of student internship : Automates d'Arbres à Arités Arbitraires(in french). 2003.

    Stepwise Automata Library

    Abstract

    The Stepwise Tree Automata Library provides functions for using stepwise automata with unranked trees ( membership, determinization, union, intersection, complementation, printing). An unranked tree is a tree for which the number of sons of a given node is unknown. Unranked trees are converting into binary trees with the function : 
    convert : 'a unranked_term -> term
    Stepwise automata are just converting into binary tree automata. The type of an unranked tree is given by : 
    type 'a unranked_term = Node of 'a * ('a unranked_term list)
    The library also provides functors which allows to create new implementations of the required modules.

    The library provides only one module called Stepwise_automata of signature : 

    module type STEPWISE_AUTOMATA = 
    
    sig 
    

      type symbol
      type term 
      type automaton
	    
      val convert : symbol unranked_term -> term 
      val empty : unit -> automaton              
      val membership : automaton -> term -> bool 
      val union : automaton -> automaton -> automaton
      val inter : automaton -> automaton -> automaton
      val complement : automaton -> automaton
      val determinize : automaton -> automaton
      val emptyness : automaton -> bool
      val term_to_string : term -> string
      val to_string : automaton -> string
      val to_short_string : automaton -> string
      val from_list : string list -> string list -> string list -> 
( string * (string list)) list -> ( string * string * (string list)) list -> automaton

 end

    Prerequisites
    Ocaml version >=3.06
    Findlib
    Binary Tree Automata Library for Ocaml

    Download
    You can download the beta version : .tar.gz
    .tar.gz with the documentation
    See also the README file.

    Documentation
    ps, ps.gz.

    Bibliography
     Julien Carme, Joachim Niehren and Marc Tommasi.Querying Unranked Trees with Stepwise Tree Automata.2004.
    Emmanuel Filiot.Rapport of student internship : Automates d'Arbres à Arités Arbitraires(in french). 2003.