Document Open Access Logo

Synchronizing Strongly Connected Partial DFAs

Authors Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, Marek Szykuła

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.12.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Author Details

Mikhail V. Berlinkov
  • Institute of Natural Sciences and Mathematics, Ural Federal University, Ekaterinburg, Russia
Robert Ferens
  • Institute of Computer Science, University of Wrocław, Poland
Andrew Ryzhikov
  • Université Gustave Eiffel, LIGM, Marne-la-Vallée, France
Marek Szykuła
  • Institute of Computer Science, University of Wrocław, Poland

Funding

  • Ferens, Robert: Supported in part by the National Science Centre, Poland under project number 2017/25/B/ST6/01920.
  • Szykuła, Marek: Supported in part by the National Science Centre, Poland under project number 2017/25/B/ST6/01920.

Acknowledgements

We are grateful to the anonymous reviewers for useful comments and recent literature references.

Cite AsGet BibTex

Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła. Synchronizing Strongly Connected Partial DFAs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.12

Abstract

We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is called synchronizing if it has a word (called a reset word) whose action brings a non-empty subset of states to a unique state and is undefined for all other states. While in the general case the problem of checking whether a partial DFA is synchronizing is PSPACE-complete, we show that in the strongly connected case this problem can be efficiently reduced to the same problem for a complete DFA. Using combinatorial, algebraic, and formal languages methods, we develop techniques that relate main synchronization problems for strongly connected partial DFAs with the same problems for complete DFAs. In particular, this includes the Černý and the rank conjectures, the problem of finding a reset word, and upper bounds on the length of the shortest reset words of literal automata of finite prefix codes. We conclude that solving fundamental synchronization problems is equally hard in both models, as an essential improvement of the results for one model implies an improvement for the other.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Mathematics of computing → Combinatorics
Keywords
  • Černý conjecture
  • literal automaton
  • partial automaton
  • prefix code
  • rank conjecture
  • reset threshold
  • reset word
  • synchronizing automaton
  • synchronizing word

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P. Babari, K. Quaas, and M. Shirmohammadi. Synchronizing data words for register automata. In MFCS, pages 15:1-15:15, 2016. Google Scholar
  2. M.-P. Béal, E. Czeizler, J. Kari, and D. Perrin. Unambiguous automata. Mathematics in Computer Science, 1(4):625-638, 2008. Google Scholar
  3. M. Berlinkov. On Two Algorithmic Problems about Synchronizing Automata. In Developments in Language Theory, LNCS, pages 61-67. Springer, 2014. Google Scholar
  4. M. Berlinkov and M. Szykuła. Algebraic synchronization criterion and computing reset words. Information Sciences, 369:718-730, 2016. Google Scholar
  5. J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  6. M. T. Biskup and W. Plandowski. Shortest synchronizing strings for Huffman codes. Theoretical Computer Science, 410(38-40):3925-3941, 2009. Google Scholar
  7. V. Bruyère. On maximal codes with bounded synchronization delay. Theoretical Computer Science, 204(1):11-28, 1998. Google Scholar
  8. J. Černý. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208-216, 1964. In Slovak. Google Scholar
  9. D. Chistikov, P. Martyugin, and M. Shirmohammadi. Synchronizing automata over nested words. Journal of Automata, Languages and Combinatorics, 24(2-4):219-251, 2019. Google Scholar
  10. L. Doyen, L. Juhl, K. G. Larsen, N. Markey, and M. Shirmohammadi. Synchronizing words for weighted and timed automata. In FSTTCS, pages 121-132, 2014. Google Scholar
  11. L. Doyen, T. Massart, and M. Shirmohammadi. Robust Synchronization in Markov Decision Processes. In CONCUR, pages 234-248, 2014. Google Scholar
  12. L. Doyen, T. Massart, and M. Shirmohammadi. The complexity of synchronizing Markov decision processes. J. Comput. Syst. Sci., 100:96-129, 2019. Google Scholar
  13. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19:500-510, 1990. Google Scholar
  14. T. Harju and D. Nowotka. On unique factorizations of primitive words. Theor. Comput. Sci., 356(1-2):186-189, 2006. Google Scholar
  15. J. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189-196. Academic Press, 1971. Google Scholar
  16. D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952. Google Scholar
  17. B. Imreh and M. Steinby. Directable nondeterministic automata. Acta Cybern., 14(1):105-115, 1999. Google Scholar
  18. J. Kari. A counter example to a conjecture concerning synchronizing word in finite. EATCS Bulletin, 73:146-147, 2001. Google Scholar
  19. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295(1-3):223-232, 2003. Google Scholar
  20. J. Kari, A. Ryzhikov, and A. Varonka. Words of minimum rank in deterministic finite automata. In Developments in Language Theory - 23rd International Conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, Proceedings, pages 74-87, 2019. Google Scholar
  21. S. Kiefer and C. Mascle. On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words. In STACS, LIPIcs, 2019. Google Scholar
  22. K. G. Larsen, S. Laursen, and J. Srba. Synchronizing strategies under partial observability. In International Conference on Concurrency Theory, pages 188-202. Springer, 2014. Google Scholar
  23. B. K. Natarajan. An algorithmic approach to the automated design of parts orienters. In Foundations of Computer Science, 27th Annual Symposium on, pages 132-142, 1986. Google Scholar
  24. J.-E. Pin. Utilisation de l'algèbre linéaire en théorie des automates. In Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées II, AFCET, pages 85-92, 1978. In French. Google Scholar
  25. J.-E. Pin. On two combinatorial problems arising from automata theory. In Proceedings of the International Colloquium on Graph Theory and Combinatorics, volume 75 of North-Holland Mathematics Studies, pages 535-548, 1983. Google Scholar
  26. I. K. Rystsov. Polynomial complete problems in automata theory. Information Processing Letters, 16(3):147-151, 1983. Google Scholar
  27. I. K. Rystsov. Reset words for commutative and solvable automata. Theoretical Computer Science, 172(1-2):273-279, 1997. Google Scholar
  28. A. Ryzhikov. Mortality and synchronization of unambiguous finite automata. In Combinatorics on Words - 12th International Conference, WORDS 2019, Loughborough, UK, September 9-13, 2019, Proceedings, pages 299-311, 2019. Google Scholar
  29. A. Ryzhikov and M. Szykuła. Finding Short Synchronizing Words for Prefix Codes. In Igor Potapov, Paul Spirakis, and James Worrell, editors, MFCS 2018, volume 117 of LIPIcs, pages 21:1-21:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  30. S. Sandberg. Homing and synchronizing sequences. In Model-Based Testing of Reactive Systems, volume 3472 of LNCS, pages 5-33. Springer, 2005. Google Scholar
  31. H. Shabana. Exact synchronization in partial deterministic automata. Journal of Physics: Conference Series, 1352:012047, 2019. Google Scholar
  32. Y. Shitov. An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata. Journal of Automata, Languages and Combinatorics, 24(2-4):367-373, 2019. Google Scholar
  33. M. Szykuła. Improving the Upper Bound on the Length of the Shortest Reset Word. In STACS 2018, LIPIcs, pages 56:1-56:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  34. N. F. Travers and J. P. Crutchfield. Exact Synchronization for Finite-State Sources. Journal of Statistical Physics, 145(5):1181-1201, 2011. Google Scholar
  35. L. Trevisan. Notes on state minimization. https://people.eecs.berkeley.edu/~luca/cs172-07/notemindfa.pdf, 2007.
  36. M. V. Volkov. Synchronizing automata and the Cerný conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
  37. M. V. Volkov. Slowly synchronizing automata with idempotent letters of low rank. Journal of Automata, Languages and Combinatorics, 24(2-4):375-386, 2019. Google Scholar
  38. Vojtech Vorel. Subset synchronization and careful synchronization of binary finite automata. Int. J. Found. Comput. Sci., 27(5):557-578, 2016. Google Scholar
  39. CM Weinbaum. Unique subwords in nonperiodic words. Proceedings of the American Mathematical Society, 109(3):615-619, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact