Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kari, J., Niemi, V.: Morphic Images of Gauss Codes. In: Developments in Language Theory, pp. 144–156 (1993)
Abramsky, S.: Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics. Mathematics of Quantum Computation and Quantum Technology (2007)
Freivalds, R.: Knot Theory, Jones Polynomial and Quantum Computing. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 15–25. Springer, Heidelberg (2005)
Lomonaco Jr., S., Kauffman, L.: Topological Quantum Computing and the Jones Polynomial. Arxiv Preprint Quant-ph/ 0605004 (2006)
Hass, J., Lagarias, J., Pippenger, N.: The computational complexity of knot and link problems. Journal of the ACM (JACM) 46(2), 185–211 (1999)
Kaminski, M., Francez, N.: Finite-memory automata. In: Proceedings of 31st Annual Symposium on Foundations of Computer Science, pp. 683–688 (1990)
Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Transactions on Computational Logic (TOCL) 5(3), 403–435 (2004)
Kurlin, V.: Gauss phrases realizable by classical links. Arxiv Preprint Math. GT/ 0610929 (2006)
David, C.: Mots et données infinies. Master’s thesis, LIAFA (2004)
Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. In: LICS, vol. 6, pp. 17–26 (2006)
Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. Journal of Computer and System Sciences 66(1), 66–97 (2003)
Bjorklund, H., Schwentick, T.: On Notions of Regularity for Data Languages. In: Csuhaj-Varjú, E., Ésik, Z. (eds.) FCT 2007. LNCS, vol. 4639, pp. 88–99. Springer, Heidelberg (2007)
Kauffman, L.: Virtual knot theory. Arxiv Preprint Math. GT/ 9811028 (1998)
Cairns, G., Elton, D.: The planarity problem for signed Gauss words. Journal of Knot Theory and its Ramifications 2(4), 359–367 (1993)
Cairns, G., Elton, D.: The Planarity Problem II. Journal of Knot Theory and its Ramifications 5, 137–144 (1996)
Carter, J.: Classifying immersed curves. Proc. Amer. Math. Soc. 111, 281–287 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lisitsa, A., Potapov, I., Saleh, R. (2009). Automata on Gauss Words. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-00982-2_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00981-5
Online ISBN: 978-3-642-00982-2
eBook Packages: Computer ScienceComputer Science (R0)