ANNOUNCE: Fsa Utilities (version 4)

FSA utilities (version 4)

A new version of FSA Utilities is available!

What is it:

-----------

The FSA Utilities toolbox is a collection of utilities to manipulate

regular expressions, finite-state automata and finite-state

transducers. Manipulations include automata construction from regular

expresssions, determinization (both for finite-state acceptors and

finite-state transducers), minimization, composition, complementation,

intersection, Kleene closure, etc. Furthermore, various visualization

tools are available to browse finite-state automata.

Required:

---------

The package requires SICStus Prolog 3 #3 or 3 #5, and is known to

work under HP UX (9.0.5) and Linux (1.2.13 Elf).

Copyright:

----------

The package is available under the conditions of the

GNU General public licence.

More Info:

----------

http://www.*-*-*.com/ ~vannoord/FSA/fsa.html

Highlights:

-----------

** Construction of finite automata on the basis of regular

expressions. Regular expression operators can be added; moreover the

syntax of regular expressions can be adapted too. Regular expression

operators include:

* Concatenation, Kleene closure, Union and Option.

* Complement, Difference and Intersection.

* Composition, Cross-Product. Same-Length-Cross-Product.

Domain. Range. Identity. Inversion.

* Intervals

* Minimization, Determinization, Determinization of Transducers.

* `Any'-variable which matches any symbol.

* Macro's and other user-defined regular expression operators.

** Optimal Prolog Code Generation.

Compilation of a FSA or FST into an efficient Prolog program (which

can be used to check whether a given string is in the language defined

by the automaton, or to generate the transduction of a given string

w.r.t. a given transducer). If the input FSA/FST is deterministic,

the resulting Prolog program also is (using indexing).

** Determinization.

A given FSA is determinized (using subset construction). There is a

limited functionality to determinize finite state transducers as well;

this procedure is not guaranteed to terminate though. Note that in

general FST cannot be determinized.

** Minimization.

Minimization of a FSA. Three different minimization algorithms are

supported.

** Acceptance, Transduction and Production.

Check a given string for acceptance by FA. Transduce a given string

with a transducer. Produce all strings / pairs generated by FA.

** Visualisation.

Much attention has been paid to be able to visualize finite state

recognizers and finite state transducers. Support includes built-in

visualization (Tk, PicTeX and postscript) and interfaces to third

party software (VCG and daVinci).

Changes with FSA3

-----------------

The underlying philosophy has changed: from now on users are expected

to write regular expressions. To this end, the regular expression

notation has been revised from scratch and is much more powerful.

Moreover, it is easy to define new regular expression operators. The

system compiles regular expressions into automata. The format of

automata has changed drastically (since it is an internal format

now). This has the benefit that the code is much cleaner, shorter and

thus easier to understand, modify and extend. Moreover, the program is

faster too! There is an option to convert automata in the old format

to automata in the new format.

The Tk Widget has been extended. You can now type in regular

expressions which will be converted to automata and visualised on your

screen.

--

dr Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen

http://www.*-*-*.com/ ~vannoord/