We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
CNF-Structure: Stabilizers, Orbits, Fibre-Transversals.
- Authors
Porschen, Stefan
- Abstract
The structure of CNF formulas as well as classes of formulas is considered here from a group theoretic perspective, provided by the action under the complementation group. For this study again, the fibre view approach to CNF on basis of the concepts of base hypergraphs and its fibre-transversals is exploited extensively. Several CNF classes are investigated which are defined via orbits of complementation subgroups. Besides their stabilizer properties we also study to some extent the satisfiability aspects of those classes. In that context it turns out that several results regarding stabilizer properties or satisfiability aspects valid for fibre-transversals cannot be transfered when replacing them with arbitrary CNF formulas. Further we present an algorithm for computing the isotropy groups of fibre formulas, and investigate the lifting process to the total case. The members of several concrete subclasses of CNF are treated thereby such as linear or symmetric formulas.
- Subjects
ORBITS (Astronomy); HYPERGRAPHS; FIBERS
- Publication
IAENG International Journal of Computer Science, 2020, Vol 47, Issue 2, p284
- ISSN
1819-656X
- Publication type
Article