Around the Cerny conjecture
Автор: Central European University
Загружено: 2015-02-16
Просмотров: 1307
Speaker: Peter P. Palfy (Alfred Renyi Institute of Mathematics,
Hungarian Academy of Sciences)
Abstract: A famous open problem in automata theory is the half-a-century old Cerny conjecture. In common mathematical terms it can be formulated in the following way. Let us given some transformations (self-maps) of an n-element finite set. Assume that some composition of the given transformations is a constant map. The Cˇerny ́ conjecture asserts that there is a composition with at most (n−1)^2 factors that yields a constant map. The best known upper bound is cubic in n, it is based on a combinatorial result of Peter Frankl. I will outline a possible strategy that might lead to an improved upper bound (although it will not be suitable to prove the conjecture). I will pose some analogous group theoretic questions as well.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
