Document Open Access Logo

Complexity of Preimage Problems for Deterministic Finite Automata

Authors Mikhail V. Berlinkov, Robert Ferens, Marek Szykula

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.32.pdf
  • Filesize: 462 kB
  • 14 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, Wrocław, Poland
Marek Szykula
  • Institute of Computer Science, University of Wrocław, Wrocław, Poland

Funding

  • Berlinkov, Mikhail V.: Supported by Russian Foundation for Basic Research, grant no. 16-01-00795, and the Competitiveness Enhancement Program of Ural Federal University.
  • Ferens, Robert: Supported in part by the National Science Centre, Poland under project number 2014/15/B/ST6/00615.
  • Szykula, Marek: Supported in part by the National Science Centre, Poland under project number 2017/25/B/ST6/01920.

Cite AsGet BibTex

Mikhail V. Berlinkov, Robert Ferens, and Marek Szykula. Complexity of Preimage Problems for Deterministic Finite Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.32

Abstract

Given a subset of states S of a deterministic finite automaton and a word w, the preimage is the subset of all states that are mapped to a state from S by the action of w. We study the computational complexity of three problems related to the existence of words yielding certain preimages, which are especially motivated by the theory of synchronizing automata. The first problem is whether, for a given subset, there exists a word extending the subset (giving a larger preimage). The second problem is whether there exists a word totally extending the subset (giving the whole set of states) - it is equivalent to the problem whether there exists an avoiding word for the complementary subset. The third problem is whether there exists a word resizing the subset (giving a preimage of a different size). We also consider the variants of the problem where an upper bound on the length of the word is given in the input. Because in most cases our problems are computationally hard, we additionally consider parametrized complexity by the size of the given subset. We focus on the most interesting cases that are the subclasses of strongly connected, synchronizing, and binary automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • avoiding word
  • extending word
  • extensible subset
  • reset word
  • synchronizing automaton

Metrics

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

Related Versions

References

  1. D. S. Ananichev and V. V. Gusev. Approximation of Reset Thresholds with Greedy Algorithms. Fundamenta Informaticae, 145(3):221-227, 2016. Google Scholar
  2. D. S. Ananichev and M. V. Volkov. Synchronizing generalized monotonic automata. Theoretical Computer Science, 330(1):3-13, 2005. Google Scholar
  3. M.-P. Béal, M. Berlinkov, and D. Perrin. A quadratic upper bound on the size of a synchronizing word in one-cluster automata. International Journal of Foundations of Computer Science, 22(2):277-288, 2011. Google Scholar
  4. M. Berlinkov. Synchronizing Quasi-Eulerian and Quasi-one-cluster Automata. International Journal of Foundations of Computer Science, 24(6):729-745, 2013. Google Scholar
  5. M. Berlinkov. On Two Algorithmic Problems about Synchronizing Automata. In Developments in Language Theory, LNCS, pages 61-67. Springer, 2014. Google Scholar
  6. M. Berlinkov. On the probability of being synchronizable. In CALDAM, volume 9602 of LNCS, pages 73-84. Springer, 2016. Google Scholar
  7. M. Berlinkov and M. Szykuła. Algebraic synchronization criterion and computing reset words. Information Sciences, 369:718-730, 2016. Google Scholar
  8. J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  9. M. T. Biskup and W. Plandowski. Shortest synchronizing strings for Huffman codes. Theoretical Computer Science, 410(38-40):3925-3941, 2009. Google Scholar
  10. E. A. Bondar and M. V. Volkov. Completely reachable automata. In C. Câmpeanu, F. Manea, and J. Shallit, editors, DCFS, LNCS, pages 1-17. Springer, 2016. Google Scholar
  11. 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
  12. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19:500-510, 1990. Google Scholar
  13. P. Gawrychowski and D. Straszak. Strong inapproximability of the shortest reset word. In Mathematical Foundations of Computer Science, volume 9234 of LNCS, pages 243-255. Springer, 2015. Google Scholar
  14. M. Grech and A. Kisielewicz. The Černý conjecture for automata respecting intervals of a directed graph. Discrete Mathematics and Theoretical Computer Science, 15(3):61-72, 2013. Google Scholar
  15. K. Guldstrand Larsen, S. Laursen, and J. Srba. Synchronizing Strategies under Partial Observability. In P. Baldan and D. Gorla, editors, CONCUR 2014, pages 188-202. Springer, 2014. Google Scholar
  16. H. Jürgensen. Synchronization. Information and Computation, 206(9-10):1033-1044, 2008. Google Scholar
  17. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295(1-3):223-232, 2003. Google Scholar
  18. A. Kisielewicz, J. Kowalski, and M. Szykuła. Computing the shortest reset words of synchronizing automata. Journal of Combinatorial Optimization, 29(1):88-124, 2015. Google Scholar
  19. D. Kozen. Lower Bounds for Natural Proof Systems. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS, pages 254-266, 1977. Google Scholar
  20. P. Martyugin. Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata. Theory of Computing Systems, 54(2):293-304, 2014. Google Scholar
  21. J. Olschewski and M. Ummels. The complexity of finding reset words in finite automata. In Mathematical Foundations of Computer Science, volume 6281 of LNCS, pages 568-579. Springer, 2010. Google Scholar
  22. A. Roman and M. Szykuła. Forward and backward synchronizing algorithms. Expert Systems with Applications, 42(24):9512-9527, 2015. Google Scholar
  23. I. K. Rystsov. Polynomial complete problems in automata theory. Information Processing Letters, 16(3):147-151, 1983. Google Scholar
  24. S. Sandberg. Homing and synchronizing sequences. In Model-Based Testing of Reactive Systems, volume 3472 of LNCS, pages 5-33. Springer, 2005. Google Scholar
  25. B. Steinberg. The averaging trick and the Černý conjecture. International Journal of Foundations of Computer Science, 22(7):1697-1706, 2011. Google Scholar
  26. B. Steinberg. The Černý conjecture for one-cluster automata with prime length cycle. Theoretical Computer Science, 412(39):5487-5491, 2011. Google Scholar
  27. 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
  28. R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  29. A. N. Trahtman. The C̆erný conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science, 9(2):3-10, 2007. Google Scholar
  30. W.-G. Tzeng. The Equivalence and Learning of Probabilistic Automata. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS, pages 268-273. IEEE Computer Society, 1989. Google Scholar
  31. M. V. Volkov. Synchronizing automata and the C̆erný conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
  32. M. V. Volkov. Synchronizing automata preserving a chain of partial orders. Theoretical Computer Science, 410(37):3513-3519, 2009. Google Scholar
  33. V. Vorel. Subset Synchronization of Transitive Automata. In Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014), pages 370-381, 2014. Google Scholar
  34. V. Vorel. Complexity of a problem concerning reset words for Eulerian binary automata. Information and Computation, 253(Part 3):497-509, 2017. 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