Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331268" target="_blank" >RIV/00216208:11320/16:10331268 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-42432-3_7" target="_blank" >http://dx.doi.org/10.1007/978-3-319-42432-3_7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-42432-3_7" target="_blank" >10.1007/978-3-319-42432-3_7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT

Popis výsledku v původním jazyce

We apply SAT and #-SAT to problems of computational topology: knot detection and recognition. Quandle coloring can be viewed as associations of elements of algebraic structures, called quandles, to arcs of knot diagrams such that certain algebraic relations hold at each crossing. The existence of a coloring (called colorability) and the number of colorings of a knot by a quandle are knot invariants that can be used to distinguish knots. We realise coloring instances as SAT and #-SAT instances, and produce experimental data demonstrating that a SAT-based approach to colorability is a practically efficient method for knot detection and #-SAT can be utilised for knot recognition.

Název v anglickém jazyce

Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT

Popis výsledku anglicky

We apply SAT and #-SAT to problems of computational topology: knot detection and recognition. Quandle coloring can be viewed as associations of elements of algebraic structures, called quandles, to arcs of knot diagrams such that certain algebraic relations hold at each crossing. The existence of a coloring (called colorability) and the number of colorings of a knot by a quandle are knot invariants that can be used to distinguish knots. We realise coloring instances as SAT and #-SAT instances, and produce experimental data demonstrating that a SAT-based approach to colorability is a practically efficient method for knot detection and #-SAT can be utilised for knot recognition.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA13-01832S" target="_blank" >GA13-01832S: Obecná algebra a její souvislost s informatikou</a><br>

Návaznosti

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

Rok uplatnění

2016

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 statě ve sborníku

MATHEMATICAL SOFTWARE, ICMS 2016

ISBN

978-3-319-42432-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

8

Strana od-do

51-58

Název nakladatele

SPRINGER INT PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Zuse Inst, Berlin

Datum konání akce

11. 7. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000387431800007