@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{BM21a,
  title={Counting Maximal Satisfiable Subsets},
  author={Bendik, Jaroslav and Meel, Kuldeep S.},
  booktitle=AAAI,
  month=feb,
  year={2021},
  bib2html_pubtype={Refereed Conference},
  bib2html_rescat={Counting},
  bib2html_dl_pdf={../Papers/aaai21-bm.pdf},
  abstract={
    Given an unsatisfiable set of constraints F, a maximal satisfiable subset
    (MSS) is a maximal subset of constraints C such that C is satisfiable. Over
    the past two decades, the steady improvement in runtime performance of
    algorithms for finding MSS has led to an increased adoption of MSS-based
    techniques in wide variety of domains. Motivated by the progress in finding
    an MSS, the past decade has witnessed a surge of interest in design of
    algorithmic techniques to enumerate all the MSSes, which has subsequently
    led to discovery of new applications utilizing enumeration of MSSes.
    The development of techniques for finding and enumeration of MSSes mirrors a
    similar phenomenon of finding and enumeration of SAT solutions in the early
    2000s, which subsequently motivated design of algorithmic techniques for
    model counting. In a similar spirit, we undertake study to investigate the
    feasibility of MSS counting techniques. In particular, the focus point of
    our investigation is to answer whether one can design efficient MSS counting
    techniques that do not rely on explicit MSS enumeration. The primary
    contribution of this work is an affirmative answer to the above question.
    Our tool, CountMSS, uses a novel architecture of a wrapper W and a remainder
    R such that the desired MSS count can be expressed as |W|- |R|. CountMSS
    relies on the advances in projected model counting to efficiently compute
    |W| and |R|. Our empirical evaluation demonstrates that CountMSS is able to
    scale to instances clearly beyond the reach of enumeration-based techniques.
  },
}