T E S T A S
A package TESTAS
for checking some kinds of testability, finding synchronizing words and road
coloring.
Download the freeware version for
WINDOWS:
TESTAS (zip file, about 200 KB)
The package includes three main and some auxiliary
programs. The main programs:
1) analyze an automaton of
the language presented as oriented labeled graph;
2) find syntactic
semigroup of the language,
3) find road coloring
of directed complete graph,
4) view visual
image of the transition graph (and its subgraphs) based on the structure
properties of the graph.
5)
check the synchronizabity, find synchronizing words.
The auxiliary programs (not included in
DEMO version) find:
1) direct product of two transition graphs of the automaton;
2) direct product of two syntactic semigroups of the automaton,
The User defines the data:
the number of nodes, size of the alphabet of edge labels and the values in the
matrix. For example, the input 2 6 1 0 2 1 0 3 5 2 3 2 4 5 presents the Cayley
graph with 2 labels and 6 vertices and the next input 2 5 1 0 2 1 ; 3 : ; 3 2
presents the Cayley graph (non complete) with 2 labels and 5 vertices. The
values are divided by a gap. The semicolon corresponds to empty cell of the
table.
The graph from Figure 1 with matrix
representation and the graph from Figure 2 with matrix representation follow.

Letter a

Letter b

Vertex 0

1

0

Vertex 1

2

1

Vertex 2

0

3

Vertex 3

5

2

Vertex 4

3

2

Vertex 5

4

5


Letter a

Letter b

Vertex 0

1

0

Vertex 1

2

1

Vertex 0


3

Vertex 0



Vertex 0

3

2

Paper in
postscript file
A package TESTAS for checking some kinds
of testability.
TESTAS on
several prominent CONFERENCES
Visualisation
A linear
algorithm of the visualization of the graph. Labels on arcs are presented by colors
of the arcs. Strongly connected components, cycles and paths (partially) are
seen on the layout.
Road coloring
The program changed the labels (colors) on edges of the automaton
for to turn it into synchronizing automaton. The input automaton must be
deterministic (no empty cells in input). The search (input) table is
considered as an automaton with an arbitrary coloring (sometimes even
synchronizing). One can see visual presentation of the search automaton and
after the coloring compare with the visualization of the result. Subquadratic
algorithm.
Power Point Report of the proof on Conference