{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T19:00:38Z","timestamp":1762542038771,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>We construct finite groups whose Cayley graphs have large girth even with respect to a discounted distance measure that contracts arbitrarily long sequences of edges from the same color class (subgroup), and only counts transitions between color classes (cosets). These groups are shown to be useful in the construction of finite bisimilar hypergraph covers that avoid any small cyclic configurations. We present two applications to the finite model theory of the guarded fragment: a strengthening of the known finite model property for GF and the characterization of GF as the guarded bisimulation invariant fragment of first-order logic in the sense of finite model theory.<\/jats:p>","DOI":"10.1145\/2108242.2108247","type":"journal-article","created":{"date-parts":[[2012,2,28]],"date-time":"2012-02-28T12:58:35Z","timestamp":1330433915000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Highly acyclic groups, hypergraph covers, and the guarded fragment"],"prefix":"10.1145","volume":"59","author":[{"given":"Martin","family":"Otto","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,3,2]]},"reference":[{"volume-title":"Eds.","year":"1995","author":"Alon N.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1023\/A:1004275029985"},{"unstructured":"Baader F. Calvanese D. McGuinness D. Nardi D. and Patel-Schneider P. Eds. 2003. The Description Logic Handbook. Cambridge University Press.   Baader F. Calvanese D. McGuinness D. Nardi D. and Patel-Schneider P. Eds. 2003. The Description Logic Handbook. Cambridge University Press.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/LICS.2010.26"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/2402.322389"},{"unstructured":"Berge C. 1973. Graphs and Hypergraphs. North-Holland.   Berge C. 1973. Graphs and Hypergraphs. North-Holland.","key":"e_1_2_1_6_1"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/LICS.2005.27"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/602220.602222"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1515\/9781400879915-019"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/504794.504798"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/382780.382783"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.2307\/2586808"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/507382.507388"},{"unstructured":"Grohe M. 2008. Logic graphs and algorithms. In Logic and Automata History and Perspectives J. Flum E. Gr\u00e4del and T. Wilke Eds. Amsterdam University Press 357--422.  Grohe M. 2008. Logic graphs and algorithms. In Logic and Automata History and Perspectives J. Flum E. Gr\u00e4del and T. Wilke Eds. Amsterdam University Press 357--422.","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.2178\/bsl\/1058448678"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.5555\/645683.664574"},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Logic","volume-title":"Colloquium Logicum","author":"Otto M.","year":"2002"},{"unstructured":"Otto M. 2009. Avoiding incidental homomorphisms into guarded covers. Tech. rep. no. 2600 TU Darmstadt.  Otto M. 2009. Avoiding incidental homomorphisms into guarded covers. Tech. rep. no. 2600 TU Darmstadt.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/LICS.2010.14"},{"key":"e_1_2_1_21_1","volume-title":"LMS Lecture Note Series Series","volume":"379","author":"Otto M.","year":"2011"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1023\/A:1008275906015"},{"unstructured":"van Benthem J. 1983. Modal Logic and Classical Logic. Bibliopolis Napoli.  van Benthem J. 1983. Modal Logic and Classical Logic. Bibliopolis Napoli.","key":"e_1_2_1_23_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2108242.2108247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2108242.2108247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:08Z","timestamp":1750241168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2108242.2108247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2108242.2108247"],"URL":"https:\/\/doi.org\/10.1145\/2108242.2108247","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2010-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}