{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T19:17:17Z","timestamp":1768677437904,"version":"3.49.0"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8777,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1990,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain \u201cbuilt-in\u201d relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fra\u00efss\u00e9 games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most<jats:italic>k<\/jats:italic>, reachability is expressible by an existential monadic second-order sentence.<\/jats:p>","DOI":"10.2307\/2274958","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:33:48Z","timestamp":1146954828000},"page":"113-150","source":"Crossref","is-referenced-by-count":93,"title":["Reachability is harder for directed than for undirected finite graphs"],"prefix":"10.1017","volume":"55","author":[{"given":"Miklos","family":"Ajtai","sequence":"first","affiliation":[]},{"given":"Ronald","family":"Fagin","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200026475_ref037","first-page":"137","volume-title":"Proceedings of the Fourteenth ACM Symposium on Theory of Computing","author":"Vardi","year":"1982"},{"key":"S0022481200026475_ref016","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"S0022481200026475_ref011","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"S0022481200026475_ref036","first-page":"1","volume-title":"Proceedings of the Sixth ACM Symposium on Principles of Database Systems","author":"Ullman","year":"1987"},{"key":"S0022481200026475_ref034","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330107"},{"key":"S0022481200026475_ref032","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786976"},{"key":"S0022481200026475_ref031","first-page":"464","volume-title":"Proceedings of the Twenty-sixth IEEE Symposium on Foundations of Computer Science","author":"Lov\u00e1sz","year":"1985"},{"key":"S0022481200026475_ref029","first-page":"425","volume-title":"Proceedings of the Nineteenth ACM Symposium on Theory of Computing","author":"Kolaitis","year":"1987"},{"key":"S0022481200026475_ref028","first-page":"539","volume-title":"Proceedings of the Twentieth ACM Symposium on Theory of Computing","author":"Karchmer","year":"1988"},{"key":"S0022481200026475_ref027","volume-title":"Foundations of deductive databases and logic programming","author":"Kanellakis","year":"1988"},{"key":"S0022481200026475_ref025","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"S0022481200026475_ref024","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S0022481200026475_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S0022481200026475_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"S0022481200026475_ref035","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"S0022481200026475_ref018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"S0022481200026475_ref017","first-page":"43","volume-title":"Complexity of computation","volume":"7","author":"Fagin","year":"1974"},{"key":"S0022481200026475_ref007","volume-title":"Random graphs","author":"Bollob\u00e1s","year":"1982"},{"key":"S0022481200026475_ref033","first-page":"143","volume-title":"Proceedings of the Seventeenth ACM Symposium on Theory of Computing","author":"Pan","year":"1985"},{"key":"S0022481200026475_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"S0022481200026475_ref019","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","volume":"1","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Publications Scientifiques de l'Universit\u00e9 d'Alger"},{"key":"S0022481200026475_ref004","unstructured":"Anderson R. , Private communication, 05 1987."},{"key":"S0022481200026475_ref020","volume-title":"Computers and intractibility: a guide to the theory of NP-completeness","author":"Garey","year":"1979"},{"key":"S0022481200026475_ref014","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"S0022481200026475_ref003","first-page":"218","volume-title":"Proceedings of the Twentieth IEEE Symposium on Foundations of Computer Science","author":"Aleliunas","year":"1979"},{"key":"S0022481200026475_ref021","volume-title":"Parallel Graph Algorithms","author":"Hochschild","year":"1987"},{"key":"S0022481200026475_ref009","first-page":"116","volume-title":"Proceedings of the Third Conference on Structure in Complexity Theory","author":"Borodin","year":"1988"},{"key":"S0022481200026475_ref005","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/28659.28683","volume-title":"Proceedings of the Sixth ACM Symposium on Principles of Database Systems","author":"Beeri","year":"1987"},{"key":"S0022481200026475_ref006","first-page":"304","volume-title":"Proceedings of the Twenty-fourth IEEE Symposium on Foundations of Computer Science","author":"Berman","year":"1983"},{"key":"S0022481200026475_ref030","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/PSCT.1987.10319272","volume-title":"Proceedings of the Second IEEE Conferencee on Structure in Complexity Theory","author":"Leivant","year":"1987"},{"key":"S0022481200026475_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"S0022481200026475_ref012","volume-title":"On the computational complexity of finding a kernel","author":"Chv\u00e1tal","year":"1973"},{"key":"S0022481200026475_ref008","volume-title":"Handbook of Theoretical Computer Science","author":"Boppana"},{"key":"S0022481200026475_ref013","first-page":"478","volume-title":"Proceedings of the Twenty-seventh IEEE Symposium on Foundations of Computer Science","author":"Cole","year":"1986"},{"key":"S0022481200026475_ref015","first-page":"1","volume-title":"Proceedings of the Nineteenth ACM Symposium on Theory of Computing","author":"Coppersmith","year":"1987"},{"key":"S0022481200026475_ref026","unstructured":"Kanellakis P. , Private communication, 10 1986."},{"key":"S0022481200026475_ref001","first-page":"325","volume-title":"Proceedings of the Nineteenth ACM Symposium on Theory of Computing","author":"Aggarwal","year":"1987"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200026475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:26:48Z","timestamp":1707031608000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200026475\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["S0022481200026475"],"URL":"https:\/\/doi.org\/10.2307\/2274958","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}