{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T03:25:30Z","timestamp":1775013930494,"version":"3.50.1"},"reference-count":15,"publisher":"Pleiades Publishing Ltd","issue":"6","license":[{"start":{"date-parts":[[2014,11,1]],"date-time":"2014-11-01T00:00:00Z","timestamp":1414800000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,11,1]],"date-time":"2014-11-01T00:00:00Z","timestamp":1414800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Program Comput Soft"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1134\/s0361768814060140","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T11:39:32Z","timestamp":1415965172000},"page":"333-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the complexity of existence of homing sequences for nondeterministic finite state machines"],"prefix":"10.1134","volume":"40","author":[{"given":"N. G.","family":"Kushik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. V.","family":"Kulyamin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Evtushenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"137","published-online":{"date-parts":[[2014,11,12]]},"reference":[{"key":"6234_CR1","volume-title":"Introduction to Theory of Finite-State Machines","author":"A Gill","year":"1962","unstructured":"Gill, A., Introduction to Theory of Finite-State Machines, McGraw-Hill, 1962."},{"key":"6234_CR2","volume-title":"Cand. Sci. (Phys.-Mat.) Dissertation","author":"PV Martyugin","year":"2008","unstructured":"Martyugin, P.V., Length estimates and computational complexity of synchronization of finite state machines, Cand. Sci. (Phys.-Mat.) Dissertation, Yekaterinburg, 2008."},{"issue":"1","key":"6234_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2004.09.006","volume":"330","author":"DS Ananichev","year":"2005","unstructured":"Ananichev, D.S. and Volkov, M.V., Synchronizing generalized monotonic automata, Theor. Comput. Sci., 2005, vol. 330, no. 1, pp. 3\u201313.","journal-title":"Theor. Comput. Sci."},{"key":"6234_CR4","first-page":"16","volume-title":"Kibern.","author":"AA Klyachko","year":"1987","unstructured":"Klyachko, A.A., Rystsov, I.K., and Spivak, M.A., On an extremum combinatorial problem related to estimationof length of a return word in automaton, Kibern., 1987, no. 2, pp. 16\u201321."},{"key":"6234_CR5","volume-title":"Switching and Finite Automata Theory","author":"Z Kohavi","year":"1978","unstructured":"Kohavi, Z., Switching and Finite Automata Theory, New York: McGraw-Hill, 1978."},{"key":"6234_CR6","volume-title":"Lektsii po teorii konechnykh avtomatov","author":"GP Agibalov","year":"1984","unstructured":"Agibalov, G.P. and Oranov, A.M., Lektsii po teorii konechnykh avtomatov (Lectures on Finite Automaton Theory), Tomsk: TGU, 1984."},{"issue":"3","key":"6234_CR7","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, Information Processing Lett., 1983, vol. 16, no. 3, pp. 147\u2013151.","journal-title":"Information Processing Lett."},{"key":"6234_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/11498490_2","volume":"3472","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S., Homing and synchronization sequences, Lecture Notes Comput. Sci., 2005, vol. 3472, pp. 5\u201333.","journal-title":"Lecture Notes Comput. Sci."},{"key":"6234_CR9","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-22256-6_20","volume":"6807","author":"N Kushik","year":"2011","unstructured":"Kushik, N., El-Fakih, K., and Yevtushenko, N., Preset and adaptive homing experiments for nondeterministic finite state machines, Lecture Notes Comput. Sci., 2011, vol. 6807, pp. 215\u2013224.","journal-title":"Lecture Notes Comput. Sci."},{"key":"6234_CR10","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-642-39274-0_20","volume":"7982","author":"N Kushik","year":"2013","unstructured":"Kushik, N. and Yevtushenko, N., On the length of homing sequences for nondeterministic finite state machines, Lecture Notes Comput. Sci., 2013, vol. 7982, pp. 220\u2013231.","journal-title":"Lecture Notes Comput. Sci."},{"key":"6234_CR11","volume-title":"Cand. Sci. (Phys.-Mat.) Dissertation","author":"NG Kushik","year":"2013","unstructured":"Kushik, N.G., Methods for synthesizing homing and distinguishing experiments with nondeterministic finite state machines, Cand. Sci. (Phys.-Mat.) Dissertation, Tomsk, 2013."},{"key":"6234_CR12","volume-title":"Synthesis of FSMs: Functional Optimization","author":"T Kim","year":"1997","unstructured":"Kim T., Villa, T., Brayton, R., and Sangiovanni-Vincentelli, A., Synthesis of FSMs: Functional Optimization, Kluwer, 1997."},{"key":"6234_CR13","volume-title":"Nedeterminirovannye avtomaty: analiz i sintez","author":"NV Yevtushenko","year":"2006","unstructured":"Yevtushenko, N.V., Petrenko, A.F., and Vetrova, M.V., Nedeterminirovannye avtomaty: analiz i sintez (Nondeterministic Automata: Analysis and Synthesis) Tomsk: TGU, 2006."},{"key":"6234_CR14","volume-title":"Abstract Automata","author":"P Starke","year":"1972","unstructured":"Starke, P., Abstract Automata, Elsevier, 1972."},{"key":"6234_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 1970, vol. 4, pp. 177\u2013192.","journal-title":"J. Comput. System Sci."}],"container-title":["Programming and Computer Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0361768814060140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S0361768814060140","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1134\/S0361768814060140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0361768814060140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:14:02Z","timestamp":1775009642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S0361768814060140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["6234"],"URL":"https:\/\/doi.org\/10.1134\/s0361768814060140","relation":{},"ISSN":["0361-7688","1608-3261"],"issn-type":[{"value":"0361-7688","type":"print"},{"value":"1608-3261","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11]]},"assertion":[{"value":"21 June 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2014","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}