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.