{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:19Z","timestamp":1750220179883,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":15,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533368","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Separating LREC from LFP"],"prefix":"10.1145","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Technology, University of Cambridge, United Kingdom"}]},{"given":"Felipe","family":"Ferreira Santos","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, University of Cambridge, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On the Power of Symmetric Linear Programs. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS. 1\u201313","author":"Atserias A.","year":"2019","unstructured":"A. Atserias , A. Dawar , and J. Ochremiak . 2019 . On the Power of Symmetric Linear Programs. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS. 1\u201313 . https:\/\/doi.org\/10.1109\/LICS. 2019 .8785792 10.1109\/LICS.2019.8785792 A. Atserias, A. Dawar, and J. Ochremiak. 2019. On the Power of Symmetric Linear Programs. In 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS. 1\u201313. https:\/\/doi.org\/10.1109\/LICS.2019.8785792"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728816.2728820"},{"key":"e_1_3_2_1_4_1","unstructured":"H-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory(2nd ed.). Springer.  H-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory(2nd ed.). Springer."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1995.523268"},{"key":"e_1_3_2_1_6_1","volume-title":"SIAM-AMS Proc. 7 (01","author":"Fagin Ronald","year":"1974","unstructured":"Ronald Fagin . 1974 . Generalized first-order spectra, and polynomial. time recognizable sets . SIAM-AMS Proc. 7 (01 1974). Ronald Fagin. 1974. Generalized first-order spectra, and polynomial. time recognizable sets. SIAM-AMS Proc. 7 (01 1974)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1081"},{"key":"e_1_3_2_1_8_1","volume-title":"Choiceless Logarithmic Space. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0138)","author":"Gr\u00e4del Erich","year":"2019","unstructured":"Erich Gr\u00e4del and Svenja Schalth\u00f6fer . 2019 . Choiceless Logarithmic Space. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0138) , Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1\u201331:15. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS. 2019.31 10.4230\/LIPIcs.MFCS.2019.31 Erich Gr\u00e4del and Svenja Schalth\u00f6fer. 2019. Choiceless Logarithmic Space. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0138), Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1\u201331:15. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.31"},{"volume-title":"Vol.\u00a047","author":"Grohe Martin","key":"e_1_3_2_1_9_1","unstructured":"Martin Grohe . 2017. Descriptive Complexity , Canonisation, and Definable Graph Structure Theory . Lecture Notes in Logic , Vol.\u00a047 . Cambridge University Press . Martin Grohe. 2017. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic, Vol.\u00a047. Cambridge University Press."},{"key":"e_1_3_2_1_10_1","volume-title":"L-Recursion and a new Logic for Logarithmic Space. Log. Methods Comput. Sci. 9","author":"Grohe Martin","year":"2012","unstructured":"Martin Grohe , Berit Gru\u00dfien , Andr\u00e9 Hernich , and Bastian Laubner . 2012. L-Recursion and a new Logic for Logarithmic Space. Log. Methods Comput. Sci. 9 ( 2012 ). https:\/\/doi.org\/10.2168\/LMCS-9(1:11)2013 10.2168\/LMCS-9(1:11)2013 Martin Grohe, Berit Gru\u00dfien, Andr\u00e9 Hernich, and Bastian Laubner. 2012. L-Recursion and a new Logic for Logarithmic Space. Log. Methods Comput. Sci. 9 (2012). https:\/\/doi.org\/10.2168\/LMCS-9(1:11)2013"},{"volume-title":"Proc. 7th International Conference on Database Theory(LNCS, Vol.\u00a01540)","author":"Grohe M.","key":"e_1_3_2_1_11_1","unstructured":"M. Grohe and J. Mari\u00f1o . 1999. Definability and Descriptive Complexity on Databases of Bounded Tree-Width . In Proc. 7th International Conference on Database Theory(LNCS, Vol.\u00a01540) . Springer, 70\u201382. M. Grohe and J. Mari\u00f1o. 1999. Definability and Descriptive Complexity on Databases of Bounded Tree-Width. In Proc. 7th International Conference on Database Theory(LNCS, Vol.\u00a01540). Springer, 70\u201382."},{"key":"e_1_3_2_1_12_1","volume-title":"Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs. Log. Methods Comput. Sci. 15","author":"Gru\u00dfien Berit","year":"2019","unstructured":"Berit Gru\u00dfien . 2019. Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs. Log. Methods Comput. Sci. 15 ( 2019 ). https:\/\/doi.org\/10.23638\/LMCS-15(3:2)2019 10.23638\/LMCS-15(3:2)2019 Berit Gru\u00dfien. 2019. Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs. Log. Methods Comput. Sci. 15 (2019). https:\/\/doi.org\/10.23638\/LMCS-15(3:2)2019"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. 1999. Descriptive Complexity. Springer.  N. Immerman. 1999. Descriptive Complexity. Springer.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_2_1_14_1","volume-title":"Describing Graphs: A First-order Approach to Graph Canonization. In Complexity Theory Retrospective, A.\u00a0Selman (Ed.)","author":"Immerman N.","year":"1990","unstructured":"N. Immerman and E.\u00a0 S. Lander . 1990 . Describing Graphs: A First-order Approach to Graph Canonization. In Complexity Theory Retrospective, A.\u00a0Selman (Ed.) . Springer-Verlag . N. Immerman and E.\u00a0S. Lander. 1990. Describing Graphs: A First-order Approach to Graph Canonization. In Complexity Theory Retrospective, A.\u00a0Selman (Ed.). Springer-Verlag."},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","key":"e_1_3_2_1_15_1","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"],"location":"Haifa Israel","acronym":"LICS '22"},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533368","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":15,"alternative-id":["10.1145\/3531130.3533368","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533368","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}