Document Open Access Logo

Computational Complexity of Synchronization under Regular Constraints

Authors Henning Fernau , Vladimir V. Gusev , Stefan Hoffmann , Markus Holzer , Mikhail V. Volkov , Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.63.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Henning Fernau
  • Fachbereich 4 - Abteilung Informatikwissenschaften, Universität Trier, Germany
Vladimir V. Gusev
  • Leverhulme Research Centre for Functional Materials Design, University of Liverpool, UK
Stefan Hoffmann
  • Fachbereich 4 - Abteilung Informatikwissenschaften, Universität Trier, Germany
Markus Holzer
  • Institut für Informatik, Universität Gießen, Germany
Mikhail V. Volkov
  • Institute of Natural Sciences and Mathematics, Ural Federal University, Yekaterinburg, Russia
Petra Wolf
  • Fachbereich 4 - Abteilung Informatikwissenschaften, Universität Trier, Germany

Funding

The financial support of the last two authors by the DFG-funded project FE560/9-1 is gratefully acknowledged. V. V. Gusev is supported by the Leverhulme Trust. M. V. Volkov is supported by the Ministry of Science and Higher Education of the Russian Federation, project no. 1.580.2016, and the Competitiveness Enhancement Program of Ural Federal University.

Acknowledgements

This project started during the workshop "Modern Complexity Aspects of Formal Languages" that took place at Trier University on February 11-15, 2019.

Cite AsGet BibTex

Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, and Petra Wolf. Computational Complexity of Synchronization under Regular Constraints. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.63

Abstract

Many variations of synchronization of finite automata have been studied in the previous decades. Here, we suggest studying the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We show that this synchronization problem becomes PSPACE-complete even for some constraint automata with two states and a ternary alphabet. In addition, we characterize constraint automata with arbitrarily many states for which the constrained synchronization problem is polynomial-time solvable. We classify the complexity of the constrained synchronization problem for constraint automata with two states and two or three letters completely and lift those results to larger classes of finite automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Finite automata
  • synchronization
  • computational complexity

Metrics

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

