Some New Features and Algorithms for the Study of DFA

Avraham N. Trahtman

Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel.

DOI: 10.4236/ojdm.2012.22008                

Abstract

The work presents some new algorithms realized recently in the package TESTAS. The package decides whether or not DFA is synchronizing, several procedures find relatively short synchronizing words and a synchronizing word of the minimal length. We check whether or not a directed graph has a road coloring that turns the graph into a synchronizing deterministic finite automaton (DFA). The algorithm finds the coloring if it exists. Otherwise, the k-synchronizing road coloring can be found. We use a linear visualization of the graph of an automaton based on its structural properties.

Keywords

Finite Automaton; Synchronizing Word; Algorithm; Visualization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. P. Beal, E. Czeizler, J. Kari and D. Perrin, “Unambiguous Automata,” Mathematics and Computer Science, Vol. 1, No. 4, 2008. pp. 625-638. doi:10.1007/s11786-007-0027-1
[2]	D. Perrin and M. P. Schutzenberger, “Synchronizing Prefix Codes and Automata, and the Road Coloring Problem,” Symbolic Dynamics and Applications, Contemporary Mathematics, Vol. 135, 1992, pp. 295-318. doi:10.1090/conm/135/1185096
[3]	A. N. Trahtman, “A Package TESTAS for Checking Some Kinds of Testability,” Implementation and Application of Automata, Vol. 2608, 2003, pp. 228-232. doi:10.1007/3-540-44977-9_22
[4]	C. Robert Berwick, K. Okanoya, Z. Gabriel, J. L. Beckers and J. J. Bolhuis, “Songs to Syntax: The Linguistics of Birdsong,” Trends in Cognitive Science, Vol. 15, No. 3, 2011, pp. 113-121. doi:10.1016/j.tics.2011.01.002
[5]	J. V. Rauff, “Way Back from Anywhere: Exploring the Road Coloring Conjecture,” Mathematical and Computer Education, Vol. 43, No.1, 2009, pp. 6-17.
[6]	J. ?erny, “Poznamka k Homogenym Eksperimentom s Konechnymi Automatami,” Matematicko Fyzicalny ?asopis, Vol. 14, 1964, pp. 208-215.
[7]	A. N. Trahtman, “Modifying the Upper Bound on the Length of Minimal Synchronizing Word,” Fundamentals of Computation Theory, Vol. 6914, 2011, pp. 173-180. doi:10.1007/978-3-642-22953-4_15
[8]	A. Mateescu and A. Salomaa, “Many-Valued Truth Functions, ?erny’s Conjecture and Road Coloring,” Bulletin of European Association for TCS, Vol. 68, 1999. pp. 134- 148.
[9]	K. Culik II, J. Karhumaki and J. Kari, “A Note on Synchronized Automata and Road Coloring Problem,” Journal of Foundations of Computer Science, Vol. 13, No. 3, 2002, pp. 459-471. doi:10.1142/S0129054102001217
[10]	A. N. Trahtman, “An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the ?erny Conjecture,” Mathematical Foundations of Computer Science, Vol. 4162, 2006, pp. 789-800.
[11]	R. L. Adler and B. Weiss, “Similarity of Automorphisms of the Torus,” Memoirs of the American Mathematical Society, Providence, RI, 1970, p. 98.
[12]	R. L. Adler, L. W. Goodwyn and B. Weiss, “Equivalence of Topological Markov Shifts,” Israel Journal of Mathematics, Vol. 27, No. 1, 1977, pp. 49-63. doi:10.1007/BF02761605
[13]	B. A. Rubshtein, “Generating Partitions of Markov Endomorphisms,” Functional Analysis Applications, Vol. 8, No. 1, 1974, pp. 84-85. doi:10.1007/BF02028320
[14]	A. N. Trahtman, “Synchronizing Road Coloring,” 5-th IFIP World Computer Congress—Theoretical Computer Science, Vol. 273, 2008, pp. 43-53.
[15]	A. N. Trahtman, “The Road Coloring Problem,” Israel Journal of Mathematics, Vol. 172, No. 1, 2009, pp. 51- 60. doi:10.1007/s11856-009-0062-5
[16]	G. Budzban and Ph. Feinsilver, “The Generalized Road Coloring Problem and Periodic Digraphs,” Applied Algebra in Engineering, and Computing, Vol. 22, No. 1, 2011, pp. 21-35. doi:10.1007/s00200-010-0135-z
[17]	A. N. Trahtman, “A Partially Synchronizing Coloring,” Computer Science—Theory and Applications, Vol. 6072, 2010, pp. 362-370.
[18]	A. N. Trahtman, T. Bauer and N. Cohen, “Linear Visualization of a Road Coloring,” Proceedings of 9th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2010, pp. 13-16.
[19]	A. N. Trahtman, “Verification of Algorithms for Checking Some Kinds of Testability,” In: F. Spoto, G. Scollo and A. Nijholt, Eds., Algebraic Methods in Language Processing, TWLT 21, Universiteit Twente, Holland, 2003, pp. 253-263.
[20]	M. P. Béal and D. Perrin, “A Quadratic Algorithm for Road Coloring,” arXiv: 0803.0726v2 [cs.DM], 2008.
[21]	J. M. Six and I. G. Tollis, “A Framework for User- Grouped Circular Drawings,” Graph Drawing, Vol. 2912, 2004, pp. 135-146. doi:10.1007/978-3-540-24595-7_13
[22]	J. M. Six and I. G. Tollis, “A Framework for Circular Drawings of Networks,” Graph Drawing, Vol. 1731, 1999, pp. 107-116. doi:10.1007/3-540-46648-7_11
[23]	J. Ellson, E. Gansner and L. Koutsofios, “GraphViz— Open Source Graph Drawing Tools,” Graph Drawing, Vol. 2265, 2002, pp. 594-597. doi:10.1007/3-540-45848-4_57
[24]	M. Simonato, “An Introduction to GraphViz,” Linux & Unix, Excerpts, Linux Devcenter, 2004.
[25]	A. Aho, J. Hopcroft and J. Ulman, “The Design and Ana- lysis of Computer Algorithms,” Addison-Wesley, Boston, 1974.