Synchronizing Series-Parallel Deterministic Finite Automata With Loops and Related Problems
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 7

We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2021005
Classification : 68Q25, 68Q45
Keywords: Synchronizing words, series-parallel graphs, parameterized complexity 
@article{ITA_2021__55_1_A9_0,
     author = {Bruchertseifer, Jens and Fernau, Henning},
     editor = {Holzer, Markus and Sempere, Jos\'e M.},
     title = {Synchronizing {Series-Parallel} {Deterministic} {Finite} {Automata} {With} {Loops} and {Related} {Problems}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021005},
     mrnumber = {4289542},
     zbl = {1508.68186},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021005/}
}
TY  - JOUR
AU  - Bruchertseifer, Jens
AU  - Fernau, Henning
ED  - Holzer, Markus
ED  - Sempere, José M.
TI  - Synchronizing Series-Parallel Deterministic Finite Automata With Loops and Related Problems
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021005/
DO  - 10.1051/ita/2021005
LA  - en
ID  - ITA_2021__55_1_A9_0
ER  - 
%0 Journal Article
%A Bruchertseifer, Jens
%A Fernau, Henning
%E Holzer, Markus
%E Sempere, José M.
%T Synchronizing Series-Parallel Deterministic Finite Automata With Loops and Related Problems
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021005/
%R 10.1051/ita/2021005
%G en
%F ITA_2021__55_1_A9_0
Bruchertseifer, Jens; Fernau, Henning. Synchronizing Series-Parallel Deterministic Finite Automata With Loops and Related Problems. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 7. doi: 10.1051/ita/2021005

[1] M. Béal, M. V. Berlinkov and D. Perrin, A quadratic upper bound on the size of a synchronizing word in one-cluster automata. Int. J. Found. Comp. Sci. 22 (2011) 277–288. | MR | Zbl | DOI

[2] M. V. Berlinkov, Approximating the minimum length of synchronizing words is hard. Theory Comput. Syst. 54 (2014) 211–223. | MR | Zbl | DOI

[3] T. Bläsius, T. Friedrich, J. Lischeid, K. Meeks and M. Schirneck, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, in Algorithm Engineering and Experiments (ALENEX). SIAM (2019) 130–143. | Zbl

[4] H. Bodlaender, R. G. Downey, M. R. Fellows and H. T. Wareham, The parameterized complexity of sequence alignment and consensus. Theor. Comput. Sci. 147 (1995) 31–54. | MR | Zbl | DOI

[5] J. Bruchertseifer and H. Fernau, Synchronizing words and monoid factorization: a parameterized perspective, in Theory and Applications of Models of Computation, 16th International Conference, TAMC, edited by J. Chen, Q. Feng and J. Xu, eds., vol. 12337 of LNCS. Springer (2020) 352–364. | MR | Zbl | DOI

[6] J. A. Brzozowski and F. E. Fich, Languages of ℜ-trivial monoids. J. Comput. Syst. Sci. 20 (1980) 32–49. | MR | Zbl | DOI

[7] L. Cai, J. Chen, R. Downey and M. Fellows, On the parameterized complexity of short computation and factorization. Arch. Math. Logic 36 (1997) 321–337. | MR | Zbl | DOI

[8] J. Černý, A. Pirická and B. Rosenauerová, On directable automata. Kybernetika 7 (1971) 289–298. | MR | Zbl

[9] J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis 14 (1964) 208–216. | Zbl

[10] J. Černý, A note on homogeneous experiments with finite automata. J. Autom. Lang. Combinat. 24 (2019) 123–132. | MR | Zbl

[11] H. Cho, S. Jeong, F. Somenzi and C. Pixley, Synchronizing sequences and symbolic traversal techniques in test generation. J. Electr. Testing 4 (1993) 19–31. | DOI

[12] M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms. Springer (2015). | MR | DOI

[13] I. Dinur and D. Steurer, Analytical approach to parallel repetition, in Symposium on Theory of Computing, STOC, edited by D. B. Shmoys. ACM (2014) 624–633. | MR | Zbl | DOI

