Thumbnail
Access Restriction
Subscribed

Author Otto, Martin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Finite model theory ♦ Expressive completeness ♦ Groups of large girth ♦ Guarded fragment
Abstract 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-03-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 59
Issue Number 1
Page Count 40
Starting Page 1
Ending Page 40


Open content in new tab

   Open content in new tab
Source: ACM Digital Library