EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 55 (2021) RAIRO-Theor. Inf. Appl., 55 (2021) 7 References
Issue
RAIRO-Theor. Inf. Appl.
Volume 55, 2021
11th Workshop on Non-classical Models of Automata and Applications (NCMA 2019)
Article Number 7
Number of page(s) 24
DOI https://doi.org/10.1051/ita/2021005
Published online 22 July 2021
  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. [Google Scholar]
  2. M.V. Berlinkov, Approximating the minimum length of synchronizing words is hard. Theory Comput. Syst. 54 (2014) 211–223. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  6. J.A. Brzozowski and F.E. Fich, Languages of ℜ-trivial monoids. J. Comput. Syst. Sci. 20 (1980) 32–49. [Google Scholar]
  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. [Google Scholar]
  8. J. Černý, A. Pirická and B. Rosenauerová, On directable automata. Kybernetika 7 (1971) 289–298. [Google Scholar]
  9. J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis 14 (1964) 208–216. [Google Scholar]
  10. J. Černý, A note on homogeneous experiments with finite automata. J. Autom. Lang. Combinat. 24 (2019) 123–132. [Google Scholar]
  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. [Google Scholar]
  12. M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms. Springer (2015). [Google Scholar]
  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. [Google Scholar]
  14. R.G. Downey and M.R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013). [Google Scholar]
  15. D. Eppstein, Reset sequences for monotonic automata. SIAM J. Comput. 19 (1990) 500–510. [Google Scholar]
  16. D. Eppstein, Parallel recognition of series-parallel graphs. Inf. Comput. 98 (1992) 41–55. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  20. H. Fernau and S. Hoffmann, Extensions to minimal synchronizing words. J. Autom. Lang. Combin. 24 (2019) 287–307. [Google Scholar]
  21. H. Fernau and D. Meister, Digraphs of bounded elimination width. Discr. Appl. Math. 168 (2014) 78–87. [Google Scholar]
  22. P. Frankl, An extremal problem for two families of sets. Eur. J. Combin. 3 (1982) 125–127. [Google Scholar]
  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. [Google Scholar]
  24. W. Göhring, Minimal initializing word: a contribution to Černý’s conjecture. J. Autom. Lang. Combin. 2 (1997) 209–226. [Google Scholar]
  25. S. Guillemot, Parameterized complexity and approximability of the longest compatible sequence problem. Discr. Optim. 8 (2011) 50–60. [Google Scholar]
  26. S. Gulan, On the Relative Descriptional Complexity of Regular Expressions and Finite Automata, PhD thesis, Fachbereich IV, Universität Trier, Germany (2011). [Google Scholar]
  27. S. Gulan, Series parallel digraphs with loops—graphs encoded by regular expression. Theory Comput. Syst. 53 (2013) 126–158. [Google Scholar]
  28. F. Gurski and C. Rehs, Comparing linear width parameters for directed graphs. Theory Comput. Syst. 63 (2019) 1358–1387. [Google Scholar]
  29. J. Kari, Synchronizing finite automata on Eulerian digraphs. Theor. Comput. Sci. 295 (2003) 223–232. [Google Scholar]
  30. A. Kisielewicz, J. Kowalski and M. Szykuła, Computing the shortest reset words of synchronizing automata. J. Combin. Optim. 29 (2015) 88–124. [Google Scholar]
  31. S. Kreutzer and O. Kwon, Digraphs of bounded width, in Classes of Directed Graphs, Springer Monographs in Mathematics. Springer (2018) 405–466. [Google Scholar]
  32. P. Martyugin, Complexity of problems concerning reset words for some partial cases of automata. Acta Cybern. 19 (2009) 517–536. [Google Scholar]
  33. P.V. Martyugin, Complexity of problems concerning reset words for cyclic and Eulerian automata. Theor. Comp. Sci. 450 (2012) 3–9. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  37. J.E. Pin, On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17 (1983) 535–548. [Google Scholar]
  38. E.V. Pribavkina and E. Rodaro, Synchronizing automata with finitely many minimal synchronizing words. Inf. Comput. 209 (2011) 568–579. [Google Scholar]
  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. [Google Scholar]
  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). [Google Scholar]
  41. I.K. Rystsov, Reset words for commutative and solvable automata. Theor. Comput. Sci. 172 (1997) 273–279. [Google Scholar]
  42. A. Ryzhikov, Synchronization problems in automata without non-trivial cycles. Theor. Comput. Sci. 787 (2019) 77–88. [Google Scholar]
  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. [Google Scholar]
  44. Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata. J. Autom. Lang. Combinat. 24 (2019) 367–373. [Google Scholar]
  45. B. Steinberg, The Černý conjecture for one-cluster automata with prime length cycle. Theor. Comput. Sci. 412 (2011) 5487–5491. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  48. J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series parallel graphs. SIAM J. Comput. 11 (1982) 298–313. [CrossRef] [MathSciNet] [Google Scholar]
  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. [Google Scholar]
  50. M.V. Volkov, Synchronizing automata preserving a chain of partial orders. Theor. Comput. Sci. 410 (2009) 3513–3519. [Google Scholar]
  51. M.V. Volkov, Preface: Special issue on the Černý conjecture. J. Autom. Lang. Comb. 24 (2019) 119–121. [Google Scholar]
  52. V. Vorel, Complexity of a problem concerning reset words for Eulerian binary automata. Inf. Comput. 253 (2017) 497–509. [Google Scholar]
  53. V. Vorel and A. Roman, Parameterized complexity of synchronization and road coloring. Discr. Math. Theor. Comput. Sci. 17 (2015) 283–306. [Google Scholar]
  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. [Google Scholar]
  55. C. Yap, Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26 (1983) 287–300. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.