{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T08:27:24Z","timestamp":1712305644612},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,17]],"date-time":"2013-11-17T00:00:00Z","timestamp":1384646400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s10878-013-9682-0","type":"journal-article","created":{"date-parts":[[2013,11,16]],"date-time":"2013-11-16T04:07:31Z","timestamp":1384574851000},"page":"88-124","source":"Crossref","is-referenced-by-count":16,"title":["Computing the shortest reset words of synchronizing automata"],"prefix":"10.1007","volume":"29","author":[{"given":"Andrzej","family":"Kisielewicz","sequence":"first","affiliation":[]},{"given":"Jakub","family":"Kowalski","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,11,17]]},"reference":[{"key":"9682_CR1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-45007-6_8","volume-title":"Developments in language theory, LNCS","author":"D Ananichev","year":"2003","unstructured":"Ananichev D, Volkov M (2003) Synchronizing monotonic automata. In: Esik Z, Fulop Z (eds) Developments in language theory, LNCS, vol 2710. Springer, New York, pp 111\u2013121"},{"key":"9682_CR2","first-page":"55","volume-title":"Mathematical foundations of computer science, LNCS","author":"D Ananichev","year":"2010","unstructured":"Ananichev D, Gusev V, Volkov M (2010) Slowly synchronizing automata and digraphs. In: Hlineny P, Kucera A (eds) Mathematical foundations of computer science, LNCS, vol 6281. Springer, Berlin, pp 55\u201365"},{"key":"9682_CR3","first-page":"9","volume":"402","author":"D Ananichev","year":"2012","unstructured":"Ananichev D, Gusev V, Volkov M (2012) Primitive digraphs with large exponents and slowly synchronizing automata. Zapiski Nauchnyh Seminarov POMI [Kombinatorika i Teorija Grafov IV] 402:9\u201339 in Russian","journal-title":"Zapiski Nauchnyh Seminarov POMI [Kombinatorika i Teorija Grafov IV]"},{"key":"9682_CR4","first-page":"1","volume":"6","author":"M Batsyn","year":"2013","unstructured":"Batsyn M, Goldengorin B, Maslov E, Pardalos PM (2013) Improvements to MCS algorithm for the maximum clique proble. J Comb Optim 6:1\u201320","journal-title":"J Comb Optim"},{"issue":"5","key":"9682_CR5","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1073\/pnas.0535624100","volume":"100","author":"Y Benenson","year":"2003","unstructured":"Benenson Y, Adar R, Paz-Elizur T, Livneh Z, Shapiro E (2003) DNA molecule provides a computing machine with both data and fuel. Proc Natl Acad Sci 100(5):2191\u20132196","journal-title":"Proc Natl Acad Sci"},{"key":"9682_CR6","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-13182-0_4","volume-title":"Computer science\u2014theory and applications, LNCS","author":"M Berlinkov","year":"2010","unstructured":"Berlinkov M (2010) Approximating the minimum length of synchronizing words is hard. In: Ablayev F, Mayr FW (eds) Computer science\u2014theory and applications, LNCS, vol 6072. Springer, Berlin, pp 37\u201347"},{"key":"9682_CR7","unstructured":"Berlinkov M (2013) On the probability to be synchronizable. http:\/\/arxiv.org\/abs\/1304.5774"},{"key":"9682_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/b137241","volume-title":"Model-based testing of reactive systems: advanced lectures (lecture notes in computer science)","author":"M Broy","year":"2005","unstructured":"Broy M, Jonsson B, Katoen JP, Leucker M, Pretschner A (2005) Model-based testing of reactive systems: advanced lectures (lecture notes in computer science). Springer, New York"},{"issue":"3","key":"9682_CR9","first-page":"208","volume":"14","author":"J \u010cern\u00fd","year":"1964","unstructured":"\u010cern\u00fd J (1964) Pozn\u00e1mka k homog\u00e9nnym eksperimentom s kone\u010dn\u00fdmi automatami. Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied 14(3):208\u2013216 in Slovak","journal-title":"Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied"},{"key":"9682_CR10","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-3-642-18098-9_9","volume-title":"Implementation and application of automata, LNCS","author":"K Chmiel","year":"2011","unstructured":"Chmiel K, Roman A (2011) COMPAS\u2014a computing package for synchronization. In: Domaratzki M, Salomaa K (eds) Implementation and application of automata, LNCS, vol 6482. Springer, Berlin, pp 79\u201386"},{"key":"9682_CR11","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02279819","volume":"28","author":"L Devroye","year":"1982","unstructured":"Devroye L (1982) A note on the average depth of tries. Computing 28:367\u2013371","journal-title":"Computing"},{"key":"9682_CR12","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein D (1990) Reset sequences for monotonic automata. SIAM J Comput 19:500\u2013510","journal-title":"SIAM J Comput"},{"key":"9682_CR13","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/978-3-642-18098-9_17","volume-title":"Implementation and application of automata, LNCS","author":"M Gerbush","year":"2011","unstructured":"Gerbush M, Heeringa B (2011) Approximating minimum reset sequence. In: Laemmel AE, Rudner B (eds) Implementation and application of automata, LNCS, vol 6482. Springer, Berlin, pp 154\u2013162"},{"key":"9682_CR14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF02573120","volume":"37","author":"P Higgins","year":"1988","unstructured":"Higgins P (1988) The range order of a product of i-transformations from a finite full transformation semigroup. Semigroup Forum 37:31\u201336","journal-title":"Semigroup Forum"},{"issue":"301","key":"9682_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Am Stat Assoc 58(301):13\u201330","journal-title":"J Am Stat Assoc"},{"issue":"9\u201310","key":"9682_CR16","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1016\/j.ic.2008.03.005","volume":"206","author":"H J\u00fcrgensen","year":"2008","unstructured":"J\u00fcrgensen H (2008) Synchronization. Inf Comput 206(9\u201310):1033\u20131044","journal-title":"Inf Comput"},{"issue":"2","key":"9682_CR17","first-page":"270","volume":"8","author":"J Kari","year":"2002","unstructured":"Kari J (2002) Synchronization and stability of finite automata. J Univers Comput Sci 8(2):270\u2013277","journal-title":"J Univers Comput Sci"},{"key":"9682_CR18","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/978-3-642-39274-0_30","volume-title":"Implementation and application of automata, LNCS","author":"A Kisielewicz","year":"2013","unstructured":"Kisielewicz A, Szyku\u0142a M (2013) Generating small automata and the \u010cern\u00fd conjecture. In: Konstantinidis S (ed) Implementation and application of automata, LNCS, vol 7982. Springer, Berlin, pp 340\u2013348"},{"key":"9682_CR19","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-642-38768-5_18","volume-title":"Computing and combinatorics, LNCS","author":"A Kisielewicz","year":"2013","unstructured":"Kisielewicz A, Kowalski J, Szykula M (2013) A fast algorithm finding the shortest reset words. In: Du DZ, Zhang G (eds) Computing and combinatorics, LNCS, vol 7936. Springer, Berlin, pp 182\u2013196"},{"key":"9682_CR20","unstructured":"Kowalski J, Szyku\u0142a M (2013) A new heuristic synchronizing algorithm. http:\/\/arxiv.org\/abs\/1308.1978"},{"issue":"14","key":"9682_CR21","doi-asserted-by":"crossref","first-page":"11746","DOI":"10.1016\/j.eswa.2012.04.079","volume":"39","author":"R Kud\u0142acik","year":"2012","unstructured":"Kud\u0142acik R, Roman A, Wagner H (2012) Effective synchronizing algorithms. Expert Syst App 39(14):11746\u201311757","journal-title":"Expert Syst App"},{"key":"9682_CR22","first-page":"517","volume":"19","author":"P Martyugin","year":"2009","unstructured":"Martyugin P (2009) Complexity of problems concerning reset words for some partial cases of automata. Acta Cybern 19:517\u2013536","journal-title":"Acta Cybern"},{"key":"9682_CR23","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/978-3-642-22256-6_22","volume-title":"Implementation and application of automata, LNCS","author":"p Martyugin","year":"2011","unstructured":"Martyugin p (2011) Complexity of problems concerning reset words for cyclic and Eulerian automata. In: Bouchou-Markhoff B (ed) Implementation and application of automata, LNCS, vol 6807. Springer, Berlin, pp 238\u2013249"},{"key":"9682_CR24","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D Morrison","year":"1968","unstructured":"Morrison D (1968) PATRICIA\u2014practical algorithm to retrieve information coded in alphanumeric. J ACM 15:514\u2013534","journal-title":"J ACM"},{"key":"9682_CR25","first-page":"568","volume-title":"Mathematical foundations of computer science, LNCS","author":"J Olschewski","year":"2010","unstructured":"Olschewski J, Ummels M (2010) The complexity of finding reset words in finite automata. In: Hinneny P, Kucera A (eds) Mathematical foundations of computer science, LNCS, vol 6281. Springer, Berlin, pp 568\u2013579"},{"issue":"1","key":"9682_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1132973.1132974","volume":"32","author":"F Panneton","year":"2006","unstructured":"Panneton F, L\u2019Ecuyer P, Matsumoto M (2006) Improved long-period generators based on linear recurrences modulo 2. ACM Trans Math Softw 32(1):1\u201316","journal-title":"ACM Trans Math Softw"},{"key":"9682_CR27","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/978-3-642-29347-4_49","volume-title":"Artificial intelligence and soft computing, LNCS","author":"IT Podolak","year":"2012","unstructured":"Podolak IT, Roman A, J\u0119drzejczyk D (2012) Application of hierarchical classifier to minimal synchronizing word problem. In: Rutkowsk L, Zurada JM (eds) Artificial intelligence and soft computing, LNCS, vol 7267. Springer, Berlin, pp 421\u2013429"},{"key":"9682_CR28","unstructured":"Rho JK, Yu FS (1993) Minimum length synchronizing sequences of finite state machine. In: Proceedings of the 30th ACM\/IEEE Design Automation Conference, DAC 93, pp 463\u2013466"},{"key":"9682_CR29","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1007\/978-3-642-00982-2_58","volume-title":"Language and automata theory and applications, LNCS","author":"A Roman","year":"2009","unstructured":"Roman A (2009a) Genetic algorithm for synchronization. In: Dediu AH, Ionescu AM, Marin-Vide C (eds) Language and automata theory and applications, LNCS, vol 5457. Springer, Berlin, pp 684\u2013695"},{"key":"9682_CR30","first-page":"125","volume-title":"Applied mathematics and computation, ICCMSE-2005","author":"A Roman","year":"2009","unstructured":"Roman A (2009b) Synchronizing finite automata with short reset words. In: Simos TM (ed) Applied mathematics and computation, ICCMSE-2005, vol 209. Springer, Berlin, pp 125\u2013136"},{"key":"9682_CR31","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-based testing of reactive systems, LNCS","author":"S Sandberg","year":"2005","unstructured":"Sandberg S (2005) Homing and synchronizing sequences. In: Broy M, Jonsson B, Leucker M (eds) Model-based testing of reactive systems, LNCS, vol 3472. Springer, Berlin, pp 5\u201333"},{"key":"9682_CR32","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-22256-6_27","volume-title":"Implementation and application of automata, LNCS","author":"E Skvortsov","year":"2011","unstructured":"Skvortsov E, Tipikin E (2011) Experimental study of the shortest reset word of random automata. In: Bouchou-Markhoff B (ed) Implementation and application of automata, LNCS, vol 6807. Springer, Berlin, pp 290\u2013298"},{"key":"9682_CR33","volume-title":"Introduction to the numerical solution of Markov Chains","author":"WJ Stewart","year":"1994","unstructured":"Stewart WJ (1994) Introduction to the numerical solution of Markov Chains, 1st edn. Princeton University Press, Princeton","edition":"1"},{"key":"9682_CR34","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-1-4757-4828-4_4","volume-title":"Computational probability","author":"WJ Stewart","year":"2000","unstructured":"Stewart WJ (2000) Numerical methods for computing stationary distributions of finite irreducible markov chains. Computational probability, vol 24. Springer, New York, pp 81\u2013111"},{"issue":"1\u20136","key":"9682_CR35","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/BF01759045","volume":"6","author":"W Szpankowski","year":"1991","unstructured":"Szpankowski W (1991) On the height of digital trees and related problems. Algorithmica 6(1\u20136):256\u2013277","journal-title":"Algorithmica"},{"issue":"2","key":"9682_CR36","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146\u2013160","journal-title":"SIAM J Comput"},{"key":"9682_CR37","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1007\/3-540-44977-9_22","volume-title":"Implementation and application of automata, LNCS","author":"AN Trahtman","year":"2003","unstructured":"Trahtman AN (2003) A package TESTAS for checking some kinds of testability. In: Domaratzki M, Salomaa K (eds) Implementation and application of automata, LNCS, vol 2608. Springer, New York, pp 228\u2013232"},{"key":"9682_CR38","first-page":"789","volume-title":"Mathematical foundations of computer science, LNCS","author":"AN Trahtman","year":"2006","unstructured":"Trahtman AN (2006) An efficient algorithm finds noticeable trends and examples concerning the C\u0306ern\u00fd conjecture. In: Kralovic R, Urzyczyn P (eds) Mathematical foundations of computer science, LNCS, vol 4162. Springer, Berlin, pp 789\u2013800"},{"key":"9682_CR39","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume-title":"Language and automata theory and applications, LNCS","author":"M Volkov","year":"2008","unstructured":"Volkov M (2008) Synchronizing automata and the C\u0306ern\u00fd conjecture. In: Martin-Vide C, Otta F, Fernau H (eds) Language and automata theory and applications, LNCS, vol 5196. Springer, Berlin, pp 11\u201327"},{"issue":"2","key":"9682_CR40","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1009850721462","volume":"4","author":"G Xue","year":"2000","unstructured":"Xue G, Sun S, Du DHC, Shi L (2000) An efficient algorithm for delay buffer minimization. J Comb Optim 4(2):217\u2013233","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9682-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9682-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9682-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T22:53:44Z","timestamp":1553640824000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9682-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,17]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9682"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9682-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,17]]}}}