[Caml-list] Simple library to manipulate automata?

[Caml-list] Simple library to manipulate automata?

[David MENTRE]

Hello,

I would like to manipulate some basic automata in OCaml: creation, 
execution, minimization, display, etc.

Before re-inventing the wheel, do you know a library doing that?

 From my own searches, I only found "automatx" 
(http://pauillac.inria.fr/~quercia/) which seems to suit my needs but 
(1) has a French API and (2) has no license information.

Best regards,
david

Re: [Caml-list] Simple library to manipulate automata?

[Török Edwin]

On 05/10/2016 07:01 PM, David MENTRE wrote:
> Hello,
> 
> I would like to manipulate some basic automata in OCaml: creation, execution, minimization, display, etc.
> 
> Before re-inventing the wheel, do you know a library doing that?
> 
> From my own searches, I only found "automatx" (http://pauillac.inria.fr/~quercia/) which seems to suit my needs but (1) has a French API and (2) has no license information.

There is safa/symkat on opam [1]. It has various automata minimization algorithms, NFA -> DFA, print to .dot format.
Although it is meant for equivalence checking, so it may not be 'simple' to use for actually executing the automata, and beware that the syntax for its parser is not the usual regex [2].
(of course you can construct the automata with the API instead of parsing from a string to avoid this).

See below for some code that I wrote a while ago to visualize a DFA using safa/symkat:

[1] http://perso.ens-lyon.fr/damien.pous/symbolickat/
[2] http://perso.ens-lyon.fr/damien.pous/symbolickat/symkat.docdir/Parse.html

(*
 * $ ocamlfind ocamlopt printnfa.ml -package safa,symkat -o printnfa -linkpkg -rectypes
 * $ ./printnfa >test.dot
 * NFA states: 7
 * DFA states: 5
 * $ dot -Tsvg test.dot -o test.svg
 * $ firefox ./test.svg
 *)
let trace_dfa a states =
  let trace = Automata.SDFA.trace Format.pp_print_char Format.pp_print_char
      (Bdd.print_formula 0) in
  Trace.clear ();
  trace a states;
  print_endline (Trace.render false "\"")

let print_nfa x =
  let a,f = Automata.SNFA.reindex (Antimirov.nfa()) in
  let states = f (Antimirov.split x) in
  let number_of_states, _ = Automata.SNFA.size a states in
  Printf.eprintf "NFA states: %d\n%!" number_of_states;
  let a = Determinisation.optimised a in
  let number_of_states, _ = Automata.SDFA.size a [states] in
  trace_dfa a states; 
  Printf.eprintf "DFA states: %d\n%!" number_of_states

let print_dfa x =
  let a = Brzozowski.dfa () in
  let number_of_states, _ = Automata.SDFA.size a [x] in
  Printf.eprintf "DFA states: %d\n" number_of_states

let () =
  let e = Parse.expr "x*x*x*x*x*(x+y)z" in
  let x,_,_ = Hypotheses.eliminate [] e e in
  print_nfa x;

Best regards,
-- 
Edwin Török | Co-founder and Lead Developer

Skylable open-source object storage: reliable, fast, secure
http://www.skylable.com

Re: [Caml-list] Simple library to manipulate automata?

[David MENTRE]

Hello,

Le 10/05/2016 23:20, Török Edwin a écrit :
> There is safa/symkat on opam [1].

Yes, I also saw this library. But frankly, it seems overly complicated 
for our needs. I took a look at the API but don't understand it, and I 
don't have time to read the paper and related literature.

Sincerely yours,
david

Re: [Caml-list] Simple library to manipulate automata?

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 1452 bytes --]

Two libraries come to mind. I and others on the Frenetic[0] team have used
both at various points in time to implemented automata-related algorithms.
The first is a project called DPRLE. You can find its home page and my
GitHub clone of the SVN repository below:

  http://www.cs.virginia.edu/~ph4u/dprle/
  https://github.com/seliopou/dprle

The second is a library that I wrote called TDK. It implements a
generalization of BDDs, allowing for variables to have a lattice structure
and terminal nodes to have something like a semi-ring structure. You can
find the GitHub repository here:

  https://github.com/frenetic-lang/ocaml-tdk

Last I checked, TDK is on OPAM, while DPRLE is not. Hope this helps!

-Spiros E.

[0]: http://frenetic-lang.org

On Wed, May 11, 2016 at 2:37 AM, David MENTRE <dmentre@linux-france.org>
wrote:

> Hello,
>
> Le 10/05/2016 23:20, Török Edwin a écrit :
>
>> There is safa/symkat on opam [1].
>>
>
> Yes, I also saw this library. But frankly, it seems overly complicated for
> our needs. I took a look at the API but don't understand it, and I don't
> have time to read the paper and related literature.
>
> Sincerely yours,
> david
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2570 bytes --]

Re: [Caml-list] Simple library to manipulate automata?

[David MENTRÉ]

Hello,

Le 2016-05-10 à 18:01, David MENTRE a écrit :
> I would like to manipulate some basic automata in OCaml: creation,
> execution, minimization, display, etc.
> 
> Before re-inventing the wheel, do you know a library doing that?

Privately somebody pointed me to FSM:
   http://udel.edu/~heinz/software/index.html#fsm

Thanks for all the links, I'll look at them.

Best regards,
david