{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T05:37:22Z","timestamp":1737610642348,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540665366"},{"type":"electronic","value":"9783540481683"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48168-0_24","type":"book-chapter","created":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T11:30:26Z","timestamp":1196508626000},"page":"338-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Directed Reachability: From Ajtai-Fagin to Ehrenfeucht-Fra\u00efss\u00e9 Games"],"prefix":"10.1007","author":[{"given":"Jerzy","family":"Marcinkowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"issue":"1","key":"24_CR1","first-page":"113","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai, R. Fagin Reachability is harder for directed than for undirected finite graphs, Journal of Symbolic Logic, 55(1):113\u2013150, 1990","journal-title":"Reachability is harder for directed than for undirected finite graphs"},{"key":"24_CR2","first-page":"97","volume":"174","author":"S. Arora","year":"1997","unstructured":"S. Arora, R. Fagin On winning strategies in Ehrenfeucht-Fra?iss\u00e9e games, Theoretical Computer Science, 174:97\u2013121, 1997","journal-title":"On winning strategies in Ehrenfeucht-Fra?iss\u00e9e games"},{"key":"24_CR3","unstructured":"M. Ajtai, R. Fagin, L. Stockmeyer The Closure of Monadic NP, IBM Research report RJ 10092, November 1997"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Fagin, L. Stockmeyer The Closure of Monadic NP, Proc. of 13th STOC, pp 309\u2013318, 1998","DOI":"10.1145\/276698.276771"},{"key":"24_CR5","first-page":"47","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"M. de Rougemont Second-order and inductive definiability on finite structures, Zeitschrift fuer Mathematische Logik und Grundlagen der Mathematik, 33:47\u201363, 1987","journal-title":"Second-order and inductive definiability on finite structures"},{"key":"24_CR6","first-page":"129","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht an application of games to the completeness problem for formalized theories, Fund. Math. 49:129\u2013141,1961","journal-title":"an application of games to the completeness problem for formalized theories"},{"key":"24_CR7","first-page":"89","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin Monadic Generalized spectra, Zeitschrift fuer Mathematische Logik und Grundlagen der Mathematik, 21;89\u201396, 1975","journal-title":"Monadic Generalized spectra"},{"key":"24_CR8","first-page":"431","volume":"43","author":"R. Fagin","year":"1997","unstructured":"R. Fagin Comparing the power of games on graphs, Math. Logic Quarterly 43, 1997, pp. 431\u2013455","journal-title":"Comparing the power of games on graphs"},{"key":"24_CR9","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9 Sur quelques classifications des systemes de relations, Publ. Sci. Univ. Alger. Ser. A, 1:35\u2013182, 1954","journal-title":"Sur quelques classifications des systemes de relations"},{"issue":"1","key":"24_CR10","first-page":"78","volume":"120","author":"R. Fagin","year":"1995","unstructured":"R. Fagin, L. Stockmeyer, M. Vardi On monadic NP vs. monadic co-NP, Information and Computation, 120(1):78\u201392, July 1995","journal-title":"On monadic NP vs. monadic co-NP"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/3-540-60084-1_92","volume-title":"Automata, Languages and Programming","author":"Thomas Schwentick","year":"1995","unstructured":"T. Schwentick Graph connectivity, monadic NP and built-in relations of moderate degree, Proceedings of 22nd ICALP: 405\u2013416,1995"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48168-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T03:45:32Z","timestamp":1737603932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48168-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540665366","9783540481683"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-48168-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"13 May 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}