Isomorphims, Symmetry, and Automorphisms Sample Clauses

Isomorphims, Symmetry, and Automorphisms. An isomorphism θ of a set of models M is a permutation on L that satisfies θ(M ) = M and θ(x) = −y ↔ θ(−x) = y. Suppose I is a PI. Then the set of models of M that are consistent with I is denoted MI. Moreover, the local symmetries associated with I, ΘI, is the set of all isomorphisms of MI, which forms a permutation group. As a special case, a symmetry θ is global if θ ∈ Θ{}. Computing the end result of two or more permutations is called composition, de- noted θ ◦ σ, so that (θ ◦ σ)(x) = θ(σ(x)). We will also denote composition with × so that (σ × θ)(x) = θ(σ(x)). Other than local and global symmetry, there are other important classes of sym- metries [15, 7]. Solution or semantic symmetry is symmetry on the full set of models (of the underlying theory), while constraint, or syntactic symmetry is sym- metry on the formula used to find the models. There is also a notion of literal vs clause symmetry, which act on literals and clauses, respectively. Finding symmetries of logical theories is polytime reducible to finding the auto- morphisms of a graph [17]. An elegant approach is found in [2]. Although there can be many automorphisms, one can store far fewer by using a set of generators where every automorphism can be described as a composition of the generators. Symmetry problems are interesting from a complexity standpoint. They are among the few problems that are known to be in NP , but they have also not been shown to be NP-Complete or in P. There are software packages that can find automorphisms and their generators very quickly in practice including nauty and Traces[35, 36], saucy[32, 33], and bliss [30, 31].