Back
 OJDM  Vol.2 No.2 , April 2012
Some New Features and Algorithms for the Study of DFA
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.
Cite this paper: A. Trahtman, "Some New Features and Algorithms for the Study of DFA," Open Journal of Discrete Mathematics, Vol. 2 No. 2, 2012, pp. 45-50. doi: 10.4236/ojdm.2012.22008.
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.

 
 
Top