{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:11:59Z","timestamp":1782263519755,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540095262","type":"print"},{"value":"9783540350880","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1979]]},"DOI":"10.1007\/3-540-09526-8_6","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:49:28Z","timestamp":1330188568000},"page":"70-88","source":"Crossref","is-referenced-by-count":5,"title":["Relative succinctness of representations of languages and separation of complexity classes"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T. P.","family":"Baker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"6_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A.V., J.E. Hopcroft and J.D. Ullman, \"The Design and Analysis of Computer Algorithms,\" Addison-Wesley, Reading, Massachusetts, 1974."},{"key":"6_CR2","unstructured":"Baker, T.P., \"On \"Provable\" Analogs of P and NP,\" Mathematical Systems Theory (to appear)."},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0019-9958(67)90546-3","volume":"11","author":"M. Blum","year":"1967","unstructured":"Blum, M., \"On the Size of Machines,\" Information and Control, Vol. 11 (1967), 257\u2013265.","journal-title":"Information and Control"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/321832.321839","volume":"21","author":"G. J. Chaitin","year":"1974","unstructured":"Chaitin, G.J., \"Information Theoretic Limitations of Formal Systems,\" J. ACM 21, (1974), 403\u2013424.","journal-title":"J. ACM"},{"key":"6_CR5","unstructured":"Hartmanis, J., \"On the Succinctness of Different Representations of Languages,\" SIAM J. Computing (to appear)."},{"key":"6_CR6","first-page":"1","volume-title":"Advances in Computers Vol. 14","author":"J. Hartmanis","year":"1976","unstructured":"Hartmanis, J. and J. Simon., \"On the Structure of Feasible Computations,\" Advances in Computers Vol. 14, Morris Rubinoff and Marshall C. Yovits, eds., 1\u201343, Academic Press, New York, 1976."},{"key":"6_CR7","first-page":"265","volume":"9","author":"L. A. Levin","year":"1973","unstructured":"Levin, L.A., \"Universal Sequential Search Problems,\" Problemy Peredachi Informatsii, Vol. 9 (1973), 265\u2013266.","journal-title":"Problemy Peredachi Informatsii"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/S0019-9958(72)90592-X","volume":"21","author":"A. R. Meyer","year":"1972","unstructured":"Meyer, A.R., \"Program Size in Restricted Programming Languages,\" Information and Control, Vol. 21 (1972), 382\u2013394.","journal-title":"Information and Control"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Meyer, A.R. and M.J. Fischer., \"Economy of Description by Automata, Grammars and Formal Systems,\" Conference Record IEEE 12th Annual Symposium on Switching and Automata Theory (1971), 188\u2013190.","DOI":"10.1109\/SWAT.1971.11"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1137\/0206039","volume":"6","author":"E. H. Schmidt","year":"1977","unstructured":"Schmidt, E.H. and T.G. Szymanski., \"Succinctness of Descriptions of Unambiguous Context-Free Language,\" SIAM J. Computing, Vol. 6 (1977), 547\u2013553.","journal-title":"SIAM J. Computing"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0019-9958(76)90173-X","volume":"32","author":"L. G. Valiant","year":"1976","unstructured":"Valiant, L.G., \"A Note on the Succinctness of Description of Deterministic Languages,\" Information and Control, Vol. 32, (1976), 139\u2013145.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1979"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-09526-8_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:01:02Z","timestamp":1619557262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-09526-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979]]},"ISBN":["9783540095262","9783540350880"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-09526-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979]]}}}