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,

 

                 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, strictly locally testable, or piecewise testable. The order of local testability of transition semigroup and 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. The application creates the syntactic semigroup from the transition graph of automaton. 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: for semigroups and for graphs. The graph folder contains main AUTOMATA.EXE file that calls the help file ViewGraph.EXE 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: 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

 

 

 

 

 

    

 

The semigroup folder contains main SEMI.EXE file with examples. Some semigroups, some direct products of them and some graphs of DFA are presented in input files. The input files are ordinary TXT files and can be created or modified by help of a standard editor. Comments in input files may be included, but they do not contain numbers and sign ;
First two numbers in INPUT semigroup file are the number of generators and the number of elements. Semigroup is presented by its Cayley graph of the semigroup meaning the table:

                                                     elements X generators,

where the elements of the semigroup are represented by integers from 0 to n-1 with generators in beginning. i-th row of the table is a list of products of i-th element on all generators..

 

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.

Graphs with maximal length of synchronizing word (n-1)2. Cerny for n states (here n=8) 2 colors; Kari 6 states, 2 colors, Roman 5 states, 2 colors; two found by Testas 4 states, 3 colors; CenyPirickaRozenaurova 4 states, 2 colors; three found by Testas 3 states, 3 and 2 colors

 

                                 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 

 

Thank You for any remarks concerning the package!

  http://www.cs.biu.ac.il/~trakht

  home