Scientific Research

An Academic Publisher

**Some New Features and Algorithms for the Study of DFA** ()

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.

Share and Cite:

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.Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.