WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

n Следствие 3.1 Если n =3k для k >1, то pfa(n) 3 · 3 - Следствие 3.2 Если n =3r, то (m+1)n mn r- 3m 3m+n 3 - 3 n n 3 3 pfa(n) 3 · 3 + (3m +1) · - n =5 · 3 - o(3 ).

32m-1 - m=Теорема 3.1 Существует бесконечная последовательность ЧКА 3 {Apfa(n)|Apfa(n) ={Qn, {a, b, }, n}, |Qn| = n} такая, что длина кратчайшего бережно синхронизирующего слова для автоматов Apfa(n) растет быстрее любого многочлена от n.

Теорема 3.2 Существует бесконечная последовательность ЧКА 2 {Apfa(n)|Apfa(n) ={Qn, {a, b}, n}, |Qn| = n} такая, что длина кратчайшего бережно синхронизирующего слова для автоматов Apfa(n) растет быстрее любого многочлена от n.

Оставшаяся часть третьей главы посвящена самому весомому результату диссертации — доказательству PSPACE-полноты проверки заданного ЧКА на бережную синхронизируемость. Прежде всего, рассматривается следующая задача:

Задача: SY N(pfa) Дано: ЧКА A =(Q,, ).

Вопрос: Существует ли слово w, бережно синхронизирующее автомат A Параллельно доказывается PSPACE-полнота задачи проверки на существование слова w, бережно синхронизирующего заданный автомат такого, что длина w не превосходит заданное число L (задача SY N(pfa, L)), и задачи поиска длины кратчайшего бережно синхронизирующего слова для заданного ЧКА (задача SY N(pfa, = L)).

В разделе 3.2 доказывается принадлежность задач SY N(pfa), SY N(pfa, L) и SY N(pfa, = L) к классу PSPACE. Результат сформулирован в следующем предложении.

Предложение 3.2 Существует алгоритм, позволяющий решить задачи SY N(pfa), SY N(pfa, L) и SY N(pfa, = L), используя дополнительнуюпамять полиномиального размера.

Напомним, что если на вход задачи Z могут подаваться только автоматы над k-буквенным алфавитом, то перед названием задачи Z добавляется k-. В разделе 3.3 доказывается следующее предложение.

Предложение 3.3 Задача 2-SY N(pfa)-трудна.

Для доказательства PSPACE-трудности задачи 2-SY N(pfa) к н ей сводится классическая PSPACE-полная задача 3-ВЫПОЛНИМОСТЬ С КВАНТОРАМИ. Задача 2-SY N(pfa) — самая легкая из задач, рассматриваемых в связи с бережной синхронизируемостью ЧКА. Поэтому справедлива следующая теорема.

Теорема 3.3 1. Задачи SY N(pfa), SY N(pfa, L) и SY N(pfa, = L) являются PSPACE-полными.

2. Для любого k 2 задачи k-SY N(pfa), k-SY N(pfa, L) и kSY N(pfa, = L) являются PSPACE-полными.

Заключение Диссертационная работа посвящена построению оценок длины синхронизирующих слов и их обобщений, а также описанию сложности алгоритмических задач, связанных с синхронизируемостью и ее обобщениями.

Основные результаты диссертации:

1. Получена нижняя оценка максимальной длины кратчайшего синхронизирующего слова для двухбуквенных ДКА с нулем.

2. Описана сложность задач проверки заданного ДКА на синхронизируемость и задач поиска длины кратчайшего слова, синхронизирующего заданный ДКА, для автоматов из различных подклассов класса всех ДКА.

3. Получены нижние оценки максимальной длины кратчайшего бережно синхронизирующего слова для ЧКА как с произвольным алфавитом, так и с алфавитом фиксированного размера 4. Доказана PSPACE-полнота задачи проверки заданного ЧКА на бережную синхронизируемость.

Благодарности Автор выражает глубокую благодарность своему научному руководителю Д.С. Ананичеву и профессору М.В. Волкову за помощь в подготовке текстов и внимание к работе.

Список литературы [1] Клячко А.А., Рысцов И.К., Спивак М.А. Экстремальная комбинаторная задача связанная с длиной синхронизирующего слова в автомате // Кибернетика, №2, 1987, C. 16–20.

[2] Ananichev D. S., Volkov M. V. Synchronizing monotonic automata // Lecture Notes in Computer Science 2710, 2003, pp. 111–121.

[3] Ananichev D. S. The mortality threshold for partially monotonic automata // Lecture Notes in Computer Science, 3572, 2005, pp. 112– 121.

[4] ern J. Pozamka k homognnym eksperimentom s konecnmi avtomatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14, 1964, pp. 208– 216.

[5] Dubuc L. Sur les automates circulaires et la conjecture de ern // RAIRO Inform. Theor. Appl. 32, 1998, pp. 21–34.

[6] Eppstein D. Reset sequences for monotonic automata // SIAM J.

Comput. 19, 1990, pp. 500–510.

[7] Ito M., Shikishima-Tsuji K. Some results on directable automata // Lecture Notes in Computer Science, 3113, 2004, pp. 125–133.

[8] Mateescu A., Salomaa A. Many-valued truth functions, ern’s conjecture and road coloring // EATCS Bull. 68, 1999, pp. 134–150.

[9] Roman A., Forys W. Lower bound for the length of synchronizing words in partially-synchronizing automata // Proc. Int. Conf. SOFSEM, 2008.

[10] Rystsov I. K. Reset words for commutative and solvable automata // Theoretical Computer Science, 172, 1997, pp. 273–279.

[11] Rystsov I. K. Reset words for automata with simple idempotents // Cybernetics and System Analysis, 36, 2000, pp. 339–344.

[12] Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // Proc. Int. Conf. AUTOMATA, Palermo, 2007.

[13] Sandberg S. Homing and synchronizing sequences // Lecture Notes in Computer Science, 3472, 2005, pp. 5–33.

[14] Trahtman A. N. The ern conjecture for aperiodic automata // Discr.

Math. and Theoret. Comput. Sci. v. 9 2, 2007, pp. 3–10.

Работы автора по теме диссертации [15] Мартюгин П.В. Бережная синхронизируемость частичных автоматов // Труды 39-й региональной молодежной конференции "Проблемы теоретической и прикладной математики", Екатеринбург, 2008.

C. 336–341.

[16] Мартюгин П.В. Нижние оценки длины кратчайших бережно синхронизирующих слов для двух- и трёхбуквенных частичных автоматов // Дискретн. анализ и исслед. опер., 2008, 15:4, C. 44–56.

[17] Мартюгин П.В. PSPACE-полнота задачи проверки частичных автоматов на бережную инхронизируемость // Известия Уральского Государственного Университета, №62, 2008, С. 106–150.

[18] Martyugin P.V. Lower bounds for length of shortest carefully synchronizing words // Proc. Int. Conf. Workshop on Words and Automata, St.Petersburg, 2006.

[19] Martyugin P.V. Complexity of problems concerning reset words for commutative automata and automata with simple idempotents // Proc.

12th Int. Conf. Automata and Formal Languages, 2008, pp. 314–324.

[20] Martyugin P.V. A series of slowly synchronizable automata with a zero state over a small alphabet // Information and Computation, 206 (2008), pp. 1197–1203.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»