Automata on Gauss Words

摘要

In this paper we investigate the computational complexity of knot theoretic problems and show upper and lower bounds for planarity problem of signed-and unsigned knot diagrams represented by Gauss words. Due to the fact the number of crossing in knots is unbounded, the Gauss words of knot diagrams are strings over infinite (unbounded) alphabet. For establishing the lower and upper bounds on recognition of knot properties we study these problems in a context of automata models over infinite alphabet.