Paper: Semantic Minimization of 3-Valued Propositional Formulae (at LICS 2002)

Authors: Thomas W. Reps Alexey Loginov Shmuel Sagiv

Abstract

This paper presents an algorithm for a non-standard logic-minimization problem that arises in 3-valued propositional logic. The problem is motivated by the potential for obtaining better answers in applications that use 3-valued logic. An answer of 0 or 1 provides precise (definite) information; an answer of 1/2 provides imprecise (indefinite) information. By replacing a formula phi with a ``better'' formula psi, we may improve the precision of the answers obtained. In this paper, we give an algorithm that always produces a formula that is ``best'' (in a certain well-defined sense).

BibTeX

  @InProceedings{RepsLoginovSagiv-SemanticMinimizatio,
    author = 	 {Thomas W. Reps and Alexey Loginov and Shmuel Sagiv},
    title = 	 {Semantic Minimization of 3-Valued Propositional Formulae},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science (LICS 2002)},
    year =	 {2002},
    month =	 {July}, 
    pages =      {40--51},
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }