{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:02Z","timestamp":1759639082405,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319601335"},{"type":"electronic","value":"9783319601342"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60134-2_16","type":"book-chapter","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T12:53:09Z","timestamp":1495889589000},"page":"188-200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Synchronization Problems in Automata Without Non-trivial Cycles"],"prefix":"10.1007","author":[{"given":"Andrew","family":"Ryzhikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,28]]},"reference":[{"issue":"3","key":"16_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2004.03.068","volume":"327","author":"D Ananichev","year":"2004","unstructured":"Ananichev, D., Volkov, M.: Synchronizing monotonic automata. Theor. Comput. Sci. 327(3), 225\u2013239 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-319-09698-8_6","volume-title":"Developments in Language Theory","author":"MV Berlinkov","year":"2014","unstructured":"Berlinkov, M.V.: On two algorithmic problems about synchronizing automata. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 61\u201367. Springer, Cham (2014). doi:10.1007\/978-3-319-09698-8_6"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-41114-9_1","volume-title":"Descriptional Complexity of Formal Systems","author":"EA Bondar","year":"2016","unstructured":"Bondar, E.A., Volkov, M.V.: Completely reachable automata. In: C\u00e2mpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 1\u201317. Springer, Cham (2016). doi:10.1007\/978-3-319-41114-9_1"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0022-0000(80)90003-3","volume":"20","author":"J Brzozowski","year":"1980","unstructured":"Brzozowski, J., Fich, F.E.: Languages of R-trivial monoids. J. Comput. Syst. Sci. 20(1), 32\u201349 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR5","unstructured":"Cardoso, A.: The \u010cern\u00fd Conjecture and Other Synchronization Problems. Ph.D. thesis. University of Porto, Portugal (2014)"},{"key":"16_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500\u2013510 (1990)","journal-title":"SIAM J. Comput."},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-662-48057-1_19","volume-title":"Mathematical Foundations of Computer Science 2015","author":"P Gawrychowski","year":"2015","unstructured":"Gawrychowski, P., Straszak, D.: Strong inapproximability of the shortest reset word. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9234, pp. 243\u2013255. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48057-1_19"},{"key":"16_CR9","unstructured":"Gerencs\u00e9r, B., Gusev, V.V., Jungers, R.M.: Primitive sets of nonnegative matrices and synchronizing automata. CoRR abs\/1602.07556 (2016)"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-31606-7_20","volume-title":"Implementation and Application of Automata","author":"G Jir\u00e1skov\u00e1","year":"2012","unstructured":"Jir\u00e1skov\u00e1, G., Masopust, T.: On the state and computational complexity of\u00a0the\u00a0reverse of acyclic minimal dfas. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 229\u2013239. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-31606-7_20"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-642-13182-0_27","volume-title":"Computer Science \u2013 Theory and Applications","author":"PV Martyugin","year":"2010","unstructured":"Martyugin, P.V.: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 288\u2013302. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-13182-0_27"},{"issue":"2","key":"16_CR13","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphs. Colloquium Mathematicae 3(2), 161\u2013162 (1955)","journal-title":"Colloquium Mathematicae"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Natarajan, B.K.: An algorithmic approach to the automated design of parts orienters. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 132\u2013142 (1986)","DOI":"10.1109\/SFCS.1986.5"},{"key":"16_CR15","first-page":"535","volume":"17","author":"J\u00c9 Pin","year":"1983","unstructured":"Pin, J.\u00c9.: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17, 535\u2013548 (1983)","journal-title":"Ann. Discrete Math."},{"issue":"3","key":"16_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01125412","volume":"28","author":"IK Rystsov","year":"1992","unstructured":"Rystsov, I.K.: Rank of a finite automaton. Cybern. Syst. Anal. 28(3), 323\u2013328 (1992)","journal-title":"Cybern. Syst. Anal."},{"issue":"3","key":"16_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(83)90067-4","volume":"16","author":"IK Rystsov","year":"1983","unstructured":"Rystsov, I.K.: Polynomial complete problems in automata theory. Inform. Process. Lett. 16(3), 147\u2013151 (1983)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/S0304-3975(96)00136-3","volume":"172","author":"IK Rystsov","year":"1997","unstructured":"Rystsov, I.K.: Reset words for commutative and solvable automata. Theor. Comput. Sci. 172(1), 273\u2013279 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR19","unstructured":"Ryzhikov, A.: Approximating the maximum number of synchronizing states in automata. CoRR abs\/1608.00889 (2016)"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-Based Testing of Reactive Systems","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5\u201333. Springer, Heidelberg (2005). doi:10.1007\/11498490_2"},{"key":"16_CR21","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, 3rd edn. (2012)"},{"key":"16_CR22","unstructured":"Szyku\u0142a, M.: Improving the upper bound the length of the shortest reset words. CoRR abs\/1702.05455 (2017)"},{"issue":"2","key":"16_CR23","first-page":"3","volume":"9","author":"AN Trahtman","year":"2007","unstructured":"Trahtman, A.N.: The Cern\u00fd conjecture for aperiodic automata. Discrete Math. Theor. Comput. Sci. 9(2), 3\u201310 (2007)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"16_CR24","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"16_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume-title":"Language and Automata Theory and Applications","author":"MV Volkov","year":"2008","unstructured":"Volkov, M.V.: Synchronizing automata and the \u010cern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11\u201327. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-88282-4_4"},{"issue":"5","key":"16_CR26","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0129054116500167","volume":"27","author":"V Vorel","year":"2016","unstructured":"Vorel, V.: Subset synchronization and careful synchronization of binary finite automata. Int. J. Found. Comput. Sci. 27(5), 557\u2013578 (2016)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"16_CR27","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60134-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:32:15Z","timestamp":1710343935000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-60134-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319601335","9783319601342"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60134-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"28 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marne-la-Vall\u00e9e","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ciaa17.univ-mlv.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}