Antiprenexing for WSkS: A Little Goes a Long Way

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F20%3APU138621" target="_blank" >RIV/00216305:26230/20:PU138621 - isvavai.cz</a>

Result on the web

<a href="https://www.fit.vut.cz/research/publication/12287/" target="_blank" >https://www.fit.vut.cz/research/publication/12287/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.29007/6bfc" target="_blank" >10.29007/6bfc</a>

Result language

angličtina

Original language name

Antiprenexing for WSkS: A Little Goes a Long Way

Original language description

We study light-weight techniques for preprocessing of WSkS formulae in an automata-based decision procedure as implemented, e.g., in Mona. The techniques we use are based on antiprenexing, i.e., pushing quantifiers deeper into a formula. Intuitively, this tries to alleviate the explosion in the size of the constructed automata by making it happen sooner on smaller automata (and have the automata minimization reduce the output). The formula transformations that we use to implement antiprenexing may, however, be applied in different ways and extent and, if used in an unsuitable way, may also cause an explosion in the size of the formula and the automata built while deciding it. Therefore, our approach uses informed rules that use an estimation of the cost of constructing automata for WSkS formulae. The estimation is based on a model learnt from runs of the decision algorithm on various formulae. An experimental evaluation of our technique shows that antiprenexing can significantly boost the performance of the base WSkS decision procedure, sometimes allowing one to decide formulae that could not be decided before.

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

Result was created during the realization of more than one project. More information in the Projects tab.

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

EPiC Series in Computing

ISBN

—

ISSN

2398-7340

e-ISSN

—

Number of pages

19

Pages from-to

298-316

Publisher name

EasyChair

Place of publication

Manchester

Event location

Alicante

Event date

May 23, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—