{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:46Z","timestamp":1725663706639},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_176","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:56Z","timestamp":1330262456000},"page":"619-630","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Automaticity: Properties of a measure of descriptional complexity"],"prefix":"10.1007","author":[{"given":"Jeffrey","family":"Shallit","sequence":"first","affiliation":[]},{"given":"Yuri","family":"Breitbart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"50_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0019-9958(85)80026-7","volume":"67","author":"J. L. Balc\u00e1zar","year":"1985","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Uniform characterizations of non-uniform complexity measures. Inform. and Control\n67 (1985), 53\u201389.","journal-title":"Inform. and Control"},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I, Vol. 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"50_CR3","first-page":"16","volume":"196","author":"Y. Breitbart","year":"1971","unstructured":"Y. Breitbart. On automaton and \u201czone\u201d complexity of the predicate \u201cto be a kth power of an integer\u201d. Dokl. Akad. Nauk SSSR\n196 (1971), 16\u201319. In Russian. English translation in Soviet Math. Dokl.\n12 (1971), 10\u201314.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"50_CR4","volume-title":"PhD thesis","author":"Y. Breitbart","year":"1973","unstructured":"Y. Breitbart. Complexity of the calculation of predicates by finite automata. PhD thesis, Technion, Haifa, Israel, June 1973."},{"key":"50_CR5","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/S0022-0000(76)80005-0","volume":"12","author":"Y. Breitbart","year":"1976","unstructured":"Y. Breitbart. Some bounds on the complexity of predicate recognition by finite automata. J. Comput. System Sci.\n12 (1976), 336\u2013349.","journal-title":"J. Comput. System Sci."},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"A. Condon, L. Hellerstein, S. Pottle, and A. Wigderson. On the power of finite automata with both nondeterministic and probabilistic states. Manuscript in preparation, 1993.","DOI":"10.1145\/195058.195431"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"C. Dwork and L. Stockmeyer. On the power of 2-way probabilistic finite state automata. In Proc. 30th Ann. Symp. Found. Comput. Sci., pages 480\u2013485. IEEE Press, 1989.","DOI":"10.1109\/SFCS.1989.63522"},{"key":"50_CR8","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"C. Dwork and L. Stockmeyer. A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput.\n19 (1990), 1011\u20131023.","journal-title":"SIAM J. Comput."},{"key":"50_CR9","unstructured":"J. Gabarr\u00f3. Initial index: a new complexity function for languages. In J. D\u00edaz, editor, ICALP '83: 10th International Colloquium on Automata, Languages, and Programming, Vol. 154 of Lecture Notes in Computer Science, pages 226\u2013236. Springer-Verlag, 1983."},{"key":"50_CR10","unstructured":"J. Gabarr\u00f3. Funciones de complejidad y su relaci\u00f3n con las familias abstractas de lenguajes. PhD thesis, Facultdad de Informatica, Universidad Politecnica de Barcelona, 1983. In Spanish."},{"key":"50_CR11","first-page":"96","volume":"2","author":"V. S. Grinberg","year":"1966","unstructured":"V. S. Grinberg and A. D. Korshunov. Asymptotic behavior of the maximum of the weight of a finite tree. Problemy Peredachi Informatsii\n2 (1966), 96\u201399. In Russian. English translation in Problems of Information Transmission\n2 (1966), 75\u201378.","journal-title":"Problemy Peredachi Informatsii"},{"key":"50_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02088003","volume":"21","author":"O. H. Ibarra","year":"1988","unstructured":"O. H. Ibarra and B. Ravikumar. Sublogarithmic-space Turing machines, nonuniform space complexity, and closure properties. Math. Systems Theory\n21 (1988), 1\u201317.","journal-title":"Math. Systems Theory"},{"key":"50_CR13","doi-asserted-by":"crossref","unstructured":"J. Kaneps and R. Freivalds. Minimal nontrivial space complexity of probabilistic one-way Turing machines. In B. Rovan, editor, MFCS '90 (Mathematical Foundations of Computer Science), Vol. 452 of Lecture Notes in Computer Science, pages 355\u2013361. Springer-Verlag, 1990.","DOI":"10.1007\/BFb0029629"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"J. Kaneps and R. Freivalds. Running time to recognize nonregular languages by 2-way probabilistic automata. In J. Leach Albert, B. Monien, and M. Rodr\u00edguez Artalejo, editors, ICALP '91 (18th International Colloquium on Automata, Languages, and Programming), Vol. 510 of Lecture Notes in Computer Science, pages 174\u2013185. Springer-Verlag, 1991.","DOI":"10.1007\/3-540-54233-7_133"},{"key":"50_CR15","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0166-218X(83)90002-1","volume":"5","author":"J. Karhum\u00e4ki","year":"1983","unstructured":"J. Karhum\u00e4ki. On cube-free \u03a9-words generated by binary morphisms. Disc. Appl. Math.\n5 (1983), 279\u2013297.","journal-title":"Disc. Appl. Math."},{"key":"50_CR16","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1145\/321406.321410","volume":"14","author":"R. M. Karp","year":"1967","unstructured":"R. M. Karp. Some bounds on the storage requirements of sequential machines and Turing machines. J. Assoc. Comput. Mach.\n14 (1967), 478\u2013489.","journal-title":"J. Assoc. Comput. Mach."},{"key":"50_CR17","first-page":"75","volume":"13","author":"V. A. Kuz'min","year":"1965","unstructured":"V. A. Kuz'min. Realization of functions of the algebra of logic by means of automata, normal algorithms, and turing machines. Problemy Kibernetiki\n13 (1965), 75\u201396. In Russian.","journal-title":"Problemy Kibernetiki"},{"key":"50_CR18","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF00263766","volume":"9","author":"J. Paredaens","year":"1977","unstructured":"J. Paredaens and R. Vyncke. A class of measures on formal langauges. Acta Informatica\n9 (1977), 73\u201386.","journal-title":"Acta Informatica"},{"key":"50_CR19","unstructured":"G. Rauzy. Suites \u00e0 termes dans un alphabet fini. S\u00e9m. de Th\u00e9orie des Nombres de Bordeaux (1982\u20131983), 25-01-25-16."},{"key":"50_CR20","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1051\/ita\/1989230302811","volume":"23","author":"M. J. Serna","year":"1989","unstructured":"M. J. Serna. Asymptotical behaviour of some non-uniform measures. RAIRO Informatique Th\u00e9orique et Applications\n23 (1989), 281\u2013293.","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"50_CR21","first-page":"186","volume":"5","author":"B. A. Trakhtenbrot","year":"1964","unstructured":"B. A. Trakhtenbrot. On an estimate for the weight of a finite tree. Sibirskii Matematicheskii Zhurnal\n5 (1964), 186\u2013191. In Russian.","journal-title":"Sibirskii Matematicheskii Zhurnal"},{"key":"50_CR22","volume-title":"Fundamental Studies in Computer Science","author":"B. A. Trakhtenbrot","year":"1973","unstructured":"B. A. Trakhtenbrot and Ya. M. Barzdin'. Finite Automata: Behavior and Synthesis, Vol. 1 of Fundamental Studies in Computer Science. North-Holland, Amsterdam, 1973."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:23:20Z","timestamp":1578525800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_176"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_176","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}