References

  1. Marco Almeida, Nelma Moreira, and Rogério Reis. Enumeration and generation with a string automata representation. Theoretical Computer Science, 387(2):93-102, 2007. URL: https://doi.org/10.1016/j.tcs.2007.07.029.
  2. Dmitry S. Ananichev, Mikhail V. Volkov, and Vladimir V. Gusev. Primitive digraphs with large exponents and slowly synchronizing automata. Journal of Mathematical Sciences, 192(3):263-278, 2013. URL: https://doi.org/10.1007/s10958-013-1392-8.
  3. Frédérique Bassino and Cyril Nicaud. Enumeration and random generation of accessible automata. Theoretical Computer Science, 381(1-3):86-104, 2007. URL: https://doi.org/10.1016/j.tcs.2007.04.001.
  4. Marie-Pierre Béal, Mikhail V. Berlinkov, and Dominique 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. URL: https://doi.org/10.1142/S0129054111008039.
  5. Mikhail V. Berlinkov. Approximating the minimum length of synchronizing words is hard. Theory of Computing Systems, 54(2):211-223, 2014. URL: https://doi.org/10.1007/s00224-013-9511-y.
  6. Mikhail V. Berlinkov, Robert Ferens, and Marek Szykuła. Complexity of preimage problems for deterministic finite automata. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, volume 117 of LIPIcs, pages 32:1-32:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.32.
  7. Vincent D. Blondel and Natacha Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, 351-352:91-98, 2002. URL: https://doi.org/10.1016/S0024-3795(01)00466-9.
  8. Ján Černý. Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis, 14(3):208-216, 1964. Google Scholar
  9. Michiel de Bondt, Henk Don, and Hans Zantema. Lower bounds for synchronizing word lengths in partial automata. International Journal of Foundations of Computer Science, 30(1):29-60, 2019. URL: https://doi.org/10.1142/S0129054119400021.
  10. Michael Domaratzki, Derek Kisman, and Jeffrey Shallit. On the number of distinct languages accepted by finite automata with n states. Journal of Automata, Languages and Combinatorics, 7(4):469-486, 2002. URL: https://doi.org/10.25596/jalc-2002-469.
  11. Henning Fernau and Andreas Krebs. Problems on finite automata and the exponential time hypothesis. Algorithms, 10(1):24, 2017. Google Scholar
  12. Zsolt Gazdag, Szabolcs Iván, and Judit Nagy-György. Improved upper bounds on synchronizing nondeterministic automata. Information Processing Letters, 109(17):986-990, 2009. URL: https://doi.org/10.1016/j.ipl.2009.05.007.
  13. Vladimir V. Gusev. Synchronizing automata of bounded rank. In Nelma Moreira and Rogério Reis, editors, Implementation and Application of Automata - 17th International Conference, CIAA, volume 7381 of LNCS, pages 171-179. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31606-7_15.
  14. Michael A. Harrison. A census of finite automata. Canadian Journal of Mathematics, 17:100–113, 1965. URL: https://doi.org/10.4153/CJM-1965-010-9.
  15. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2nd edition, 2001. Google Scholar
  16. Ravindran Kannan and Richard J. Lipton. Polynomial-time algorithm for the orbit problem. Journal of the ACM, 33(4):808-821, August 1986. URL: https://doi.org/10.1145/6490.6496.
  17. Zvi Kohavi and Niraj K. Jha. Switching and Finite Automata Theory. Cambridge University Press, 3rd edition, 2009. Google Scholar
  18. Dexter Kozen. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations of Computer Science, FOCS, pages 254-266. IEEE Computer Society, 1977. URL: https://doi.org/10.1109/SFCS.1977.16.
  19. Kim Guldstrand Larsen, Simon Laursen, and Jirí Srba. Synchronizing strategies under partial observability. In Paolo Baldan and Daniele Gorla, editors, Concurrency Theory - 25th International Conference, CONCUR, volume 8704 of LNCS, pages 188-202. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44584-6_14.
  20. Pavel Martyugin. Complexity of problems concerning reset words for some partial cases of automata. Acta Cybernetica, 19(2):517-536, 2009. Google Scholar
  21. Pavel V. 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. URL: https://doi.org/10.1007/s00224-013-9516-6.
  22. Rogério Reis, Nelma Moreira, and Marco Almeida. On the representation of finite automata. CoRR, abs/0906.2477, 2009. URL: http://arxiv.org/abs/0906.2477.
  23. Igor K. Rystsov. Polynomial complete problems in automata theory. Information Processing Letters, 16(3):147-151, 1983. URL: https://doi.org/10.1016/0020-0190(83)90067-4.
  24. Sven Sandberg. Homing and synchronizing sequences. In Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and Alexander Pretschner, editors, Model-Based Testing of Reactive Systems, Advanced Lectures, volume 3472 of LNCS, pages 5-33. Springer, 2005. URL: https://doi.org/10.1007/11498490_2.
  25. Yaroslav Shitov. An improvement to a recent upper bound for synchronizing words of finite automata. Technical Report arXiv:1901.06542, Cornell University, 2019. Google Scholar
  26. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM Symposium on Theory of Computing, STOC, pages 1-9. ACM, 1973. URL: https://doi.org/10.1145/800125.804029.
  27. Marek Szykuła. Improving the upper bound on the length of the shortest reset word. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS, volume 96 of LIPIcs, pages 56:1-56:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.56.
  28. Mikhail V. Volkov. Synchronizing automata and the Černý conjecture. In Carlos Martín-Vide, Friedrich Otto, and Henning Fernau, editors, Language and Automata Theory and Applications, Second International Conference, LATA, volume 5196 of LNCS, pages 11-27. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-88282-4_4.
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