D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA
We approach the problem of computing a D2-synchronizing word of minimum length for a given nondeterministic automaton via its encoding as an instance of SAT and invoking a SAT solver. In addition, we report some of the experimental results obtained when we had tested our method on randomly generated...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin.
2018-12-01
|
| Series: | Ural Mathematical Journal |
| Subjects: | |
| Online Access: | https://umjuran.ru/index.php/umj/article/view/136 |
| _version_ | 1828419323245363200 |
|---|---|
| author | Hanan Shabana |
| author_facet | Hanan Shabana |
| author_sort | Hanan Shabana |
| collection | DOAJ |
| description | We approach the problem of computing a D2-synchronizing word of minimum length for a given nondeterministic automaton via its encoding as an instance of SAT and invoking a SAT solver. In addition, we report some of the experimental results obtained when we had tested our method on randomly generated automata and certain benchmarks. |
| first_indexed | 2024-12-10T14:51:19Z |
| format | Article |
| id | doaj.art-66ea1531bd7a43aebfa5f503ce7e3943 |
| institution | Directory Open Access Journal |
| issn | 2414-3952 |
| language | English |
| last_indexed | 2024-12-10T14:51:19Z |
| publishDate | 2018-12-01 |
| publisher | Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin. |
| record_format | Article |
| series | Ural Mathematical Journal |
| spelling | doaj.art-66ea1531bd7a43aebfa5f503ce7e39432022-12-22T01:44:26ZengKrasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin.Ural Mathematical Journal2414-39522018-12-014210.15826/umj.2018.2.01166D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATAHanan Shabana0Institute of Natural Sciences and Mathematics, Ural Federal University, 51 Lenin aven., Ekaterinburg, Russia, 620000; Faculty of Electronic Engineering, Menoufia UniversityWe approach the problem of computing a D2-synchronizing word of minimum length for a given nondeterministic automaton via its encoding as an instance of SAT and invoking a SAT solver. In addition, we report some of the experimental results obtained when we had tested our method on randomly generated automata and certain benchmarks.https://umjuran.ru/index.php/umj/article/view/136Nondeterministic automata, Synchronizing word, SAT solver |
| spellingShingle | Hanan Shabana D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA Ural Mathematical Journal Nondeterministic automata, Synchronizing word, SAT solver |
| title | D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA |
| title_full | D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA |
| title_fullStr | D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA |
| title_full_unstemmed | D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA |
| title_short | D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA |
| title_sort | d2 synchronization in nondeterministic automata |
| topic | Nondeterministic automata, Synchronizing word, SAT solver |
| url | https://umjuran.ru/index.php/umj/article/view/136 |
| work_keys_str_mv | AT hananshabana d2synchronizationinnondeterministicautomata |