{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:32Z","timestamp":1725488612145},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_33","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:32:26Z","timestamp":1186727546000},"page":"347-358","source":"Crossref","is-referenced-by-count":9,"title":["Piecewise and Local Threshold Testability of DFA"],"prefix":"10.1007","author":[{"given":"A. N.","family":"Trahtman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"issue":"1\u20132","key":"33_CR1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0304-3975(98)80011-X","volume":"205","author":"M.-P. Beal","year":"1998","unstructured":"M.-P. Beal, J. Senellart, On the bound of the synchronization delay of local automata, Theoret. Comput. Sci. 205,1\u20132(1998), 297\u2013306.","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR2","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BFb0035752","volume-title":"Factors of words","author":"D. Beauquier","year":"1989","unstructured":"D. Beauquier, J.E. Pin, Factors of words, Lect. Notes in Comp. Sci. Springer, Berlin, 372(1989), 63\u201379."},{"issue":"84","key":"33_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(91)90258-4","volume":"1","author":"D. Beauquier","year":"1991","unstructured":"D. Beauquier, J.E. Pin, Languages and scanners, Theoret. Comp. Sci. 1,84(1991), 3\u201321.","journal-title":"Theoret. Comp. Sci."},{"issue":"2","key":"33_CR4","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."},{"key":"33_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."},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"P. Caron, LANGAGE: A Maple package for automaton characterization of regular languages, Springer, Lect. Notes in Comp. Sci. 1436(1998), 46\u201355.","DOI":"10.1007\/BFb0031380"},{"key":"33_CR7","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0304-3975(98)00332-6","volume":"242","author":"P. Caron","year":"2000","unstructured":"P. Caron, Families of locally testable languages, Theoret. Comput. Sci., 242(2000), 361\u2013376.","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR8","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/BF02481771","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. 49(1987), 4, 739\u2013757.","journal-title":"Bull. Math. Biol."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"F. Hinz, Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats, Springer, Lect. Notes in Comp. Sci. 349(1990), 132\u2013143.","DOI":"10.1007\/BFb0028979"},{"issue":"10","key":"33_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. 40(1991) N10, 1087\u20131093.","journal-title":"IEEE Trans. Comput."},{"key":"33_CR11","unstructured":"R. McNaughton, S, Papert, Counter-free automata M.I.T. Press. Mass., 1971."},{"key":"33_CR12","first-page":"1","volume":"1466","author":"J. Pin","year":"1995","unstructured":"J. Pin, Finite semigroups and recognizable languages. An introduction, Semigroups and formal languages, Math. and Ph. Sci. 1466(1995), 1\u201332.","journal-title":"Math. and Ph. Sci."},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"J. Ruiz, S. Espana, P. Garcia, Locally threshold testable languages in strict sense: Application to the inference problem. Springer, Lect. Notes in Comp. Sci 1433(1998), 150\u2013161.","DOI":"10.1007\/BFb0054072"},{"key":"33_CR14","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0019-9958(85)80058-9","volume":"66","author":"J. Stern","year":"1985","unstructured":"J. Stern, Complexity of some problems from the theory of automata. Inf. and Control, 66(1985), 163\u2013176.","journal-title":"Inf. and Control"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"I. Simon, Piecewise testable events, Springer, Lect. Notes in Comp. Sci., 33(1975), 214\u2013222.","DOI":"10.1007\/3-540-07407-4_23"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"R.E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comput. 1(1972), 146\u2013160. J. of Comp. System Sci. 25(1982), 360\u2013376.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"33_CR17","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. v. 9,1(1998), 31\u201339.","journal-title":"Int. J. of Algebra and Comp."},{"key":"33_CR18","doi-asserted-by":"crossref","unstructured":"A.N. Trahtman, A precise estimation of the order of local testability of a deterministic finite automaton, Springer, Lect. Notes in Comp. Sci. 1436(1998), 198\u2013212.","DOI":"10.1007\/BFb0031393"},{"key":"33_CR19","doi-asserted-by":"crossref","unstructured":"E. Vidal, F. Casacuberta, P. Garcia, Grammatical inference and automatic speech recognition. In speech recognition and coding Springer, 1995, 175\u2013191.","DOI":"10.1007\/978-3-642-57745-1_27"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:13:10Z","timestamp":1556734390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_33","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}