Synchronization of Automata with One Undefined or Ambiguous Transition

1. Burkhard, H.V.: Zum Längenproblem homogener Experimente an determinierten und nicht-deterministischen Automaten. Elektronische Informationsverarbeitung und Kybernetik 12, 301–306 (1976)

   MathSciNet  MATH  Google Scholar 

2. Černý, J.: Poznámka k homogénnym experimentom s konečnými automatmi. Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14, 208–216 (1964) (in Slovak)

   MATH  Google Scholar 

3. Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19, 500–510 (1990)

   Article  MathSciNet  MATH  Google Scholar 

4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

   Google Scholar 

5. Gazdag, Z., Ivan, S., Nagy-Gyorgy, J.: Improved upper bounds on synchronizing nondeterministic automata. Information Processing Letters 109(17), 986–990 (2009)

   Article  MathSciNet  MATH  Google Scholar 

6. Imreh, B., Steinby, M.: Directable nondeterministic automata. Acta Cybernetica 14, 105–115 (1999)

   MathSciNet  MATH  Google Scholar 

7. Imreh, B., Imreh, C., Ito, M.: On directable nondeterministic trapped automata. Acta Cybernetica 16, 37–45 (2003)

   MathSciNet  MATH  Google Scholar 

8. Ito, M., Shikishima-Tsuji, K.: Some Results on Directable Automata. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever (Salomaa Festschrift). LNCS, vol. 3113, pp. 125–133. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

9. Ito, M.: Algebraic Theory of Automata and Languages. World Scientific, Singapore (2004)

   Book  MATH  Google Scholar 

10. Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254–266 (1977)

    Google Scholar 

11. Martyugin, P.: Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata. Diskretn. Anal. Issled. Oper. 15(4), 44–56 (2008)

    MathSciNet  MATH  Google Scholar 

12. Martyugin, P.V.: A Lower Bound for the Length of the Shortest Carefully Synchronizing Words. Russian Mathematics (Iz. VUZ) 54(1), 46–54 (2010)

    MathSciNet  MATH  Google Scholar 

13. Martyugin, P.V.: Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 288–302. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

14. Trahtman, A.N.: Modifying the Upper Bound on the Length of Minimal Synchronizing Word. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol. 6914, pp. 173–180. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

15. Volkov, M.V.: Synchronizing Automata and the Černý Conjecture. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11–27. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

Download references