Geodesic
$D_2$-synchronization in nondeterministic automata
Ural mathematical journal, Tome 4 (2018) no. 2, pp. 99-110 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We approach the problem of computing a $D_2$-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.
Keywords: Nondeterministic automata, Synchronizing word, SAT solver. 
@article{UMJ_2018_4_2_a10,
     author = {Hanan Shabana},
     title = {$D_2$-synchronization in nondeterministic automata},
     journal = {Ural mathematical journal},
     pages = {99--110},
     year = {2018},
     volume = {4},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2018_4_2_a10/}
}
TY  - JOUR
AU  - Hanan Shabana
TI  - $D_2$-synchronization in nondeterministic automata
JO  - Ural mathematical journal
PY  - 2018
SP  - 99
EP  - 110
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UMJ_2018_4_2_a10/
LA  - en
ID  - UMJ_2018_4_2_a10
ER  - 
%0 Journal Article
%A Hanan Shabana
%T $D_2$-synchronization in nondeterministic automata
%J Ural mathematical journal
%D 2018
%P 99-110
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/UMJ_2018_4_2_a10/
%G en
%F UMJ_2018_4_2_a10
Hanan Shabana. $D_2$-synchronization in nondeterministic automata. Ural mathematical journal, Tome 4 (2018) no. 2, pp. 99-110. http://geodesic.mathdoc.fr/item/UMJ_2018_4_2_a10/

[1] Biere A., “Yet another local search solver and lingeling and friends entering the SAT Competition 2014”, Proceedings of SAT Competition 2014: Solver and Benchmark Descriptions, University of Helsinki, 2014, 39–40 http://fmv.jku.at/papers/Biere-SAT-Competition-2014.pdf

[2] de Bondt M., Don H., Zantema H., Lower bounds for synchronizing word lengths in partial automata, 2018., arXiv: 1801.10436

[3] Eén N., S{ö}rensson N., “An extensible SAT-solver”, Lect. Notes Comput. Sci., 2919, Theory and Applications of Satisfiability Testing (SAT 2003) (2004), 502–518 | DOI

[4] Eén N., S{ö}rensson N., The MiniSat Page http://minisat.se

[5] Gomes C.P., Kautz H., Sabharwal A., Selman B., “Satisfiability Solvers”, Ch. 2., Handbook of Knowledge Representation, Elsevier, 2008, 89–134 | DOI

[6] Güniçen C., Erdem E., Yenigün H., “Generating shortest synchronizing sequences using Answer Set Programming”, Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 117–127, arXiv: . 1312.6146

[7] Imreh B., Steinby M., “Directable nondeterministic automata”, Acta Cybernetica, 14:1 (1999), 105–115 | MR | Zbl

[8] Kisielewicz A., Kowalski J., Szykuła M. Computing the shortest reset words of synchronizing automata, J. Comb. Optim., 29:1 (2015), 88–124 | DOI | MR | Zbl

[9] Martyugin P., “Synchronization of automata with one undefined or ambiguous transition”, Lect. Notes Comput. Sci., 7381, Implementation and Application of Automata (CIAA 2012) (2012), 278–288 | DOI | MR | Zbl

[10] Rystsov I.K., “Polynomial complete problems in automata theory”, Inf. Process. Lett., 16:3 (1983), 147–151 | DOI | MR | Zbl

[11] Rystsov I.K. Asymptotic estimate of the length of a diagnostic word for a finite automaton, Cybernetics, 16:1 (1980), 194–198 | DOI | MR | Zbl

[12] Shabana H., Volkov M.V., “Using Sat solvers for synchronization issues in nondeterministic automata”, Siberian Electronic Math. Reports, 15 (2018), 1426–1442 http://semr.math.nsc.ru/v15/p1426-1442.pdf

[13] Skvortsov E., Tipikin E., “Experimental study of the shortest reset word of random automata”, Lect. Notes Comput. Sci., 6807, Implementation and Application of Automata (CIAA 2011) (2011), 290–298 | DOI | MR | Zbl

[14] Soos M., CryptoMiniSat 2 http://www.msoos.org/cryptominisat2/