{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:56Z","timestamp":1725663776077},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544876"},{"type":"electronic","value":"9783540384014"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_68","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:54:15Z","timestamp":1330210455000},"page":"318-339","source":"Crossref","is-referenced-by-count":4,"title":["Nontrivial lower bounds for some NP-problems on directed graphs"],"prefix":"10.1007","author":[{"given":"Solomampionona","family":"Ranaivoson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(88)90152-4","volume":"26","author":"S. A. Cook","year":"1987","unstructured":"S. A. COOK, Short propositional formulas represent nondeterministic computations, Information Processing Letters 26 (1987\/88) 269\u2013270, North-Holland.","journal-title":"Information Processing Letters"},{"key":"20_CR2","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M. S. Garey","year":"1979","unstructured":"M. S. GAREY and D. S. JOHNSON, Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"E. GRANDJEAN, A natural NP-complete problem with a nontrivial lower bound, SIAM J. Comput., 1988.","DOI":"10.1137\/0217050"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"E. GRANDJEAN, A nontrivial lower bound for an NP problem on Automata, SIAM J. Comput., 1990. pp. 438\u2013451.","DOI":"10.1137\/0219028"},{"key":"20_CR5","unstructured":"E. GRANDJEAN, personal communication, 1990"},{"key":"20_CR6","unstructured":"F. HARARY, An introduction to the theory of directed graphs, John Wiley and Sons, 1965."},{"key":"20_CR7","unstructured":"J. F. LYNCH, The quantifier structure of sentences that characterize non-deterministic time-complexity, Logic in computer science, Proceeding colloquium, July 1990."},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1109\/TEC.1959.5222697","volume":"EC-8","author":"C. P. Pfleeger","year":"1959","unstructured":"C. P. PFLEEGER, State reduction in incompletely specified sequential switching functions, IRE Trans. Electron. Comput EC-8 (1959), 356\u2013367.","journal-title":"IRE Trans. Electron. Comput"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"W. J. PAUL, N. PIPPENGER, E. SZEMERDI and W. T. TROTTER, On determinism versus nondeterminism and related problems, Proc 24 th IEEE Symp. On Foundations of Computer Science. IEE (1983), 428\u2013438.","DOI":"10.1109\/SFCS.1983.39"},{"key":"20_CR10","unstructured":"S. RANAIVOSON, bornes inf\u00e9rieures non triviales pour des probl\u00e8mes NP en th\u00e9orie des graphes et des automates, th\u00e8se de doctorat, laboratoire d'informatique de l'universit\u00e9 de Caen"},{"key":"20_CR11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"M. de Rougemont, Second-order and inductive definability on finite structures, Zeitschr. f. math. Logik und Grundalgen d. Math. 33 (1987), 47\u201363.","journal-title":"Zeitschr. f. math. Logik und Grundalgen d. Math."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_68.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:08Z","timestamp":1605646508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}