Verification Tools of the Package


An important verification tool of the package is the possibility to study both transition graph and semigroup of a given automaton and compare the results. The algorithms for graphs and for semigroups are completely different.
An auxiliary program, written in C, finds the syntactic semigroup of the automaton from its transition graph. The program of |G|gn2 time complexity finds distinct mappings of the graph of the automaton induced by the letters of the alphabet of the labels.
On this way, the syntactic semigroup of the automaton and the minimal set of semigroup generators is constructed.

Let us notice that the size of the syntactic semigroup is in general not polynomial in the size of the transition graph.

However, in many cases the difference between the size of the semigroup and the graph is not so great and the passage to the syntactic semigroup is useful.



The checking of the algorithms is based also on the fact that some of the considered objects form a variety (quasivariety, pseudovariety) and therefore they are closed under direct product. For instance, k-testable semigroups form variety, locally threshold testable semigroups and piecewise testable semigroups form pseudovariety. Left [right] locally testable semigroups form quasivariety because they are locally idempotent and satisfy locally some identities. Let us mention also Eilenberg classical variety theorem.
Two auxiliary programs, written in C, that find the direct product of two semigroups and of two graphs belong to the package. The input of the semigroup program consists of two semigroups presented by their Cayley graph with generators at the beginning of the element list. The result is presented in the same form and the set of generators of the result is placed in the beginning of the list of elements. The number of generators of the result is n1g2 +n2g1 - g1g2 where ni is the size of the i-th semigroup and gi is the number of its generators. The components of the direct product of graphs are considered as graphs with common alphabet of edge labels. The labels of both graphs are identified according to their order. The number of labels is not necessarily the same for both graphs, but the result alphabet uses only common labels from the beginning of both alphabets.

Big size semigroups and graphs with predesigned properties can be obtained by help of these programs. Any direct power of a semigroup or graph keeps the properties of the origin.


A GRAPH REPRESENTATION


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 in column ( number of the node from the end of the edge with label from the j-th column and beginning in i-th node is placed in the (i,j) cell). The User has opportunity to define the number of nodes, size of alphabet of edge labels and to change values in table.
Maximal size of considered graphs was about some hundreds nodes.



home