Skip to main content

2018 | OriginalPaper | Buchkapitel

Visual Algebraic Proofs for Unknot Detection

verfasst von : Andrew Fish, Alexei Lisitsa, Alexei Vernitski

Erschienen in: Diagrammatic Representation and Inference

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A knot diagram looks like a two-dimensional drawing of a knotted rubberband. Proving that a given knot diagram can be untangled (that is, is a trivial knot, called an unknot) is one of the most famous problems of knot theory. For a small knot diagram, one can try to find a sequence of untangling moves explicitly, but for a larger knot diagram producing such a proof is difficult, and the produced proofs are hard to inspect and understand. Advanced approaches use algebra, with an advantage that since the proofs are algebraic, a computer can be used to produce the proofs, and, therefore, a proof can be produced even for large knot diagrams. However, such produced proofs are not easy to read and, for larger diagrams, not likely to be human readable at all. We propose a new approach combining advantages of these: the proofs are algebraic and can be produced by a computer, whilst each part of the proof can be represented as a reasonably small knot-like diagram (a new representation as a labeled tangle diagram), which can be easily inspected by a human for the purposes of checking the proof and finding out interesting facts about the knot diagram.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
In the implementation presented in Sect. 6 we did not use word reversion because, although reversing a word may make a proof shorter, it is not easy to implement it in the prover software we used.
 
2
Another approach that we tested (as presented in Sect. 6) is simply to place two tangle diagrams next to each other without connecting them by an arc; this corresponds, in terms of labelling words, to concatenating the words.
 
3
System used in experiments: Intel(R) Core(TM) i7-4790 CPU 3.60 Ghz, RAM 32 GB, Windows 7 Enterprise.
 
Literatur
1.
Zurück zum Zitat Burde, G., Heusener, M., Zieschang, H.: Knots. De Gruyter (2013) Burde, G., Heusener, M., Zieschang, H.: Knots. De Gruyter (2013)
2.
3.
Zurück zum Zitat Dynnikov, I.A.: Three-page approach to knot theory. Universal semigroup. Funct. Anal. Appl. 34(1), 24–32 (2000)MathSciNetCrossRef Dynnikov, I.A.: Three-page approach to knot theory. Universal semigroup. Funct. Anal. Appl. 34(1), 24–32 (2000)MathSciNetCrossRef
6.
Zurück zum Zitat Gilbert, N.D., Porter, T.: Knots and Surfaces. Oxford University Press, Oxford (1994)MATH Gilbert, N.D., Porter, T.: Knots and Surfaces. Oxford University Press, Oxford (1994)MATH
12.
Zurück zum Zitat Livingston, C.: Knot Theory, vol. 24. Cambridge University Press, Cambridge (1993)MATH Livingston, C.: Knot Theory, vol. 24. Cambridge University Press, Cambridge (1993)MATH
15.
Zurück zum Zitat Morgan, J.W., Bass, H. (eds.): The Smith Conjecture. Elsevier, New York (1984)MATH Morgan, J.W., Bass, H. (eds.): The Smith Conjecture. Elsevier, New York (1984)MATH
19.
Zurück zum Zitat Vernitski, A.: Describing semigroups with defining relations of the form xy = yz and yx = zy and connections with knot theory. Semigroup Forum 95(1), 66–82 (2017)MathSciNetCrossRef Vernitski, A.: Describing semigroups with defining relations of the form xy = yz and yx = zy and connections with knot theory. Semigroup Forum 95(1), 66–82 (2017)MathSciNetCrossRef
20.
Zurück zum Zitat Winker, S.K.: Quandles, knot invariants, and the n-fold branched cover. Ph.D. thesis, University of Illinois at Chicago (1984) Winker, S.K.: Quandles, knot invariants, and the n-fold branched cover. Ph.D. thesis, University of Illinois at Chicago (1984)
Metadaten
Titel
Visual Algebraic Proofs for Unknot Detection
verfasst von
Andrew Fish
Alexei Lisitsa
Alexei Vernitski
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-91376-6_12

Neuer Inhalt