{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T18:10:42Z","timestamp":1725905442642},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_11","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:37:57Z","timestamp":1500525477000},"page":"160-172","source":"Crossref","is-referenced-by-count":1,"title":["Undecidability and Finite Automata"],"prefix":"10.1007","author":[{"given":"J\u00f6rg","family":"Endrullis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22012-8_1","volume-title":"Automata, Languages and Programming","author":"R Alur","year":"2011","unstructured":"Alur, R., Deshmukh, J.V.: Nondeterministic streaming string transducers. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 1\u201320. Springer, Heidelberg (2011). doi:\n10.1007\/978-3-642-22012-8_1"},{"key":"11_CR2","first-page":"143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase structure grammars. Z. Phonetik. Sprachwiss. Kommuniationsforsch. 14, 143\u2013172 (1961)","journal-title":"Z. Phonetik. Sprachwiss. Kommuniationsforsch."},{"key":"11_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String-Rewriting Systems","author":"RV Book","year":"1993","unstructured":"Book, R.V., Otto, F.: String-Rewriting Systems. Springer, New York (1993). doi:\n10.1007\/978-1-4613-9771-7"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/BF01706087","volume":"6","author":"A Cobham","year":"1972","unstructured":"Cobham, A.: Uniform tag sequences. Math. Syst. Theor. 6, 164\u2013192 (1972)","journal-title":"Math. Syst. Theor."},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322203.322211","volume":"27","author":"J Engelfriet","year":"1980","unstructured":"Engelfriet, J., Rozenberg, G.: Fixed point languages, equality languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach. 27, 499\u2013518 (1980)","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/321150.321153","volume":"10","author":"S Ginsburg","year":"1963","unstructured":"Ginsburg, S., Rose, G.F.: Some recursively unsolvable problems in ALGOL-like languages. J. Assoc. Comput. Mach. 10, 29\u201347 (1963)","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR7","unstructured":"Hoogeboom, H.J.: Are there undecidable properties of non-turing-complete automata? Posting on stackexchange, 20 October 2012. \nhttp:\/\/cs.stackexchange.com\/questions\/1697\/are-there-undecidable-properties-of-non-turing-complete-automata"},{"key":"11_CR8","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"RC Lyndon","year":"1962","unstructured":"Lyndon, R.C., Sch\u00fctzenberger, M.P.: The equation \n            $$a^M = b^N c^P$$\n           in a free group. Mich. Math. J. 9, 289\u2013298 (1962)","journal-title":"Mich. Math. J."},{"key":"11_CR10","first-page":"338","volume-title":"The Undecidable","author":"E Post","year":"1965","unstructured":"Post, E.: Absolutely unsolvable problems and relatively undecidable propositions: account of an anticipation. In: Davis, M. (ed.) The Undecidable, pp. 338\u2013433. Raven Press, Hewlett (1965)"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0129054115500197","volume":"26","author":"E Rowland","year":"2015","unstructured":"Rowland, E., Shallit, J.: Automatic sets of rational numbers. Int. J. Found. Comput. Sci. 26, 343\u2013365 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"11_CR12","volume-title":"Cornerstones of Undecidability","author":"G Rozenberg","year":"1994","unstructured":"Rozenberg, G., Salomaa, A.: Cornerstones of Undecidability. Prentice-Hall, New York (1994)"},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"1611","DOI":"10.1142\/S0129054112400655","volume":"23","author":"L Schaeffer","year":"2012","unstructured":"Schaeffer, L., Shallit, J.: The critical exponent is computable for automatic sequences. Int. J. Found. Comput. Sci. 23, 1611\u20131626 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"11_CR14","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1006\/inco.1994.1076","volume":"113","author":"JO Shallit","year":"1994","unstructured":"Shallit, J.O.: Numeration systems, linear recurrences, and regular sets. Inf. Comput. 113, 331\u2013347 (1994)","journal-title":"Inf. Comput."},{"key":"11_CR16","first-page":"230","volume":"42","author":"AM Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42, 230\u2013265 (1936)","journal-title":"Proc. Lond. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62809-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:40:28Z","timestamp":1500525628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}