Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/77888
Title: NFASync: Программный комплекс для вычисления порога синхронизации недетерминированных конечных автоматов
Patent Number: 2018663225
Authors: Шабана, Х. М. Д.
Issue Date: 2018-10-24
Abstract: Программный комплекс предназначен для экспериментального исследования скорости различных вариантов синхронизации недетерминированных конечных автоматов. Он основан на редукции задачи о синхронизации данного недетерминированного автомата словом данной длины к задаче выполнимости для пропозициональных формул с последующим вызовом SAT-солвера, т.е. специализированной программы для решения задачи выполнимости, и состоит из нескольких подпрограмм. Основная подпрограмма кодирует действие букв на состояния автомата с помощью набора формул в конъюнктивной нормальной форме, подобранного так, что этот набор формул выполним тогда и только тогда, когда автомат имеет синхронизирующее слово данной длины. Подпрограмма на входе получает описание автомата в виде некоторого массива и длину потенциального синхронизирующего слова, а на выходе возвращает набор формул в формате DIMACS. Кроме того, программный комплекс включает подпрограммы для генерации случайных автоматов и ряд служебных подпрограмм для накопления и последующей обработки экспериментальных результатов.
Keywords: COMPUTER SOFTWARE
ПРОГРАММА ДЛЯ ЭВМ
URI: http://hdl.handle.net/10995/77888
RSCI ID: 39304254
PURE ID: 12999848
Patent Type: Регистрация программы для ЭВМ
Patent Owner: Федеральное государственное автономное образовательное учреждение высшего образования «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»
Appears in Collections:Патенты и изобретения

Files in This Item:
File Description SizeFormat 
2018663225.pdf191,07 kBAdobe PDFView/Open
2018663225_blank.pdf841,74 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.