Синхронизация конечных атомов

Proyecto: Award Project

Detalles del proyecto

Description

Конечный детерминированный автомат A называется синхронизируемым, если существует слово w во входном алфавите этого автомата, переводящее А в одно выделенное состояние независимо от текущего состояния автомата, т.е. обеспечивающее равенство q.w=q'.w для всех состояний q,q' автомата А. Любое слово с таким свойством называется синхронизирующим для автомата A. Синхронизируемые автоматы являются прозрачной и полезной моделью дискретных управляемых систем, способных к устойчивому функционированию при наличии помех. Теория таких автоматов активно развивается с начала 60-х годов прошлого века благодаря двум основным обстоятельствам. Во-первых, синхронизируемые автоматы имеют многочисленные приложения в различных областях математики, информатики и инженерии, таких, как тестирование программных систем и протоколов, промышленная робототехника, помехоустойчивое кодирование, символическая динамика, теория подстановочных систем и др. Во-вторых, теория синхронизируемых автоматов оказалась богатой на весьма нетривиальные задачи. Здесь классическим примером является гипотеза Черни, утверждающая, что синхронизируемый автомат с n состояниями всегда есть синхронизирующее слово длины (n-1)^2. Гипотеза Черни обсуждается в литературе более полувека и до сих пор не подтверждена и не опровергнута. Интерес к ней привлекает многочисленных исследователей ко всему кругу вопросов, связанных с концепцией синхронизируемости. Предыдущие обзоры по синхронизируемым автоматам устарели, так как большая часть описанных в них результатов перекрыта новейшими достижениями. Кроме того, теория синхронизируемых автоматов в последнее время существенно расширила и набор исследуемых объектов, и спектр решаемых задач. Конкретно, наиболее популярными источниками в обсуждаемой области пока остаются два обзора: [1] Sandberg S. (2005) Homing and Synchronizing Sequences. In: Model-Based Testing of Reactive Systems. Lecture Notes in Computer Science, vol. 3472. Springer, 5-33 (93 цитирования в Google Scholar, 62 цитирования в Scopus) [2] Volkov M.V. (2008) Synchronizing Automata and the Černý Conjecture. In: Language and Automata Theory and Applications. LATA 2008. Lecture Notes in Computer Science, vol. 5196. Springer, 11-27 (260 цитирований в Google Scholar, 153 цитирования в Scopus; файл статьи приложен к заявке) Видно, что оба эти обзора появились сравнительно давно и уже по числу статей, цитирующих указанные обзоры, понятно, что массив информации, появившейся после их опубликования, весьма значителен. Что касается тематики, то и в [1], и в [2] обсуждаются только классические детерминированные автоматы и совсем не затрагиваются обобщения. Планируемый обзор призван отразить не только классические, но и новые направления. В частности, впервые будет дан подробный анализ различных вариантов понятия синхронизируемости для частичных и недетерминированных автоматов. (В литературе рассматриваются по крайней мере пять таких вариантов, каждый из которых по-своему обобщает приведенное выше определение синхронизируемости.) Предполагается также обсудить синхронизируемость некоторых других моделей, рассматриваемых в литературе: временные автоматы, взвешенные автоматы, автоматы с выходом, автоматы над арочно-аннотированными последовательностями, и др. Будут детально освещены замечательные прорывы, достигнутые в последнее время в задаче о синхронизации случайных автоматов (результаты М.В.Берлинкова и С.Нико), в частности, доказательство гипотезы Камерона о том, что случайный детерминированный автомат с n состояниями двумя входными буквами синхронизируем с вероятностью 1-\Theta(1/n). В теории автоматов все большую роль играют вычислительные эксперименты. В обзоре будут суммированы и проанализированы накопленные экспериментальные результаты, а также намечены направления для новых экспериментальных исследований. Планируется систематизировать нерешенные вопросы теории и предложить несколько новых проблем. Планируемый объем обзора – около 60 журнальных страниц без учета библиографии.
EstadoFinalizado
Fecha de inicio / finalización efectiva07/11/201931/08/2020

Type of Financial Sources

  • RFFI

UrFU Research Division section that handles this grant (Kuibyshev, Mira)

  • Kuibyshev Research Division

GRNTI

  • 28.25.15