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.let.rug.nl/~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
vannoord@let.rug.nl tel. +31-50-3635935 fax +31-50-3636855
http://www.let.rug.nl/~vannoord/
--

Return to the comp.compilers page.
Search the comp.compilers archives again.