Том 15, номер 4, 2008 г., Стр. 44-56
УДК 519.713.2
П. В. Мартюгин
Нижние оценки длины кратчайших бережно синхронизирующих слов для двух- и трёхбуквенных частичных автоматов
Аннотация:
Описывается понятие слов, бережно синхронизирующих частичные конечные автоматы (ЧКА). Бережная синхронизируемость ЧКА является естественным обобщением синхронизируемости детерминированных конечных автоматов. В статье доказывается, что нижние оценки величин порога бережной синхронизации для множеств двух- и трёхбуквенных автоматов с данным количеством состояний растут быстрее любого полинома от количества состояний.
Табл. 1, ил. 3, библиогр. 11.
Ключевые слова: автоматы, синхронизация.
Мартюгин Павел Владимироваич 1
1. Уральский гос. yниверситет им. М. Горького,
пр. Ленина 51, 620083 Екатеринбург, Россия
е-mail: martugin@mail.ru
Статья поступила 18 апреля 2008 г.
Исправленный вариант — 13 мая 2008 г.
