NFASync: Программный комплекс для вычисления порога синхронизации недетерминированных конечных автоматов
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
NFASync: Программный комплекс для вычисления порога синхронизации недетерминированных конечных автоматов
|
|
| Автор |
Шабана, Х. М. Д.
|
|
| Тематика |
COMPUTER SOFTWARE
ПРОГРАММА ДЛЯ ЭВМ |
|
| Описание |
Программный комплекс предназначен для экспериментального исследования скорости различных вариантов синхронизации недетерминированных конечных автоматов. Он основан на редукции задачи о синхронизации данного недетерминированного автомата словом данной длины к задаче выполнимости для пропозициональных формул с последующим вызовом SAT-солвера, т.е. специализированной программы для решения задачи выполнимости, и состоит из нескольких подпрограмм. Основная подпрограмма кодирует действие букв на состояния автомата с помощью набора формул в конъюнктивной нормальной форме, подобранного так, что этот набор формул выполним тогда и только тогда, когда автомат имеет синхронизирующее слово данной длины. Подпрограмма на входе получает описание автомата в виде некоторого массива и длину потенциального синхронизирующего слова, а на выходе возвращает набор формул в формате DIMACS. Кроме того, программный комплекс включает подпрограммы для генерации случайных автоматов и ряд служебных подпрограмм для накопления и последующей обработки экспериментальных результатов.
|
|
| Дата |
2019-11-11T05:47:14Z
2019-11-11T05:47:14Z 2018-10-24 |
|
| Тип |
Patent
Patent (info:eu-repo/semantics/patent) |
|
| Идентификатор |
2018616560
cec06bba-2d05-44e9-b9dc-bed33ae917f9 http://elar.urfu.ru/handle/10995/77888 39304254 |
|
| Язык |
ru
|
|