TaToWa
This project is a part of a tree automata toolkit that aims to construct, manipulate, optimize different types of tree automata.
TaToWa is a D package for tree automata minimization. Its principal is to transform a given tree automata to a word automata. The minimization of the later coincides with the minimization of the first one.
This package contains four files:
1-essential.d : implements necessary operations for manipulating, alphabets, states, states sets ...
2-FTA.d : A ''D'' class implementing a Tree automata and necessary methods to the word automata transformation.
3-sa.d : A ''D'' class implementing word (string) automata.
4-lazy_rand.d : A package containing a lazy generator of -possibly incomplete, with useless states- tree automata
REQUIREMENTS:
A ''D2'' Complier with ''phobos'' standard library
INPUT:
The package proposes its own xml input format. As example:
<?xml version="1.0"?>
<automaton>
<auto>
<alphabet>a,0;b,0;g,1;f,2;</alphabet>
<states>q1,q2,q3,q4,</states>
<Fstates>q3,q4,</Fstates>
<delta>
<rule>a,q1,</rule>
<rule>b,q2,</rule>
<rule>g,q1,q3,</rule>
<rule>g,q2,q4,</rule>
<rule>f,q2,q4,q4,</rule>
<rule>f,q1,q3,q4,</rule>
<rule>f,q2,q3,q4,</rule>
<rule>f,q1,q4,q4,</rule>
</delta>
</auto>
</automaton>
The package accepts also timbuk format:
Ops: a:0 b:0 g:1 f:2
Automaton states equivalence computation test
States q1,q2,q3,q4,
Final States q3,q4,
transitions
a() -> q1
b() -> q2
g(q1) -> q3
g(q2) -> q4
f(q2,q4) -> q4
f(q1,q3) -> q4
f(q2,q3) -> q4
f(q1,q4) -> q4
OUTPUT:
We adapt the OpenFst output format for genertated word automata:
<Lambda> q1
g,dot, q1 q3
f,dot,q3, q1 q4
f,dot,q4, q1 q4
g,dot, q2 q4
f,dot,q4, q2 q4
f,dot,q3, q2 q4
f,q1,dot, q3 q4
f,q2,dot, q3 q4
f,q2,dot, q4 q4
f,q1,dot, q4 q4
q3
q4
TODO:
A GUI for simple usage of the package
CONTACT: gyounes84@gmail.com
