{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T07:28:07Z","timestamp":1725694087620},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540079125"},{"type":"electronic","value":"9783642952890"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1976]]},"DOI":"10.1007\/978-3-642-95289-0_12","type":"book-chapter","created":{"date-parts":[[2012,7,28]],"date-time":"2012-07-28T16:50:54Z","timestamp":1343494254000},"page":"148-163","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Decision Problems for Classes of Simple Programs on Strings"],"prefix":"10.1007","author":[{"given":"G.","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"M.","family":"Moscarini","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","volume-title":"Simple programs on strings and their decision problems","author":"G Ausiello","year":"1975","unstructured":"AUSIELLO G.(1975). Simple programs on strings and their decision problems. Istituto di Automatica, R.75\u201315, Roma."},{"key":"12_CR2","volume-title":"A notion of realizability for decidable logical theories","author":"J Cherniavsky","year":"1974","unstructured":"CHERNIAVSKY J(1974). A notion of realizability for decidable logical theories. SUNY at Stony Brook, Dept. of C.S."},{"key":"12_CR3","volume-title":"A note on simple programs and 2-way finite state transducers","author":"MP Chytil","year":"1976","unstructured":"CHYTIL M.P.(1976). A note on simple programs and 2-way finite state transducers (in preparation)."},{"key":"12_CR4","volume-title":"On the computational complexity of scheme equivalencc","author":"RL Constable","year":"1974","unstructured":"CONSTABLE R.L., H.B. HUNT III, S. SAHNI (1974). On the computational complexity of scheme equivalencc. Dept. C.S.-TR 74\u2013201, Cornell University."},{"key":"12_CR5","volume-title":"Feasibly constructive proofs and the propositional calculus. Proceedings of VII ACM Symposium on Theory of Computing","author":"S Cook","year":"1975","unstructured":"COOK S.(1975). Feasibly constructive proofs and the propositional calculus. Proceedings of VII ACM Symposium on Theory of Computing, Albuqyerque, N.M."},{"key":"12_CR6","volume-title":"Some classes of recursive functions","author":"A Grzegorczyk","year":"1953","unstructured":"GRZEGORCZYK A.(1953). Some classes of recursive functions. Rozprawy Maternatyczne, 4."},{"key":"12_CR7","volume-title":"Hierarchies of primitive recursive word functions and transductions defined by automata. Automata","author":"FW Henke","year":"1972","unstructured":"HENKE F.W., K.INDERMARK, K.WEIHRAUCH (1972). Hierarchies of primitive recursive word functions and transductions defined by automata. Automata, Languages and Programming, Nivat Ed. North Holland."},{"key":"12_CR8","volume-title":"New problems complete for nondeterministic log space","author":"ND Jones","year":"1975","unstructured":"JONES N.D.,Y.E. LIEN,W.T. LAASER (1975). New problems complete for nondeterministic log space. (S-TR-75) University of Kansas."},{"key":"12_CR9","volume-title":"Even simple programs are hard to analyse","author":"ND Jones","year":"1975","unstructured":"JONES N.D.,S. MUCHNICK (1975). Even simple programs are hard to analyse. To be published in JACM."},{"key":"12_CR10","volume-title":"Computational complewity and program structure","author":"AR Meyer","year":"1967","unstructured":"MEYER A.R., D.M. RITCHIE (1967). Computational complewity and program structure. IBM Research RC-1817."},{"key":"12_CR11","volume-title":"The equivalence problem for regular expressions with squaring requires exponential space","author":"AR Meyer","year":"1972","unstructured":"MEYER A.R., L. J. STOCKMEYER (1972). The equivalence problem for regular expressions with squaring requires exponential space. XIII Symposium on Switching and Automata Theory."},{"key":"12_CR12","volume-title":"Word problems requiring exponential time","author":"AR Meyer","year":"1973","unstructured":"MEYER A.R., L.U. STOCKMEYER (1973). Word problems requiring exponential time. Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, Austin, Texas."},{"key":"12_CR13","volume-title":"Eine charackterisierung der klassen L, und R, primitiv-rekursiver Wortfunktionen","author":"G Rose","year":"1973","unstructured":"ROSE G., K. WEIHRAUCH (1973). Eine charackterisierung der klassen L, und R, primitiv-rekursiver Wortfunktionen. GMD \u2014 Bericht 63."},{"key":"12_CR14","volume-title":"The equivalence problem of simple programs","author":"D Tsichritzis","year":"1970","unstructured":"TSICHRITZIS D. (1970). The equivalence problem of simple programs. JACM 17,4."},{"key":"12_CR15","volume-title":"Teilklassen primitiv-rekursiver Wortfunktionen","author":"K Weihrauch","year":"1974","unstructured":"WEIHRAUCH K.(1974). Teilklassen primitiv-rekursiver Wortfunktionen. BMFT \u2014 GMD \u2014 91."}],"container-title":["GI \u2014 6. Jahrestagung"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-95289-0_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T15:09:20Z","timestamp":1606489760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-95289-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976]]},"ISBN":["9783540079125","9783642952890"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-95289-0_12","relation":{},"subject":[],"published":{"date-parts":[[1976]]}}}