RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2018, том 15, страницы 1426–1442 (Mi semr1005)

Эта публикация цитируется в 1 статье

Дискретная математика и математическая кибернетика

Using SAT solvers for synchronization issues in non-deterministic automata

H. Shabanaab, M. V. Volkovb

a Faculty of Electronic Engineering, Menoufia University, Egypt
b Institute of Natural Sciences and Mathematics, Ural Federal University, Lenina 51, 620000 Yekaterinburg, Russia

Аннотация: We approach the problem of computing a $D_{3}$-synchronizing word of minimum length for a given nondeterministic automaton via its encoding as an instance of SAT and invoking a SAT solver. We also present some experimental results.

Ключевые слова: nondeterministic automaton, synchronizing word, SAT, SAT-solver, random automaton.

УДК: 519.713.1, 510.633

MSC: 68Q45

Поступила 15 января 2018 г., опубликована 15 ноября 2018 г.

Язык публикации: английский

DOI: 10.17377/semi.2018.15.117



Реферативные базы данных:


© МИАН, 2024