[14] R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013). | MR | Zbl

[15] D. Eppstein, Reset sequences for monotonic automata. SIAM J. Comput. 19 (1990) 500–510. | MR | Zbl | DOI

[16] D. Eppstein, Parallel recognition of series-parallel graphs. Inf. Comput. 98 (1992) 41–55. | MR | Zbl | DOI

[17] H. Fernau, Modern aspects of complexity within formal languages, in Language and Automata Theory and Applications - 13th International Conference, LATA, edited by C. Martín-Vide, A. Okhotin and D. Shapira. Vol. 11417 of LNCS. Springer (2019) 3–30. | MR | Zbl | DOI

[18] H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov and P. Wolf, Computational complexity of synchronization under regular constraints, in 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), edited by P. Rossmanith, P. Heggernes and J.-P. Katoen. Vol. 138 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019) 63:1–63:14. | Zbl

[19] H. Fernau, P. Heggernes and Y. Villanger, A multi-parameter analysis of hard problems on deterministic finite automata. J. Comput. Syst. Sci. 81 (2015) 747–765. | MR | Zbl | DOI

[20] H. Fernau and S. Hoffmann, Extensions to minimal synchronizing words. J. Autom. Lang. Combin. 24 (2019) 287–307. | MR | Zbl

[21] H. Fernau and D. Meister, Digraphs of bounded elimination width. Discr. Appl. Math. 168 (2014) 78–87. | MR | Zbl | DOI

[22] P. Frankl, An extremal problem for two families of sets. Eur. J. Combin. 3 (1982) 125–127. | MR | Zbl | DOI

[23] R. Ganian, P. Hliněný, J. Kneis, D. Meister, J. Obdrzálek, P. Rossmanith and S. Sikdar, Are there any good digraph width measures? J. Combin. Theory B 116 (2016) 250–286. | MR | Zbl | DOI

[24] W. Göhring, Minimal initializing word: a contribution to Černý’s conjecture. J. Autom. Lang. Combin. 2 (1997) 209–226. | MR | Zbl

[25] S. Guillemot, Parameterized complexity and approximability of the longest compatible sequence problem. Discr. Optim. 8 (2011) 50–60. | MR | Zbl | DOI

[26] S. Gulan, On the Relative Descriptional Complexity of Regular Expressions and Finite Automata, PhD thesis, Fachbereich IV, Universität Trier, Germany (2011).

[27] S. Gulan, Series parallel digraphs with loops—graphs encoded by regular expression. Theory Comput. Syst. 53 (2013) 126–158. | MR | Zbl | DOI

[28] F. Gurski and C. Rehs, Comparing linear width parameters for directed graphs. Theory Comput. Syst. 63 (2019) 1358–1387. | MR | Zbl | DOI

[29] J. Kari, Synchronizing finite automata on Eulerian digraphs. Theor. Comput. Sci. 295 (2003) 223–232. | MR | Zbl | DOI

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

[31] S. Kreutzer and O. Kwon, Digraphs of bounded width, in Classes of Directed Graphs, Springer Monographs in Mathematics. Springer (2018) 405–466. | Zbl | DOI

[32] P. Martyugin, Complexity of problems concerning reset words for some partial cases of automata. Acta Cybern. 19 (2009) 517–536. | MR | Zbl

[33] P. V. Martyugin, Complexity of problems concerning reset words for cyclic and Eulerian automata. Theor. Comp. Sci. 450 (2012) 3–9. | MR | Zbl | DOI

[34] P. V. Martyugin, Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theory Comput. Syst. 54 (2014) 293–304. | MR | Zbl | DOI

[35] R. H. Möhring, Computationally tractable classes of ordered sets, in Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, edited by I. Rival. Vol. 255 of NATO Science Series C. Springer (1989) 105–194. | MR | Zbl | DOI

