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

Упорядоченность
Word combinatorics and its applications

What: Lecture
When: Thursday, 19 March 2015, 18:30–20:00
Where: ПОМИ РАН
Slides: wordscombinatorics_lecture_190315.pdf

Description

Лексикографический порядок. Слова Линдона-Ширшова. Теорема Линдона о каноническом разбиении слова. Периодичность плюс порядок. Локальные периоды. Теорема о критическом разбиении. Задача поиска по образцу с использованием константной памяти. Критическое разбиение и алгоритм Крошмора. Алгоритм Бреслауэра для реального времени.

Video