{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:33Z","timestamp":1740108333182,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T00:00:00Z","timestamp":1658448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T00:00:00Z","timestamp":1658448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00236-022-00433-1","type":"journal-article","created":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T12:04:00Z","timestamp":1658491440000},"page":"479-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Careful synchronization of partial deterministic finite automata"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0042-4797","authenticated-orcid":false,"given":"Hanan","family":"Shabana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9327-243X","authenticated-orcid":false,"given":"M. V.","family":"Volkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,22]]},"reference":[{"key":"433_CR1","doi-asserted-by":"crossref","unstructured":"Ananichev, D.S., Volkov, M.V.: Some results on \u010cern\u00fd type problems for transformation semigroups. In: Ara\u00fajo, I. M., Branco, M.J.J., Fernandes, V.H., Gomes, G.M.S. (eds.) Semigroups and Languages, pp. 23\u201342. World Scientific (2004)","DOI":"10.1142\/9789812702616_0002"},{"issue":"3","key":"433_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10958-013-1392-8","volume":"192","author":"DS Ananichev","year":"2013","unstructured":"Ananichev, D.S., Volkov, M.V., Gusev, V.V.: Primitive digraphs with large exponents and slowly synchronizing automata. J. Math. Sci. 192(3), 263\u2013278 (2013)","journal-title":"J. Math. Sci."},{"key":"433_CR3","doi-asserted-by":"crossref","unstructured":"Berlinkov, M.V.: On two algorithmic problems about synchronizing automata. In: Shur, A.M., Volkov, M.V. (eds.) Developments in Language Theory. 18th International Conference, DLT 2014. LNCS, 8633, 61\u201367. Springer (2014)","DOI":"10.1007\/978-3-319-09698-8_6"},{"key":"433_CR4","doi-asserted-by":"crossref","unstructured":"Berlinkov, M.V.: On the probability of being synchronizable. In: Govindarajan, S., Maheshwari, A. (eds.) Algorithms and Discrete Applied Mathematics. 2nd International Conference, CALDAM 2016. LNCS, vol. 9602, pp. 73\u201384. Springer (2016)","DOI":"10.1007\/978-3-319-29221-2_7"},{"key":"433_CR5","doi-asserted-by":"crossref","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press (2009)","DOI":"10.1017\/CBO9781139195768"},{"key":"433_CR6","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook on Satisfiability. IOS Press (2009)"},{"key":"433_CR7","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/j.ic.2015.04.001","volume":"242","author":"P Bonizzoni","year":"2015","unstructured":"Bonizzoni, P., Jonoska, N.: Existence of constants in regular splicing languages. Inf. Comput. 242, 340\u2013353 (2015)","journal-title":"Inf. Comput."},{"key":"#cr-split#-433_CR8.1","unstructured":"Cerny, J.: Pozn\u00e1mka k homog\u00e9nnym eksperimentom s kone\u010dn\u00fdmi automatami. Matematicko-fyzikalny \u010casopis Slovenskej Akad\u00e9mie Vied 14(3), 208-216 (1964) (in Slovak)"},{"key":"#cr-split#-433_CR8.2","unstructured":"Engl. translation: A note on homogeneous experiments with finite automata. J. Autom. Lang. Comb. 24(2-4), 121-130 (2019)"},{"issue":"1","key":"433_CR9","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1142\/S0129054119400021","volume":"30","author":"M de Bondt","year":"2019","unstructured":"de Bondt, M., Don, H., Zantema, H.: Lower bounds for synchronizing word lengths in partial automata. Int. J. Found. Comput. Sci. 30(1), 29\u201360 (2019)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"433_CR10","first-page":"307","volume":"23","author":"H Don","year":"2018","unstructured":"Don, H., Zantema, H.: Synchronizing non-deterministic finite automata. J. Autom. Lang. Comb. 23(4), 307\u2013328 (2018)","journal-title":"J. Autom. Lang. Comb."},{"key":"433_CR11","doi-asserted-by":"crossref","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.), Theory and Applications of Satisfiability Testing. 6th International Conference, SAT 2003. LNCS, 2919, 502\u2013518. Springer (2004)","DOI":"10.1007\/978-3-540-24605-3_37"},{"key":"433_CR12","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: The MiniSat Page. Available at http:\/\/minisat.se"},{"key":"433_CR13","unstructured":"Gent, I.P., Nightingale, P.: A new encoding of AllDifferent into SAt. In: Frisch, A.M., Miguel, I. (eds.), Modelling and Reformulating Constraint Satisfaction Problems: Towards Systematisation and Automation. 3rd International Workshop, 95\u2013110 (2004) Available at http:\/\/www-users.cs.york.ac.uk\/~frisch\/ModRef\/04\/proceedings.pdf"},{"key":"433_CR14","doi-asserted-by":"crossref","unstructured":"Gomes, C..P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, vol. I, pp. 89\u2013134. Elsevier (2008)","DOI":"10.1016\/S1574-6526(07)03002-7"},{"key":"433_CR15","unstructured":"G\u00fcni\u00e7en, C., Erdem, E., Yenig\u00fcn, H.: Generating shortest synchronizing sequences using Answer Set Programming. In: Fink, M., Lierler, Yu. (eds.) Answer Set Programming and Other Computing Paradigms, 6th International Workshop, ASPOCP 2013, 117\u2013127. https:\/\/arxiv.org\/abs\/1312.6146 (2013)"},{"issue":"4","key":"433_CR16","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1214\/aoms\/1177705677","volume":"31","author":"B Harris","year":"1960","unstructured":"Harris, B.: Probability distributions related to random mappings. Ann. Math. Stat. 31(4), 1045\u20131062 (1960)","journal-title":"Ann. Math. Stat."},{"key":"433_CR17","doi-asserted-by":"crossref","unstructured":"Ito, M.: Algebraic Theory of Automata and Languages. World Scientific (2004)","DOI":"10.1142\/4791"},{"key":"433_CR18","doi-asserted-by":"crossref","unstructured":"Kari, J., Volkov, M.V.: \u010cern\u00fd\u2019s conjecture and the road colouring problem. Chapter 15 in: J.-\u00c9. Pin (ed.), Handbook of Automata Theory, I, 525\u2013565. EMS Press (2021)","DOI":"10.4171\/Automata-1\/15"},{"issue":"1","key":"433_CR19","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10878-013-9682-0","volume":"29","author":"A Kisielewicz","year":"2015","unstructured":"Kisielewicz, A., Kowalski, J., Szyku\u0142a, M.: Computing the shortest reset words of synchronizing automata. J. Comb. Optim. 29(1), 88\u2013124 (2015)","journal-title":"J. Comb. Optim."},{"key":"433_CR20","unstructured":"Martyugin, P.V.: Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata. Diskretn. Anal. Issled. Oper. 15(4), 44\u201356 (2008) (in Russian)"},{"issue":"1","key":"433_CR21","doi-asserted-by":"publisher","first-page":"46","DOI":"10.3103\/S1066369X10010056","volume":"54","author":"PV Martyugin","year":"2010","unstructured":"Martyugin, P.V.: A lower bound for the length of the shortest carefully synchronizing words. Russian Math. (Iz. VUZ) 54(1), 46\u201354 (2010)","journal-title":"Russian Math. (Iz. VUZ)"},{"key":"433_CR22","doi-asserted-by":"crossref","unstructured":"Martyugin, P.V.: Synchronization of automata with one undefined or ambiguous transition. In: Moreira, N., Reis, R. (eds.), Implementation and Application of Automata, 17th International Conference, CIAA 2012. LNCS, 7381, 278\u2013288. Springer (2012)","DOI":"10.1007\/978-3-642-31606-7_24"},{"key":"433_CR23","doi-asserted-by":"crossref","unstructured":"Martyugin, P.V.: Careful synchronization of partial automata with restricted alphabets. In: Bulatov, A.A., Shur, A.M. (eds.) Computer Science\u2014Theory and Applications, 8th International Computer Science Symposium in Russia, CSR 2013. LNCS, 7913, 76\u201387. Springer (2013)","DOI":"10.1007\/978-3-642-38536-0_7"},{"issue":"2","key":"433_CR24","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00224-013-9516-6","volume":"54","author":"PV Martyugin","year":"2014","unstructured":"Martyugin, P.V.: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. Theory Comput. Syst. 54(2), 293\u2013304 (2014)","journal-title":"Theory Comput. Syst."},{"key":"433_CR25","doi-asserted-by":"crossref","unstructured":"Natarajan, B.K.: An algorithmic approach to the automated design of parts orienters. In: Proceedings of 27th Annual Symposium Foundations Computer Science, 132\u2013142. IEEE Press (1986)","DOI":"10.1109\/SFCS.1986.5"},{"issue":"6","key":"433_CR26","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1177\/027836498900800607","volume":"8","author":"BK Natarajan","year":"1989","unstructured":"Natarajan, B.K.: Some paradigms for the automated design of parts feeders. Int. J. Robotics Res. 8(6), 89\u2013109 (1989)","journal-title":"Int. J. Robotics Res."},{"key":"433_CR27","unstructured":"Nicaud, C.: Fast synchronization of random automata. In: Jansen, K., Mathieu, C., Rolim, J.D.P., Umans, C. (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX\/RANDOM 2016. LIPIcs, 60, 43:1\u201343:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"2\u20134","key":"433_CR28","first-page":"343","volume":"24","author":"C Nicaud","year":"2019","unstructured":"Nicaud, C.: The \u010cern\u00fd Conjecture holds with high probability. J. Autom. Lang. Comb. 24(2\u20134), 343\u2013365 (2019)","journal-title":"J. Autom. Lang. Comb."},{"key":"433_CR29","doi-asserted-by":"crossref","unstructured":"Ram\u00edrez\u00a0Alfons\u00edn, J.L.: The Diophantine Frobenius Problem. Oxford University Press (2005)","DOI":"10.1093\/acprof:oso\/9780198568209.001.0001"},{"issue":"1","key":"433_CR30","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/BF01069104","volume":"16","author":"IK Rystsov","year":"1980","unstructured":"Rystsov, I.K.: Asymptotic estimate of the length of a diagnostic word for a finite automaton. Cybernetics 16(1), 194\u2013198 (1980)","journal-title":"Cybernetics"},{"issue":"3","key":"433_CR31","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. Inf. Process. Lett. 16(3), 147\u2013151 (1983)","journal-title":"Inf. Process. Lett."},{"key":"433_CR32","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, 3472, 5\u201333. Springer (2005)"},{"issue":"2","key":"433_CR33","doi-asserted-by":"publisher","first-page":"99","DOI":"10.15826\/umj.2018.2.011","volume":"4","author":"H Shabana","year":"2018","unstructured":"Shabana, H.: $$D_2$$-synchronization in nondeterministic automata. Ural Math. J. 4(2), 99\u2013110 (2018)","journal-title":"Ural Math. J."},{"key":"433_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1088\/1742-6596\/1352\/1\/012047","volume":"1352","author":"H Shabana","year":"2019","unstructured":"Shabana, H.: Exact synchronization in partial deterministic automata. J. Phys. Conf. Ser. 1352, 1\u20138 (2019)","journal-title":"J. Phys. Conf. Ser."},{"key":"433_CR35","first-page":"1426","volume":"15","author":"H Shabana","year":"2018","unstructured":"Shabana, H., Volkov, M.V.: Using Sat solvers for synchronization issues in nondeterministic automata. Siberian Electron. Math. Rep. 15, 1426\u20131442 (2018)","journal-title":"Siberian Electron. Math. Rep."},{"key":"433_CR36","doi-asserted-by":"crossref","unstructured":"Shabana, H., Volkov, M.V.: Using Sat solvers for synchronization issues in partial deterministic automata. In: Bykadorov, I., Strsuevich, V.A., Tchemisova, T. (eds.), Mathematical Optimization Theory and Operation Research, 18th International Conference, MOTOR 2019. Communications in Computer and Information Science, Springer 1090, 103\u2013118 (2019)","DOI":"10.1007\/978-3-030-33394-2_9"},{"key":"433_CR37","doi-asserted-by":"crossref","unstructured":"Skvortsov, E., Tipikin, E.: Experimental study of the shortest reset word of random automata. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.), Implementation and Application of Automata, 16th International Conference, CIAA 2011. LNCS, Springer 6807, 290\u2013298 (2011)","DOI":"10.1007\/978-3-642-22256-6_27"},{"issue":"5","key":"433_CR38","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s10955-011-0342-4","volume":"145","author":"N Travers","year":"2011","unstructured":"Travers, N., Crutchfield, J.: Exact synchronization for finite-state sources. J. Stat. Phys. 145(5), 1181\u20131201 (2011)","journal-title":"J. Stat. Phys."},{"issue":"5","key":"433_CR39","doi-asserted-by":"publisher","first-page":"1202","DOI":"10.1007\/s10955-011-0349-x","volume":"145","author":"N Travers","year":"2011","unstructured":"Travers, N., Crutchfield, J.: Asymptotic synchronization for finite-state sources. J. Stat. Phys. 145(5), 1202\u20131223 (2011)","journal-title":"J. Stat. Phys."},{"key":"433_CR40","doi-asserted-by":"publisher","first-page":"3544","DOI":"10.3906\/elk-1809-1","volume":"27","author":"U. C T\u00fcrker","year":"2019","unstructured":"T\u00fcrker, U.. C.: Parallel brute-force algorithm for deriving reset sequences from deterministic incomplete finite automata. Turk. J. Electr. Eng. Comput. Sci. 27, 3544\u20133556 (2019)","journal-title":"Turk. J. Electr. Eng. Comput. Sci."},{"key":"433_CR41","unstructured":"Volkov, M.V.: Synchronizing automata and the \u010cern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.), Languages and Automata Theory and Applications, 2nd International Conference, LATA 2008. LNCS, Springer 5196, 11\u201327 (2008)"},{"key":"433_CR42","doi-asserted-by":"crossref","unstructured":"Zubkov, A.M.: Computation of distributions of the numbers of components and cyclic points for random mappings. Mat. Vopr. Kriptogr., 1(2), 5\u201318 (2010) (in Russian)","DOI":"10.4213\/mvk7"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00433-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00433-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00433-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:09:11Z","timestamp":1661591351000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00433-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,22]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["433"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00433-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,7,22]]},"assertion":[{"value":"13 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}