User menu

On the Interplay Between Babai and Černý’s Conjectures

Bibliographic reference Gonze, François ; Gusev, Vladimir ; Gerencser, Balazs ; Jungers, Raphaël M. ; Volkov, Mikhail V.. On the Interplay Between Babai and Černý’s Conjectures.21st International Conference, DLT 2017 (Liege, Belgium, du 07/08/2017 au 11/08/2017). In: Developments in Language Theory : Lecture Notes in Computer Science, Springer International Publishing2017, p. 185-197
Permanent URL
  1. Ananichev D. S., Volkov M. V., Gusev V. V., Primitive digraphs with large exponents and slowly synchronizing automata, 10.1007/s10958-013-1392-8
  2. Ananichev, D.S., Volkov, M.V.: Some results on Černy type problems for transformation semigroups. In: Araújo, I.M., Branco, M.J.J., Fernandes, V.H., Gomes, G.M.S. (eds.) Semigroups and Languages, pp. 23–42. World Scientific (2004)
  3. Araújo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: Synchronization and its friends. CoRR abs/1511.03184 (2015)
  4. Babai László, Seress Ákos, On the diameter of permutation groups, 10.1016/s0195-6698(05)80029-0
  5. Berstel Jean, Perrin Dominique, Reutenauer Christophe, Codes and Automata, ISBN:9781139195768, 10.1017/cbo9781139195768
  6. Bondar Eugenija A., Volkov Mikhail V., Completely Reachable Automata, Descriptional Complexity of Formal Systems (2016) ISBN:9783319411132 p.1-17, 10.1007/978-3-319-41114-9_1
  8. Cameron Peter J., Dixon’s theorem and random synchronization, 10.1016/j.disc.2012.06.002
  9. Černý, J.: Poznámka k homogénnym experimentom s konečnými automatami. Mat.-fyz. Časopis Slovenskej Akadémie Vied 14(3), 208–216 (1964). in Slovak
  10. Černý, J., Pirická, A., Rosenauerová, B.: On directable automata. Kybernetica 7, 289–298 (1971)
  11. Chevalier Pierre-Yves, Hendrickx Julien M., Jungers Raphael M., Reachability of consensus and synchronizing automata, 10.1109/cdc.2015.7402864
  12. Dixon John D., The probability of generating the symmetric group, 10.1007/bf01110210
  13. Don, H.: The Černý conjecture and 1-contracting automata. Electr. J. Comb. 23(3), P3.12 (2016)
  14. Dubuc L., Sur les automates circulaires et la conjecture de Černý, 10.1051/ita/1998321-300211
  15. Frankl P., An Extremal Problem for two Families of Sets, 10.1016/s0195-6698(82)80025-5
  16. Frettloh D., Sing B., Computing Modular Coincidences for Substitution Tilings and Point Sets, 10.1007/s00454-006-1280-9
  17. Friedman Joel, Joux Antoine, Roichman Yuval, Stern Jacques, Tillich Jean-Pierre, The action of a few permutations onr-tuples is quickly transitive, 10.1002/(sici)1098-2418(199807)12:4<335::aid-rsa2>;2-u
  18. Ganyushkin Olexandr, Mazorchuk Volodymyr, Classical Finite Transformation Semigroups, ISBN:9781848002807, 10.1007/978-1-84800-281-4
  19. Gerencsér, B., Gusev, V.V., Jungers, R.M.: Primitive sets of nonnegative matrices and synchronizing automata. CoRR abs/1602.07556 (2016)
  20. Gonze François, Jungers Raphaël M., On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata, 10.1137/15m1024603
  21. Grech, M., Kisielewicz, A.: The Černý conjecture for automata respecting intervals of a directed graph. Discrete Math. Theoret. Comput. Sci. 15(3), 61–72 (2013)
  22. Helfgott Harald, Seress Ákos, On the diameter of permutation groups, 10.4007/annals.2014.179.2.4
  23. Helfgott Harald A., Growth in groups: ideas and perspectives, 10.1090/s0273-0979-2015-01475-8
  24. Kari Jarkko, Synchronizing finite automata on Eulerian digraphs, 10.1016/s0304-3975(02)00405-x
  25. Klyachko A. A., Rystsov I. K., Spivak M. A., In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton, 10.1007/bf01071771
  26. Maslennikova, M.: Reset complexity of ideal languages. In: Bieliková, M. (ed.) SOFSEM 2012. Proceedings of the Institute of Computer Science Academy of Sciences of the Czech Republic, vol. II, pp. 33–44 (2012)
  27. Natarajan B. K., An algorithmic approach to the automated design of parts orienters, 10.1109/sfcs.1986.5
  28. Natarajan B.K., Some Paradigms for the Automated Design of Parts Feeders, 10.1177/027836498900800607
  29. Panteleev Pavel, Preset Distinguishing Sequences and Diameter of Transformation Semigroups, Language and Automata Theory and Applications (2015) ISBN:9783319155784 p.353-364, 10.1007/978-3-319-15579-1_27
  30. Pin, J.E.: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17, 535–548 (1983)
  31. Rystsov Igor, Reset words for commutative and solvable automata, 10.1016/s0304-3975(96)00136-3
  32. Rystsov I. K., Estimation of the length of reset words for automata with simple idempotents, 10.1007/bf02732984
  33. Saloff-Coste Laurent, Random Walks on Finite Groups, Probability on Discrete Structures (2004) ISBN:9783642056475 p.263-346, 10.1007/978-3-662-09444-0_5
  34. Salomaa Arto, Composition sequences for functions over a finite domain, 10.1016/s0304-3975(01)00227-4
  36. Steinberg Benjamin, The Černý conjecture for one-cluster automata with prime length cycle, 10.1016/j.tcs.2011.06.012
  37. Szykuła, M.: Improving the upper bound the length of the shortest reset words. CoRR abs/1702.05455 (2017)
  38. Volkov Mikhail V., Synchronizing Automata and the Černý Conjecture, Language and Automata Theory and Applications ISBN:9783540882817 p.11-27, 10.1007/978-3-540-88282-4_4
  39. Vorel Vojtěch, Subset Synchronization of Transitive Automata, 10.4204/eptcs.151.26
  40. Zubov, A.Y.: On the diameter of the group $$S_N$$ with respect to a system of generators consisting of a complete cycle and a transposition. Tr. Diskretn. Mat. 2, 112–150 (1998). in Russian