Affordable Access

Access to the full text

Boolean Functions as Models for Quantified Boolean Formulas

Authors
  • Kleine Büning, Hans1
  • Subramani, K.2
  • Zhao, Xishun3
  • 1 Universität Paderborn, Department of Computer Science, Paderborn, 33095, Germany , Paderborn (Germany)
  • 2 West Virginia University, LDCSEE, Morgantown, WV, 26506, USA , Morgantown (United States)
  • 3 Sun Yat-sen University, Institute of Logic and Cognition, Guangzhou, 510275, People’s Republic of China , Guangzhou (China)
Type
Published Article
Journal
Journal of Automated Reasoning
Publisher
Kluwer Academic Publishers
Publication Date
Apr 14, 2007
Volume
39
Issue
1
Pages
49–75
Identifiers
DOI: 10.1007/s10817-007-9067-0
Source
Springer Nature
Keywords
License
Yellow

Abstract

In this paper, we introduce the notion of models for quantified Boolean formulas. For various classes of quantified Boolean formulas and various classes of Boolean functions, we investigate the problem of determining whether a model exists. Furthermore, we show for these classes the complexity of the model checking problem, which is to check whether a given set of Boolean functions is a model for a formula. For classes of Boolean functions, we establish some characterizations in terms of classes of quantified Boolean formulas that have such a model.

Report this publication

Statistics

Seen <100 times