Document Open Access Logo

Synchronization Under Dynamic Constraints

Author Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.58.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Petra Wolf
  • Universität Trier, Fachbereich IV, Informatikwissenschaften, Germany

Funding

  • Wolf, Petra: DFG project FE 560/9-1.

Acknowledgements

I thank all colleges who commented on drafts of this work, esp. Henning Fernau.

Cite As Get BibTex

Petra Wolf. Synchronization Under Dynamic Constraints. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.58

Abstract

We introduce a new natural variant of the synchronization problem. Our aim is to model different constraints on the order in which a potential synchronizing word might traverse through the states. We discuss how a word can induce a state-order and examine the computational complexity of different variants of the problem whether an automaton can be synchronized with a word of which the induced order agrees with a given relation. While most of the problems are PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. One of them is the careful synchronization problem for partial weakly acyclic automata (which are partial automata whose states can be ordered such that no transition leads to a smaller state), which is shown to be solvable in time 𝒪(k² n²) where n is the size of the state set and k is the alphabet-size. The algorithm even computes a synchronizing word as a witness. This is quite surprising as the careful synchronization problem uses to be a hard problem for most classes of automata. We will also observe a drop in the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that (despite the partiality) the bound of the Černý conjecture also holds for partial weakly acyclic automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Synchronizing automaton
  • Černý conjecture
  • Reset sequence
  • Dynamic constraints
  • Computational complexity

Metrics

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

Related Versions

References

  1. Journal of Automata, Languages and Combinatorics - Essays on the Černý Conjecture. https://www.jalc.de/issues/2019/issue_24_2-4/content.html. Accessed: 10/1/2020.
  2. Dimitry S. Ananichev and Mikhail V. Volkov. Synchronizing monotonic automata. Theor. Comput. Sci., 327(3):225-239, 2004. Google Scholar
  3. Giorgio Ausiello, M. Protasi, A. Marchetti-Spaccamela, G. Gambosi, P. Crescenzi, and V. Kann. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin, Heidelberg, 1st edition, 1999. Google Scholar
  4. Marie-Pierre Béal and Dominique Perrin. Synchronised Automata, page 213–240. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2016. Google Scholar
  5. Jens Bruchertseifer and Henning Fernau. Synchronizing series-parallel automata with loops. In Rudolf Freund, Markus Holzer, and José M. Sempere, editors, Eleventh Workshop on Non-Classical Models of Automata and Applications, NCMA 2019, Valencia, Spain, July 2-3, 2019., pages 63-78. Österreichische Computer Gesellschaft, 2019. Google Scholar
  6. Ján Černý. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikalny Časopis Slovensk, 14(3):208-215, 1964. Google Scholar
  7. Ján Cerný. A note on homogeneous experiments with finite automata. Journal of Automata, Languages and Combinatorics, 24(2-4):123-132, 2019. Google Scholar
  8. Krishnendu Chatterjee and Laurent Doyen. Computation tree logic for synchronization properties. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 98:1-98:14, 2016. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Laurent Doyen, Line Juhl, Kim Guldstrand Larsen, Nicolas Markey, and Mahsa Shirmohammadi. Synchronizing words for weighted and timed automata. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, volume 29 of LIPIcs, pages 121-132. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  11. David Eppstein. Reset sequences for monotonic automata. SIAM J. Comput., 19(3):500-510, 1990. Google Scholar
  12. Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, and Petra Wolf. Computational complexity of synchronization under regular constraints. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 63:1-63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  13. Henning Fernau, Pinar Heggernes, and Yngve Villanger. A multi-parameter analysis of hard problems on deterministic finite automata. J. Comput. Syst. Sci., 81(4):747-765, 2015. Google Scholar
  14. Balázs Imreh and Magnus Steinby. Directable nondeterministic automata. Acta Cybern., 14(1):105-115, 1999. Google Scholar
  15. Pavel Martyugin. Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theory Comput. Syst., 54(2):293-304, 2014. Google Scholar
  16. Pavel V. Martyugin. Synchronization of automata with one undefined or ambiguous transition. In Nelma Moreira and Rogério Reis, editors, Implementation and Application of Automata - 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings, volume 7381 of Lecture Notes in Computer Science, pages 278-288. Springer, 2012. Google Scholar
  17. Balas K. Natarajan. An algorithmic approach to the automated design of parts orienters. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 132-142. IEEE Computer Society, 1986. Google Scholar
  18. I. K. Rystsov. On minimizing the length of synchronizing words for finite automata. In Theory of Designing of Computing Systems, pages 75-82. Institute of Cybernetics of Ukrainian Acad. Sci., 1980. (in Russian). Google Scholar
  19. Igor K. Rystsov. Polynomial complete problems in automata theory. Inf. Process. Lett., 16(3):147-151, 1983. Google Scholar
  20. Andrew Ryzhikov. Synchronization problems in automata without non-trivial cycles. Theor. Comput. Sci., 787:77-88, 2019. Google Scholar
  21. Andrew Ryzhikov and Anton Shemyakov. Subset synchronization in monotonic automata. Fundam. Inform., 162(2-3):205-221, 2018. Google Scholar
  22. 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 [The volume is the outcome of a research seminar that was held in Schloss Dagstuhl in January 2004], volume 3472 of Lecture Notes in Computer Science, pages 5-33. Springer, 2004. Google Scholar
  23. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. Google Scholar
  24. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. Google Scholar
  25. Avraham Trakhtman. The Černý conjecture for aperiodic automata. Discrete Mathematics & Theoretical Computer Science, 9(2), 2007. Google Scholar
  26. Uraz Cengiz Türker and Hüsnü Yenigün. Complexities of some problems related to synchronizing, non-synchronizing and monotonic automata. Int. J. Found. Comput. Sci., 26(1):99-122, 2015. Google Scholar
  27. 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 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, volume 5196 of Lecture Notes in Computer Science, pages 11-27. Springer, 2008. Google Scholar
  28. Vojtech Vorel and Adam Roman. Parameterized complexity of synchronization and road coloring. Discrete Mathematics & Theoretical Computer Science, 17(1):283-306, 2015. Google Scholar
  29. Petra Wolf. Synchronization under dynamic constraints. CoRR, abs/1910.01935, 2019. URL: http://arxiv.org/abs/1910.01935.
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 About DROPS Imprint Privacy Contact