Something from theoretical background Local testability: A locally testable language L is a language with the property that for some nonnegative integer k, called the order or the level of local testability, whether or not a word u is in the language L depends on (1) the prefix and suffix of the word u of length k-1 and (2) the set of intermediate substrings of length k of the word u. For a given k the language is called k-testable. The definition of strictly locally testable language is analogous, only the length of prefix and suffix is equal to k. The definition of left [right] locally testable language is obtained from the definition of locally testable language by adding to the list of two conditions the third condition: (3) the order of the first appearance from left [right] of substrings. The definition of bilateral] locally testable language is obtained from the definition of locally testable language by adding to the list of two conditions the third condition: (3) the order of the first appearance of substrings from both left and right. The syntactic characterization of locally threshold testable language: Given the syntactic semigroup S of the language L, we form a graph G(S) as follows. The vertices of G(S) are the idempotents of S , and the edges from e to f are the elements of the form esf. A language L is locally threshold testable if and only if S is aperiodic and for any two nodes e , f and three edges p , q , r such that p and q are edges from e to f and r is an edge from f to e we have: prq=qrp Piecewise testability: A language is piecewise testable iff its syntactic monoid is J-trivial (meaning that distinct elements of monoid generate distinct ideals). A word of labels is called synchronizing if the word maps all states of the graph on a unique state. An automaton having synchronizing word is called synchronizing. T E S T A S
This application demonstrates the basics of using the package TESTAS and is also 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 algorithms. Some new effective polynomial time algorithms are used.
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 Graph.EXE for visualization and some INPUT files as examples.
The semigroup folder contains main SEMI.EXE file with examples.
The time of life of demo version is bounded for user.
Some key 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.
Set of generators is not necessarily minimal, therefore the multiplication table of the semigroup (Cayley table) is acceptable too.
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).

Click for beginning on EXE file and then follow the prompts.

Two auxiliary programs (not included in DEMO version) create direct product of graphs and of semigroups. Auxiliary programs need files without comments.
Synchronization:
A word of labels is called synchronizing if the word maps all states
of the graph on a unique state. An automaton having synchronizing word
is called synchronizing.
An automaton with transition graph G is synchronizing iff G² has a sink state.
The last statement is a base for an algorithm to verify synchronizability of deterministic finite automaton of order O(n²) in the most worst case.
The package TESTAS contains also some essential modifications of Eppstein algorithm called cyclic and semigroup algorithms for finding synchronizing word. For wide class of automata the time complexity of semigroup algorithms is O(n²q).
An algorithm for finding synchronizing word of O(n⁴q) time complexity is based on the results of Frankl and Klyachko-Rystsov-Spivak.
A straightforward non-polynomial algorithm finds synchronizing word of minimal length.


L I T E R A T U R E

J.A. Brzozowski, I. Simon, Characterizations of locally testable events,
Discrete Math. 4(1973), 243-271.
D. Beauquier, J.E. Pin, Factors of words, Lect. Notes in Comp. Sci., vol.
372, (Springer, Berlin, 1989), 63-79.
P. Caron LANGAGE: A Maple package for automaton characterization
of regular languages, Lect. Notes in Comp. Sci., 1436(1998), 46-55,
Springer. D. Eppstein, Reset sequences for monotonic automata.
SIAM J. Comput., 19(1990), 500-510.
S. Kim, R. McNaughton, R. McCloskey, A polynomial time algorithm for the
local testability problem of deterministic finite automata, IEEE Trans.
Comput., N10, 40(1991) 1087-1093.
S. Kim, R. McNaughton, Computing the order of a locally testable automaton,
Lect. Notes in Comp. Sci., vol. 560(Springer, Berlin, 1991) 186-211. I.
Simon, Piecewise testable events, Lect. Notes in Comp. Sci., vol. 33,
(Springer, Berlin, 1975), 214-222.
A.N. Trahtman, A polynomial time algorithm for local testability and its
level. Int. J. of Algebra and Comp., vol. 9, 1(1998), 31-39.
A.N. Trahtman, Algorithms finding the order of local testability of
deterministic finite automaton and estimation of the order, Th. Comp. Sci.,
235(2000), 183-204.
A.N. Trahtman, 28. Piecewise and local threshold testability of DFA. Lect.
Notes in Comp. Sci, 2138(2001), 347-358.
A.N. Trahtman, Algorithms verifying local threshold and piecewise
testability of semigroup and solving Almeida problem. in T. Imaoka eds.
Alg. semigroups, formal languages and computation. RIMS Kokyuroku
Proceedings, 1222(2001), 145-151.
A.N. Trahtman, Verification tools for checking some kinds of testability.
TWLT Proc., 21(2003), 253-263.
A.N. Trahtman, A polynomial time algorithm for left [right] local
testability. Lect. Notes in Comp. Sci, 2608(2003), 203-212. Proceedings of
7-th Int. Conf. on Implementation and Application of Automata. Tours,
France, July 3-5,2002, 201-210.
A.N. Trahtman, A package TESTAS for checking some kinds of testability.
Lect. Notes in Comp. Sci, 2608(2003), 228-232. Proceedings of 7-th Int.
Conf. on Implementation and Application of Automata. Tours, France, July
3-5, 2002, 223-228.
A.N. Trahtman. Verification of algorithms for checking some kinds of testability.
In Algebraic Methods in Language Processing, TWLT 21, eds. F.Spoto, G. Scollo, A. Nijholt. 2003, 253-263.
A.N. Trahtman. Reducing the time complexity of testing for local threshold testability.
Theoret. Comput. Sci., 328(2004), 151-160.
A.N. Trahtman. An eficient algorithm finds noticeable trends and examples concerning the Cerny conjecture. Lect. Notes in Comp. Sci, Springer, MFCS 2006, 4162(2006), 789-800.
A.N. Trahtman. Notable trends concerning the synchronization of graphs and automata. El. Notes in Discr. Math., 25(2006), 173-175
A.N. Trahtman. The Cerny Conjecture for Aperiodic Automata. Discr. Math. & Theoret. Comput. Sci. v. 9 2(2007), 3-10.

See also
htpp://www.cs.biu.ac.il/~trakht

E-mail: trakht@macs.biu.ac.il

Thank You for any remarks concerning package!
 next