Research ArticleOpen AccessGoogle Scholar indexed
Some New Features and Algorithms for the Study of DFA
Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
- 1 Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
Open Journal of Discrete Mathematics·Volume 02 (2012)·Pages 45–50·Published 26 April 2012·DOI10.4236/ojdm.2012.22008
Copy link · social · email
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.
KeywordsFinite AutomatonSynchronizing WordAlgorithmVisualization
- 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
- 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
- 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
- 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
- J. V. Rauff, “Way Back from Anywhere: Exploring the Road Coloring Conjecture,” Mathematical and Computer Education, Vol. 43, No.1, 2009, pp. 6-17.
- J. ?erny, “Poznamka k Homogenym Eksperimentom s Konechnymi Automatami,” Matematicko Fyzicalny ?asopis, Vol. 14, 1964, pp. 208-215.
- 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
- 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.
- 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
- 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.
- R. L. Adler and B. Weiss, “Similarity of Automorphisms of the Torus,” Memoirs of the American Mathematical Society, Providence, RI, 1970, p. 98.
- 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
- B. A. Rubshtein, “Generating Partitions of Markov Endomorphisms,” Functional Analysis Applications, Vol. 8, No. 1, 1974, pp. 84-85. doi:10.1007/BF02028320