City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Автоматные слова
Inroduction to combinatorics on words

What: Lecture
When: Saturday, 15 October 2011, 19:05–20:40
Where: ПОМИ РАН
Slides: combinatoricsonwords_lecture_151011.pdf

Description

Предположим, конечный автомат получает на вход \( k \)-ичное разложение числа \( n \) и выдает символ \( w_n \). Последовательность символов \( w_0w_1w_2\dots \) называется \( k \)-автоматным словом. Каковы свойства таких слов? Как еще их можно охарактеризовать? Какие их свойства могут быть проверены конечными автоматами, полученными из исходного — вот, скажем, относится ли к ним избегание паттернов из предыдущей лекции?

Video