{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:26:41Z","timestamp":1725492401013},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540403913"},{"type":"electronic","value":"9783540449775"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44977-9_19","type":"book-chapter","created":{"date-parts":[[2007,10,16]],"date-time":"2007-10-16T10:20:28Z","timestamp":1192530028000},"page":"203-212","source":"Crossref","is-referenced-by-count":1,"title":["A Polynomial Time Algorithm for Left [Right] Local Testability"],"prefix":"10.1007","author":[{"given":"A.N.","family":"Trahtman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"19_CR1","unstructured":"A. Aho, J. Hopcroft, J. Ulman, The Design and Analisys of Computer Algorithms, Addison-Wesley, 1974."},{"key":"19_CR2","unstructured":"D. Belostotski, D. Kravtsov, A. Shemshurenko, M. Sobol, A.N. Trahtman, Sh. Yakov, A package for checking some kinds of testability. 6-th Int. Conf. on Impl. and Appl. of Automata, CIAA2001, Pretoria, 2001."},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1142\/S0218196791000092","volume":"1","author":"J.-C. Birget","year":"1991","unstructured":"J.-C. Birget, Strict local testability of the finite control of two-way automata and of regular picture description languages, J. of Alg. Comp. 1, 2(1991), 161\u2013175.","journal-title":"J. of Alg. Comp."},{"issue":"3","key":"19_CR4","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF02218673","volume":"9","author":"A.P. Biryukov","year":"1970","unstructured":"A.P. Biryukov, Varieties of idempotent semigroups, Algebra i logika, 9, 3(1970), 255\u2013273.","journal-title":"Algebra i logika"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0012-365X(73)80005-6","volume":"4","author":"J.A. Brzozowski","year":"1973","unstructured":"J.A. Brzozowski, I. Simon, Characterizations of locally testable events, Discrete Math. 4, (1973), 243\u2013271.","journal-title":"Discrete Math."},{"issue":"3","key":"19_CR6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF03325439","volume":"58","author":"J.C. Costa","year":"1999","unstructured":"J.C. Costa, Free profinite R-trivial, locally idempotent and locally commutative semigroups. Sem. Forum, 58, 3(1999), 423\u2013444.","journal-title":"Sem. Forum"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0304-3975(99)00108-5","volume":"246","author":"P. Garcia","year":"2000","unstructured":"P. Garcia, J. Ruiz, Right and left locally testable languages, Theoret. Comput. Sci., 246(2000), 253\u2013264.","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"19_CR8","first-page":"739","volume":"49","author":"T. Head","year":"1987","unstructured":"T. Head, Formal languages theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bull. Math. Biol.\n                           49(1987), 4, 739\u2013757.","journal-title":"Bull. Math. Biol."},{"issue":"3","key":"19_CR9","first-page":"233","volume":"19","author":"R. K\u00f6nig","year":"1985","unstructured":"R. K\u00f6nig, Reduction algorithm for some classes of aperiodic monoids, R.A.I.R.O. Theor.Inform., 19, 3(1985), 233\u2013260.","journal-title":"R.A.I.R.O. Theor.Inform."},{"issue":"10","key":"19_CR10","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/12.93741","volume":"40","author":"S. Kim","year":"1991","unstructured":"S. Kim, R. McNaughton, R. McCloskey, A polynomial time algorithm for the local testability problem of deterministic finite automata, IEEE Trans. Comput.\n                           40(1991) N10, 1087\u20131093.","journal-title":"IEEE Trans. Comput."},{"key":"19_CR11","volume-title":"Semigroups and Combinatorial Applications","author":"L. G","year":"1979","unstructured":"Lallement, G., Semigroups and Combinatorial Applications, Wiley, N.Y., 1979."},{"key":"19_CR12","volume-title":"Counter-free automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton, S, Papert, Counter-free automata M.I.T. Press. Mass., 1971."},{"issue":"1","key":"19_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1142\/S0218196799000035","volume":"9","author":"A.N. Trahtman","year":"1998","unstructured":"A.N. Trahtman, A polynomial time algorithm for local testability and its level. Int. J. of Algebra and Comp., vol. 9, 1(1998), 31\u201339.","journal-title":"Int. J. of Algebra and Comp."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"5405","DOI":"10.1080\/00927879908826762","volume":"27","author":"A.N. Trahtman","year":"1999","unstructured":"A.N. Trahtman, Identities of locally testable semigroups. Comm. in Algebra, v. 27, 11(1999), 5405\u20135412.","journal-title":"Comm. in Algebra"},{"key":"19_CR15","unstructured":"A.N. Trahtman, Piecewise and local threshold testability of DFA. Lect. Notes in Comp. Sci., 2138(2001), 347\u2013358."},{"key":"19_CR16","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 language, J. Comp. System Sci.\n                           6(1972), 151\u2013167","journal-title":"J. Comp. System Sci."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44977-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T02:50:31Z","timestamp":1550976631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44977-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403913","9783540449775"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44977-9_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}