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
The package includes two main (Automata, Visualization) and some
auxiliary programs. The main programs:
The package analyzes an automaton of the
language presented as
deal TESTAS
The package TESTAS is a
starting point for your acquaintance with a set of procedures for deciding
whether or not a language given by its transition graph or its syntactic
semigroup is locally
testable, threshold locally testable,
Left,
right local local testability
The order of local testability of transition graph
of deterministic finite automaton and the order of strict local testability of transition
graph is also found.
Synchronizing graphs are checked. Synchronizing word is
found by help of some effective polynomial time algorithms. All these
algorithms have been implemented as an C++ package.
The visualization of the transition graph and its
subgraphs is realized by help of a linear algorithm.
The DEMO version of the package TESTAS consists from two folders: the graph
folder contains main AUTOMATA.EXE file that
calls the help file ViewGraph.EXE (at
beginning call twice) for visualization and some INPUT
files as examples.
First two numbers in INPUT graph file are the size of
alphabet and the number of nodes. Transition graph of the automaton is
presented by the table:
nodes
X labels,
where the nodes are represented by
integers from 0 to n-1. i-th row of the table is a list of successors of
i-th node according the label column (number of the node from the end of the
edge with label from the j-th column and beginning in i-th row is placed in the
(i,j) cell).
The User defines the data:
size of the alphabet of labels
on edges – columns of the matrix, the number of nodes – rows
and the values in the matrix
along rows from row 0 row to last.
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
|
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.
Visual image of the graph can be
considered with every its transformation (removing and adding vertices and
edges).
Graphs
with maximal length of synchronizing word (n-1)2. Sequence Cerny for n states (below n=8) 2 colors; Kari 6 states, 2 colors,
Roman 5 states, 2 colors; three graphs found by TESTAS - 4 states, 3 colors;
Cerny-Piricka-Rozenaurova 4 states, 2 colors;
A group of automata of at most 4
states and some colors
(a unions of abovementioned) found by Don and Zantema. In
general 27 graphs.
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 automaton (even colored) and after the coloring compare
with the visualization of the result.
Power Point Report of the proof on Conference
Paper in postscript file
A
package TESTAS for checking some kinds of testability.
TESTAS on several prominent CONFERENCES
Thank You for any remarks
concerning the package!