Abstract
This research explores the computational complexity of determining whether a knot diagram—represented as a text string called a "Gauss word"—can be drawn flat on a plane without non-standard intersections. By treating Gauss words as strings over an infinite alphabet, the authors prove that the planarity of signed knots can be recognized by deterministic two-way register automata, while unsigned knot planarity can be recognized by co-non-deterministic register automata. This work bridges knot theory and formal language theory, offering new theoretical bounds on the memory and computational power needed to parse topological structures.
Introduction: From Knots to Gauss Words
In mathematical knot theory, a knot is a closed loop embedded in 3D space. To study these objects, mathematicians project them onto a 2D plane, creating a diagram with "over" and "under" crossings. These diagrams can be encoded into discrete text strings known as Gauss words. Each crossing is assigned a unique label, and the word records the sequence of labels encountered as one traverses the loop, noting whether the path goes over (O) or under (U) at each point.
However, not every arbitrary sequence of over/under symbols corresponds to a valid, classical 2D knot projection. Some strings imply impossible geometry that requires "virtual" crossings—intersections that are not part of the knot's actual structure but are artifacts of an attempt to draw a non-planar graph in 2D. Determining whether a given Gauss word represents a valid, flat 2D projection is known as the planarity problem.
The Challenge of Infinite Alphabets
Because a knot can be made arbitrarily complex by adding trivial twists (Reidemeister moves), the number of unique crossings is unbounded. Therefore, Gauss words must be treated as strings over an infinite alphabet. While algorithmic solutions to the planarity problem exist, this paper addresses a theoretical gap: what is the inherent descriptional complexity of this problem? Specifically, what is the weakest theoretical computing machine (automaton) capable of solving it?
Methods: Register Automata
The authors tackle this problem using the framework of automata over infinite alphabets. They utilize Register Automata (RA): finite state machines equipped with a finite number of memory "registers" that can store and compare symbols from an infinite alphabet.
To solve the planarity problem, the authors simulate known topological algorithms within this framework:
- For signed Gauss words (where the orientation/sign of the crossing is known), they design a two-way Deterministic Register Automaton (DRA). This machine simulates a linear-time algorithm that traverses the "faces" of the knot to compute the Euler characteristic of its associated Carter surface.
- For unsigned Gauss words (lacking orientation data), they design a two-way Non-deterministic Register Automaton (NRA) to simulate the Cairns-Elton algorithm. This involves checking the parity of intersections in an "interlacement graph" derived from the word.
Key Insights and Results
The research provides several critical insights into the relationship between topology and formal languages:
- Signs Simplify Analysis: Having orientation data (signed Gauss words) significantly reduces the computational power required. A deterministic machine (DRA) can trace the geometric faces of the knot to verify planarity.
- Unsigned Words Require Guesswork: Without orientation data, checking planarity deterministically with finite memory is highly complex. However, checking for non-planarity is easier: a non-deterministic machine (NRA) can "guess" a closed path in the knot's interlacement graph and verify if it violates planarity rules.
- Complexity Bounds: The language of valid Gauss words can be recognized by 2-way DRA, but not by 1-way NRA. Signed planarity is recognizable by 2-way DRA, while unsigned planarity is recognizable by 2-way co-NRA (machines that accept a word if all non-deterministic paths reject its complement).
Conclusion and Future Work
This work provides a new lens on topology by mapping knot problems to formal language theory. The authors suggest applying this automata-based approach to even more complex knot problems, such as determining unknottedness or knot equivalence. They also propose exploring variants of "pebble automata" to establish even tighter upper bounds on the complexity of these topological puzzles.
Summary updated