Том 15, номер 5, 2008 г., Стр. 61-75
УДК 519.101
П. В. Салимов
Существование бесконечного слова, последовательность графов Рози которого содержит подпоследовательность гомеоморфов заданных орграфов
Аннотация:
Объект изучения — бесконечные слова над конечным алфавитом. Доказано, что всякая последовательность конечных сильно связных орграфов с максимальными полустепенями исхода и захода, равными $s$, поэлементно гомеоморфна подпоследовательности графов Рози некоторого равномерно рекуррентного бесконечного слова над $s$-буквенным алфавитом.
Ключевые слова: бесконечные слова, равномерная рекуррентность, граф Рози, граф де Брейна.
Салимов Павел Вадимович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ch.cat.s.smile@gmail.com
Статья поступила 14 апреля 2008 г.
Исправленный вариант — 18 августа 2008 г.
