{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:57:16Z","timestamp":1725663436682},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540549673"},{"type":"electronic","value":"9783540466123"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54967-6_69","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T23:21:14Z","timestamp":1330212074000},"page":"186-211","source":"Crossref","is-referenced-by-count":2,"title":["Computing the order of a locally testable automaton"],"prefix":"10.1007","author":[{"given":"Sam","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,5,31]]},"reference":[{"key":"13_CR1","unstructured":"A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0012-365X(82)90281-3","volume":"4","author":"J. Brzozowski","year":"1973","unstructured":"J. Brzozowski and I. Simon, Characterizations of locally testable events, Discrete Mathematics, 4 (1973), pp. 243\u2013271.","journal-title":"Discrete Mathematics"},{"key":"13_CR3","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, 1979."},{"key":"13_CR4","unstructured":"M. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978."},{"key":"13_CR5","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979."},{"key":"13_CR6","unstructured":"E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1984."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"S. M. Kim, R. McNaughton, and R. McCloskey, A polynomial time algorithm for the local testability problem of deterministic finite automata (to appear in IEEE Trans. Computers, October, 1991).","DOI":"10.1109\/12.93741"},{"key":"13_CR8","unstructured":"S. M. Kim and R. McNaughton, Computing the order of a locally testable automaton, Tech. Report 91-24, Department of Computer Science, Rensselaer Polytechnic Institute"},{"key":"13_CR9","unstructured":"M. Minsky and S. Papert, Perceptions, M.I.T. Press, 1969."},{"key":"13_CR10","unstructured":"R. McNaughton and S. Papert, Counter-free Automata, M.I.T. Press, 1971."},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01761708","volume":"8","author":"R. McNaughton","year":"1974","unstructured":"R. McNaughton, Algebraic decision procedures for local testability, Mathematical Systems Theory, 8 (1974), pp. 60\u201376.","journal-title":"Mathematical Systems Theory"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"J. Stern, Complexity of some problems from the theory of automata, Information and Control, 66(185), pp. 163\u2013176.","DOI":"10.1016\/S0019-9958(85)80058-9"},{"key":"13_CR13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0022-0000(72)80020-5","volume":"6","author":"Y. Zalcstein","year":"1972","unstructured":"Y. Zalcstein, Locally testable languages, Journal of Computer and System Sciences, 6 (1972), pp. 151\u2013167.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54967-6_69.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:57:02Z","timestamp":1605646622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54967-6_69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540549673","9783540466123"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-54967-6_69","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}