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