Boosting isomorphic model filtering with invariants

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F22%3A00364201" target="_blank" >RIV/68407700:21730/22:00364201 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10601-022-09336-x" target="_blank" >https://doi.org/10.1007/s10601-022-09336-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10601-022-09336-x" target="_blank" >10.1007/s10601-022-09336-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Boosting isomorphic model filtering with invariants

Popis výsledku v původním jazyce

The enumeration of finite models is very important to the working discrete mathematician (algebra, graph theory, etc) and hence the search for effective methods to do this task is a critical goal in discrete computational mathematics. However, it is hindered by the possible existence of many isomorphic models, which usually only add noise. Typically, they are filtered out a posteriori, a step that might take a long time just to discard redundant models. This paper proposes a novel approach to split the generated models into mutually non-isomorphic blocks. To do that we use well-designed hand-crafted invariants as well as randomly generated invariants. The blocks are then tackled separately and possibly in parallel. This approach is integrated into Mace4 (the most popular tool among mathematicians) where it shows tremendous speed-ups for a large variety of algebraic structures.

Název v anglickém jazyce

Boosting isomorphic model filtering with invariants

Popis výsledku anglicky

The enumeration of finite models is very important to the working discrete mathematician (algebra, graph theory, etc) and hence the search for effective methods to do this task is a critical goal in discrete computational mathematics. However, it is hindered by the possible existence of many isomorphic models, which usually only add noise. Typically, they are filtered out a posteriori, a step that might take a long time just to discard redundant models. This paper proposes a novel approach to split the generated models into mutually non-isomorphic blocks. To do that we use well-designed hand-crafted invariants as well as randomly generated invariants. The blocks are then tackled separately and possibly in parallel. This approach is integrated into Mace4 (the most popular tool among mathematicians) where it shows tremendous speed-ups for a large variety of algebraic structures.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/LL1902" target="_blank" >LL1902: Obohacování SMT řešičů pomocí strojového učení</a><br>

Návaznosti

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

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Svazek periodika

27

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

20

Strana od-do

360-379

Kód UT WoS článku

000811949800001

EID výsledku v databázi Scopus

2-s2.0-85132391947