{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:10Z","timestamp":1725488590706},"publisher-location":"Berlin, Heidelberg","reference-count":21,"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_22","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:32:26Z","timestamp":1186727546000},"page":"217-226","source":"Crossref","is-referenced-by-count":6,"title":["New Small Universal Circular Post Machines"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Kudlek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yurii","family":"Rogozhin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"issue":"4","key":"22_CR1","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1145\/321420.321426","volume":"14","author":"S. Anderaa","year":"1967","unstructured":"Anderaa, S., Fischer, P.: The Solvability of the Halting Problem for 2-state Post Machines. JACM 14 no. 4 (1967) 677\u2013682.","journal-title":"JACM"},{"key":"22_CR2","volume-title":"Theories of Abstract Automata","author":"M. A. Arbib","year":"1969","unstructured":"Arbib, M. A.: Theories of Abstract Automata. Prentice Hall, Englewood Cliffs, 1969."},{"key":"22_CR3","series-title":"Lect Notes Comput Sci","volume-title":"Three Small Universal Turing Machines","author":"C. Baiocchi","year":"2001","unstructured":"Baiocchi, C.: Three Small Universal Turing Machines. LNCS 2055 (2001), Accepted for MCU\u20192001, to appear."},{"key":"22_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/3-540-09526-8_32","volume-title":"Proceedings MFCS\u201979","author":"M. Kudlek","year":"1979","unstructured":"Kudlek, M.: Context Free Normal Systems. Proceedings MFCS\u201979, LNCS 74 (1979) 346\u2013353."},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0304-3975(96)00078-3","volume":"168-2","author":"M. Kudlek","year":"1996","unstructured":"Kudlek, M.: Small deterministic Turing machines. TCS 168-2 (1996) 241\u2013255.","journal-title":"TCS"},{"key":"22_CR6","unstructured":"Kudlek, M., Rogozhin, Yu.: Small Universal Circular Post Machines. Computer Science Journal of Moldova, 9, no. 10 (2001), Accepted for MCU\u20192001, to appear."},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Kudlek, M., Rogozhin, Yu.: A New Small Universal Turing Machine, submitted (2001).","DOI":"10.1007\/3-540-44669-9_22"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(99)00102-4","volume":"231-2","author":"M. Margenstern","year":"2000","unstructured":"Margenstern, M.: Frontier between decidability and undecidability: a survey. TCS 231-2 (2000) 217\u2013251.","journal-title":"TCS"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M. L. Minsky","year":"1961","unstructured":"Minsky, M. L.: Recursive Unsolvability of Posts Problem of \u201dtag\u201d and Other Topics in the Theory of Turing Machines. Annals of Math. 74 (1961) 437\u2013454.","journal-title":"Annals of Math."},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1090\/pspum\/005\/0142452","volume":"5","author":"M. L. Minsky","year":"1962","unstructured":"Minsky, M. L.: Size and Structure of universal Turing Machines Using Tag Systems. In Recursive Function Theory, Symposia in Pure Mathematics, AMS 5 (1962) 229\u2013238.","journal-title":"Recursive Function Theory, Symposia in Pure Mathematics, AMS"},{"key":"22_CR11","volume-title":"Computation: Finite and Infinite Machines","author":"M. L. Minsky","year":"1972","unstructured":"Minsky, M. L.: Computation: Finite and Infinite Machines. Prentice Hall International, London, 1972."},{"key":"22_CR12","volume-title":"Introduction to Automata","author":"R. J. Nelson","year":"1968","unstructured":"Nelson, R. J.: Introduction to Automata. John Wiley & Sons, New York, 1968."},{"key":"22_CR13","first-page":"91","volume":"33","author":"L. Pavlotskaya","year":"1978","unstructured":"Pavlotskaya, L.: Sufficient conditions for halting problem decidability of Turing machines. Avtomaty i mashiny (Problemi kibernetiki), Moskva, Nauka 33 (1978) 91\u2013118 (in Russian).","journal-title":"Avtomaty i mashiny (Problemi kibernetiki), Moskva, Nauka"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"P\u0103un, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, 1998.","DOI":"10.1007\/978-3-662-03563-4"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.2307\/2371809","volume":"65","author":"E. Post","year":"1943","unstructured":"Post, E.: Formal Reduction of the General Combinatorial Decision Problem. Amer. Journ. Math. 65 (1943) 197\u2013215.","journal-title":"Amer. Journ. Math."},{"issue":"5","key":"22_CR16","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1142\/S0129167X91000302","volume":"2","author":"R. M. Robinson","year":"1991","unstructured":"Robinson, R. M.: Minsky\u2019s Small Universal Turing Machine. Intern. Journ. of Math. 2 no. 5 (1991) 551\u2013562.","journal-title":"Intern. Journ. of Math."},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","volume":"168-2","author":"Yu. V. Rogozhin","year":"1996","unstructured":"Rogozhin, Yu. V.: Small Universal Turing Machines. TCS 168-2 (1996) 215\u2013240.","journal-title":"TCS"},{"issue":"3","key":"22_CR18","first-page":"259","volume":"1","author":"Yu. Rogozhin","year":"1998","unstructured":"Rogozhin, Yu.: A Universal Turing Machine with 22 States and 2 Symbols. Romanian Journal of Information Science and Technology 1 no. 3 (1998) 259\u2013265.","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"22_CR19","first-page":"157","volume":"34","author":"C. E. Shannon","year":"1956","unstructured":"Shannon, C. E.: A Universal Turing Machine with Two Internal States. In Automata Studies, Ann. Math. Stud. 34, Princeton Uni. Press (1956) 157\u2013165.","journal-title":"Automata Studies, Ann. Math. Stud."},{"key":"22_CR20","volume-title":"The Mathematical Theory of L Systems","author":"G. Rozenberg","year":"1980","unstructured":"Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. Academic Press, New York, 1980."},{"key":"22_CR21","volume-title":"Theory of Automata","author":"A. Salomaa","year":"1969","unstructured":"Salomaa, A.: Theory of Automata. Pergamon Press, Oxford, 1969."}],"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_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:13:03Z","timestamp":1556734383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}