[36] J. A. Montoya and C. Nolasco, On the synchronization of planar automata, in Language and Automata Theory and Applications – 12th International Conference, LATA, edited by S. T. Klein, C. Martín-Vide and D. Shapira. Vol. 10792 of LNCS. Springer (2018) 93–104. | MR | Zbl | DOI

[37] J. E. Pin, On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17 (1983) 535–548. | MR | Zbl

[38] E. V. Pribavkina and E. Rodaro, Synchronizing automata with finitely many minimal synchronizing words. Inf. Comput. 209 (2011) 568–579. | MR | Zbl | DOI

[39] J. Rho, F. Somenzi and C. Pixley, Minimum length synchronizing sequences of finite state machine, in Proceedings of the 30th Design Automation Conference, DAC, edited by A. E. Dunlop. ACM Press (1993) 463–468. | DOI

[40] I. K. Rystsov, On minimizing the length of synchronizing words for finite automata, in Theory of Designing of Computing Systems. Institute of Cybernetics of Ukrainian Acad. Sci. (1980) 75–82. (in Russian). | MR

[41] I. K. Rystsov, Reset words for commutative and solvable automata. Theor. Comput. Sci. 172 (1997) 273–279. | MR | Zbl | DOI

[42] A. Ryzhikov, Synchronization problems in automata without non-trivial cycles. Theor. Comput. Sci. 787 (2019) 77–88. | MR | Zbl | DOI

[43] S. Sandberg, Homing and synchronizing sequences, in Model-Based Testing of Reactive Systems, edited by M. Broy, B. Jonsson, J.-P. Katoen, M. Leucker, and A. Pretschner. Vol. 3472 of LNCS. Springer (2005) 5–33. | DOI

[44] Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata. J. Autom. Lang. Combinat. 24 (2019) 367–373. | MR | Zbl

[45] B. Steinberg, The Černý conjecture for one-cluster automata with prime length cycle. Theor. Comput. Sci. 412 (2011) 5487–5491. | MR | Zbl | DOI

[46] M. Szykuła, Improving the upper bound on the length of the shortest reset word, in 35th Symposium on Theoretical Aspects of Computer Science, STACS, edited by R. Niedermeier and B. Vallée. Vol. 96 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018) 1–13. | MR | Zbl

[47] U. C. Türker and H. Yenigün, Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata. Int. J. Found. Comput. Sci. 26 (2015) 99–122. | MR | Zbl | DOI

[48] J. Valdes, R. E. Tarjan and E. L. Lawler, The recognition of series parallel graphs. SIAM J. Comput. 11 (1982) 298–313. | MR | Zbl | DOI

[49] M. V. Volkov, Synchronizing automata and the Černý conjecture, in Language and Automata Theory and Applications, Second International Conference, LATA, edited by C. Martín-Vide, F. Otto and H. Fernau. Vol. 5196 of LNCS. Springer (2008) 11–27. | MR | Zbl | DOI

[50] M. V. Volkov, Synchronizing automata preserving a chain of partial orders. Theor. Comput. Sci. 410 (2009) 3513–3519. | MR | Zbl | DOI

[51] M. V. Volkov, Preface: Special issue on the Černý conjecture. J. Autom. Lang. Comb. 24 (2019) 119–121. | MR | Zbl

[52] V. Vorel, Complexity of a problem concerning reset words for Eulerian binary automata. Inf. Comput. 253 (2017) 497–509. | MR | Zbl | DOI

[53] V. Vorel and A. Roman, Parameterized complexity of synchronization and road coloring. Discr. Math. Theor. Comput. Sci. 17 (2015) 283–306. | MR | Zbl

[54] H. T. Wareham, The parameterized complexity of intersection and composition operations on sets of finite-state automata, in Implementation and Application of Automata, 5th CIAA 2000, edited by S. Yu and A. Păun. Vol. 2088 of LNCS. Springer (2001) 302–310. | MR | Zbl

[55] C. Yap, Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26 (1983) 287–300. | MR | Zbl | DOI

Cité par Sources :