No Cover Image

Conference Paper/Proceeding/Abstract 496 views

Minimal unsatisfiability and minimal strongly connected digraphs / Hoda Abbasizanjani, Oliver Kullmann

Theory and Applications of Satisfiability Testing - SAT 2018

Swansea University Author: Oliver Kullmann

Abstract

A new method for classification of minimally unsatisfiable clause-sets (MUs) is introduced, connecting MUs with MSDs, minimal strongly connected digraphs. Two basic characterisations of MUs from the literature, namely for deficiency 2 and 2-CNF (the latter only available as technical report) are giv...

Full description

Published in: Theory and Applications of Satisfiability Testing - SAT 2018
ISBN: 978-3-319-42803-1
Published: Oxford, UK Theory and Applications of Satisfiability Testing
URI: https://cronfa.swan.ac.uk/Record/cronfa39955
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: A new method for classification of minimally unsatisfiable clause-sets (MUs) is introduced, connecting MUs with MSDs, minimal strongly connected digraphs. Two basic characterisations of MUs from the literature, namely for deficiency 2 and 2-CNF (the latter only available as technical report) are given lucid and much shorter proofs.
Keywords: minimal unsatisfiability, strong digraphs, minimal strongly connected
College: College of Science