{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:42:14Z","timestamp":1774946534959,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_15","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"172-183","source":"Crossref","is-referenced-by-count":3,"title":["Directed st-Connectivity Is Not Expressible in Symmetric Datalog"],"prefix":"10.1007","author":[{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beno\u00eet","family":"Larose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jcss.1995.1060","volume":"51","author":"F. Afrati","year":"1995","unstructured":"Afrati, F., Cosmadakis, S.S., Yannakakis, M.: On Datalog vs. polynomial time. J. Comput. Syst. Sci.\u00a051(2), 177\u2013196 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected finite graphs. J. Symb. Log.\u00a055(1), 113\u2013150 (1990)","journal-title":"J. Symb. Log."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Cohen, D., Jeavons, P.: The complexity of constaint languages. In: Handbook of Constraint Programming, pp. 245\u2013280 (2006)","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Linear Datalog and bounded path duality of relational structures. Logical Methods in Computer Science\u00a01(1) (2005)","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Egri, L., Larose, B., Tesson, P.: Symmetric Datalog and constraint satisfaction problems in logspace. In: LICS 2007: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, pp. 193\u2013202 (2007)","DOI":"10.1109\/LICS.2007.47"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing complexity classes by fragments of second-order logic. Theor. Comput. Sci.\u00a0101(1), 35\u201357 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems 6. In: ICALP, pp. 267\u2013278 (2007)","DOI":"10.1007\/978-3-540-73420-8_25"},{"key":"15_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of finite model theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of finite model theory. Springer, Heidelberg (2004)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-connectivity in log-space, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:07:56Z","timestamp":1605744476000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}