{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:39Z","timestamp":1725456759308},"publisher-location":"Berlin\/Heidelberg","reference-count":15,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029632","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"378-384","source":"Crossref","is-referenced-by-count":3,"title":["Vector language: Simple description of hard instances"],"prefix":"10.1007","author":[{"given":"Miroslaw","family":"Kowaluk","sequence":"first","affiliation":[]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai M., \u03a3 1 1 formulae on finite structures, Annals of Pure and Applied Logic 24 (1983), 1\u201348.","journal-title":"Annals of Pure and Applied Logic"},{"doi-asserted-by":"crossref","unstructured":"Barrington D.A.M., Immerman N., Straubing H., On uniformity within NC1, Proc. 3rd Struct. in Complexity Theory Conf., IEEE (1988), 47\u201359.","key":"41_CR2","DOI":"10.1109\/SCT.1988.5262"},{"key":"41_CR3","first-page":"127","volume":"1","author":"J.L. Bentley","year":"1983","unstructured":"Bentley J.L., Ottmann T., Widmayer P., The complexity of manipulating hierarchically defined sets of rectangles, Adv. Comput. Res. 1 (1983), 127\u2013158.","journal-title":"Adv. Comput. Res."},{"doi-asserted-by":"crossref","unstructured":"Furst M., Saxe J.B., Sipser M., Parity circuits and the polynomial-time hierarchy, Proc. 22nd IEEE Symp. on Fundations of Computer Science (1981), 260\u2013270; see also MST 17 (1984), 13\u201327.","key":"41_CR4","DOI":"10.1007\/BF01744431"},{"key":"41_CR5","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S., Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H.Freeman, San Francisco (1979)."},{"key":"41_CR6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin H., Wigderson A., Succinct representations of graphs, Inform. Control 56 (1983), 183\u2013198.","journal-title":"Inform. Control"},{"key":"41_CR7","first-page":"201","volume":"32","author":"M. Karpinski","year":"1988","unstructured":"Karpinski, M., Wagner, K.W., The computational complexity of graph problems with succinct multigraph representation, ZOR 32 (1988), 201\u2013211,.","journal-title":"ZOR"},{"key":"41_CR8","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner R.E., The circuit value problem is logspace complete for P, SIGACT News 7 (1975), 18\u201320.","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"Lengauer T., The complexity of compacting hierarchically specified layouts of integrated circuits, Proc. 23rd Ann. Symp. on Found. of Comp. Sci. (1982), 358\u2013368.","key":"41_CR9","DOI":"10.1109\/SFCS.1982.92"},{"unstructured":"Lengauer T., Wagner K.W., The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Bericht Nr.33; Reihe Theoretische Informatik, Universit\u00e4t Paderborn (1986).","key":"41_CR10"},{"doi-asserted-by":"crossref","unstructured":"Lengauer T., Wanke E., Efficient analysis of graph properties on context-free graph languages (extended abstract), Proc. of ICALP'88, Springer Lecture Notes in Computer Science (1988), 379\u2013393.","key":"41_CR11","DOI":"10.1007\/3-540-19488-6_129"},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N.A. Lynch","year":"1977","unstructured":"Lynch N.A., Logspace recognition and translation of parenthesis languages, J. Assoc. Comput. Mach. 24 (1977), 583\u2013590.","journal-title":"J. Assoc. Comput. Mach."},{"key":"41_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C.H. Papadimitriou","year":"1986","unstructured":"Papadimitriou C.H., Yannakakis M., A note on succinct representations of graphs, Inform. Control 71 (1986), 181\u2013185.","journal-title":"Inform. Control"},{"doi-asserted-by":"crossref","unstructured":"Stockmeyer L.J., Meyer A.R., Word problems requiring exponential time, Proc. 5th ACM Symp. on Theory of Comp. (1973), 1\u20139.","key":"41_CR14","DOI":"10.1145\/800125.804029"},{"key":"41_CR15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K.W. Wagner","year":"1986","unstructured":"Wagner K.W., The complexity of combinatorial problems with succinct input representation, Acta Informatica 23 (1986), 325\u2013356.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:15:35Z","timestamp":1586592935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0029632","relation":{},"subject":[]}}