{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:12:22Z","timestamp":1778249542123,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030882","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"597-606","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An efficient algorithm for local testability problem of finite state automata"],"prefix":"10.1007","author":[{"given":"Sam Myo","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"McNaughton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"69_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0012-365X(82)90281-3","volume":"4","author":"J Brzozowski","year":"1973","unstructured":"Brzozowski, J, Simon, I.: Characterizations of locally testable events, Discrete Mathematics, 4 (1973) 243\u2013271.","journal-title":"Discrete Mathematics"},{"key":"69_CR2","unstructured":"Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979."},{"key":"69_CR3","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/12.93741","volume":"40","author":"S. M. Kim","year":"1991","unstructured":"Kim, S. M., McNaughton, R., McCloskey, R.: A polynomial time algorithm for the local testability problem of deterministic finite automata, IEEE Trans. Computers, 40 (1991) 1087\u20131093.","journal-title":"IEEE Trans. Computers"},{"key":"69_CR4","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/S0097539791216987","volume":"23","author":"S. M. Kim","year":"1994","unstructured":"Kim, S. M., McNaughton, R.: Computing the Order of a Locally Testable Automaton, SIAM J. Computing 23 (1994) 1193\u20131215.","journal-title":"SIAM J. Computing"},{"key":"69_CR5","unstructured":"Kim, S. M., McNaughton, R.: An Efficient Algorithm for Local Testability Problem of Finite State Automata, Computer Science Department, Rensselaer Polytechnic Institute. Tech. Report 93-8."},{"key":"69_CR6","unstructured":"Minsky, M., Papert, S.: Perceptrons, M.I.T. Press, 1969."},{"key":"69_CR7","unstructured":"McNaughton, R., Papert, S.: Counter-free Automata, M.I.T. Press, 1971."},{"key":"69_CR8","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01761708","volume":"8","author":"R. McNaughton","year":"1974","unstructured":"McNaughton, R.: Algebraic decision procedures for local testability, Mathematical Systems Theory, 8 (1974) 60\u201376.","journal-title":"Mathematical Systems Theory"},{"key":"69_CR9","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. E. Tarjan","year":"1972","unstructured":"Tarjan, R. E.: Depth first search and linear graph algorithms, SIAM J. Computing 1 (1972) 146\u2013160.","journal-title":"SIAM J. Computing"},{"key":"69_CR10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0022-0000(72)80020-5","volume":"6","author":"Y. Zalcstein","year":"1972","unstructured":"Zalcstein, Y.: Locally testable languages, Journal of Computer and System Sciences, 6 (1972) 151\u2013167.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030882","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:24:02Z","timestamp":1778246642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0030882","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}