Switch-List Representations in a Knowledge Compilation Map

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10424880" target="_blank" >RIV/00216208:11320/20:10424880 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.24963/ijcai.2020/229" target="_blank" >https://doi.org/10.24963/ijcai.2020/229</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2020/229" target="_blank" >10.24963/ijcai.2020/229</a>

Result language

angličtina

Original language name

Switch-List Representations in a Knowledge Compilation Map

Original language description

In this paper we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists. Given a truth table representation of a Boolean function f the switch-list representation (SLR) of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include the language SL of all SLR in the Knowledge Compilation Map [Darwiche and Marquis, 2002] and to argue, that SL may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First we compare SL with a number of standard representation languages (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incomparability of MODS (models) and PI (prime implicates) languages. Next we analyze which standard transformations and queries (those considered in [Darwiche and Marquis, 2002] can be performed in poly-time with respect to the size of the input SLR. We show that this collection is quite broad and the combination of poly-time transformations and queries is quite unique.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA19-19463S" target="_blank" >GA19-19463S: Boolean Representation Languages Complete for Unit Propagation</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI-20}

ISBN

978-0-9992411-6-5

ISSN

—

e-ISSN

—

Number of pages

7

Pages from-to

1651-1657

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

California, USA

Event location

Yokohama

Event date

Jul 11, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—