Stepwise Tree Automata Library (for OCaml) Copyright (C) 2003 Emmanuel Filiot This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA version 1.0 beta contact : filiot@grappa.univ-lille3.fr (********************************************************************) (****** *******) (****** Stepwise Tree Autamata Library for Ocaml *******) (****** *******) (********************************************************************) VERSION 1.0 AUTHOR Emmanuel Filiot DEPENDENCIES ocaml version >= 3.06 with ocamlopt compiler findlib which can be found on http://www.ocaml-programming.de/packages/ binary_tree_automata_library for Ocaml which can be found on http://www.ens-lyon.fr/~efiliot/tata/ INSTALLATION 1) become root by the command `su` if necessary ( typically when writing in the directory specified by the variable dest_dir of findlib.conf requires to be root) 2) type `make install` You can check if the package stepwise_automata is well installed by using the command : ocamlfind query binary_tree_automata The installation procedure installs all the modules (*.ml *.mli *.cmo *.cmx *.cma *.cmax) in dest_dir/binary_tree_automata/ where dest_dir is the variable specified in your findlib.conf . ABSTRACT The Stepwise Tree Automata Library provides functions for using stepwise automata with unranked trees ( membership, determinization, union, intersection, complementation, printing). The library also provides functors which allows to create new implementations of the required modules. DESCRIPTION The library provides only one module named stepwise_automata. See the .mli for details about the signature. The directory examples/ contains run examples of the library. You can also see the Makefile to see how to compile with Findlib or look at the following section. USING THE LIBRARY Example 1 : toto1.ml > open Stepwise_automata > > let () = print_string ( Stepwise.to_string (Stepwise.empty ()) > Example 2 : toto2.ml > open Stepwise_automata > open Stepwise_automata.Stepwise > > let () = print_string (to_string (empty ())) How to compile with ocamlfind ? Typing : >ocamlfind ocamlc -package stepwise_automata -c toto.mli >ocamlfind ocamlc -package stepwise_automata -c toto.ml >ocamlfind ocamlc -package stepwise_automata -linkpkg -o run_toto toto.cmo creates the executable "run_toto". It is the same way with ocamlopt : >ocamlfind ocamlopt -package stepwise_automata -c toto.mli >ocamlfind ocamlopt -package stepwise_automata -c toto.ml >ocamlfind ocamlopt -package stepwise_automata -linkpkg -o run_toto toto.cmx notes : description of the options -package : Causes that the package is added to the package list, and that -I options are added for every package, and all direct or indirect ancestors. -linkpkg: Causes that the archives of the packages in the package list and all their direct or indirect ancestors are added in topological order to the command line before the first file to compile or to link. USING THE LIBRARY IN A TOPLOOP BY USING TOPFIND It is possible to use the library in a toploop using the module Topfind provides with FindLib. Here is an example : type the command `ocaml` in a shell. Example : Objective Caml version 3.06 # #use "topfind";; Findlib has been successfully loaded. Additional directives: #require "package";; to load a package #list;; to list the available packages #camlp4o;; to load camlp4 (standard syntax) #camlp4r;; to load camlp4 (revised syntax) Topfind.reset();; to force that packages will be reloaded - : unit = () # #require "stepwise_automata";; Loading /usr/lib/ocaml/site-lib/binary_tree_automata/binary_tree_automata.cma Loading /usr/lib/ocaml/site-lib/stepwise_automata/stepwise_automata.cma # open Stepwise_automata;; # let t = Stepwise.convert (Node ("a", [Node ("b", [])]));; val t : Stepwise_automata.Stepwise.term = Term.N ("+", Term.L "a", Term.L "b") # let t2 = Stepwise.convert (Node ("a", [Node ("a", []); Node ("a", [])]));; val t2 : Stepwise_automata.Stepwise.term = Term.N ("+", Term.N ("+", Term.L "a", Term.L "a"), Term.L "a") # print_string (Stepwise.term_to_string t2);; +(+(a,a),a)- : unit = () # module A = Stepwise ;; module A : sig type symbol = Symbol.Symbol.t and term = Term.Term.t and automaton = Automaton.Automaton.automaton val convert : symbol Stepwise_automata.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 # let a = A.from_list ["a"] ["q"] ["q"] [("a",["q"])] [("q","q",["q"])] ;; val a : A.automaton = {Automaton.alphabet = ; Automaton.states = ; Automaton.final_states = ; Automaton.rules = } # print_string (A.to_string a);; ALPHABET : { + a } STATES : {q} FINAL STATES : {q} RULES : q+q->{q} a -> {q} - : unit = () # A.membership a t;; - : bool = false # A.membership a t2;; - : bool = true # A.emptyness a;; - : bool = false # let aa = A.union a a;; val aa : A.automaton = {Automaton.alphabet = ; Automaton.states = ; Automaton.final_states = ; Automaton.rules = } # print_string (A.to_string aa);; ALPHABET : { + a } STATES : {(q , q)} FINAL STATES : {(q , q)} RULES : a -> {(q , q)} (q , q)+(q , q)->{(q , q)} - : unit = () # print_string (A.to_short_string aa);; ALPHABET : { + a } STATES : {q0} FINAL STATES : {q0} RULES : a -> {q0} q0+q0->{q0} - : unit = ()