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 two main (Automata, Visualization) and some auxiliary programs. The main programs:


The package analyzes an automaton of the language presented as oriented labeled graph.

 

                 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,

piecewise 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

 

 

 

 

 

    

 

                    

Visualization

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.

 

                         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 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!

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

  home