@inproceedings{10.1007/978-3-642-21254-3_29,
    Abstract = {In this paper we investigate the complexity of planarity of knot diagrams encoded by Gauss words, both in terms of recognition by automata over infinite alphabets and in terms of classical logarithmic space complexity. As the main result, we show that recognition of planarity of unsigned Gauss words can be done in deterministic logarithmic space and by deterministic register automata. We also demonstrate generic results on the mutual simulations between logspace bounded classical computations (over finite alphabets) and register automata working over infinite alphabets.},
    Address = {Berlin, Heidelberg},
    Author = {Lisitsa, Alexei and Potapov, Igor and Saleh, Rafiq},
    BookTitle = {Language and Automata Theory and Applications},
    Editor = {Dediu, Adrian-Horia and Inenaga, Shunsuke and Mart{\'\i}n-Vide, Carlos},
    File = {Planarity of Knots, Register Automata and LogSpace Computability - Lisitsa2011\_Chapter\_PlanarityOfKnotsRegisterAutoma - d - d.pdf},
    ISBN = {978-3-642-21254-3},
    Pages = {366--377},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Planarity of Knots, Register Automata and LogSpace Computability},
    Year = {2011},
    date-added = {2021-03-29 21:14:22 +0200},
    date-modified = {2021-03-29 21:14:22 +0200},
    doi = {10.1007/978-3-642-21254-3_29}
}

@inproceedings{10.1007/978-3-642-21254-3_29, Abstract = {In this paper we investigate the complexity of planarity of knot diagrams encoded by Gauss words, both in terms of recognition by automata over infinite alphabets and in terms of classical logarithmic space complexity. As the main result, we show that recognition of planarity of unsigned Gauss words can be done in deterministic logarithmic space and by deterministic register automata. We also demonstrate generic results on the mutual simulations between logspace bounded classical computations (over finite alphabets) and register automata working over infinite alphabets.}, Address = {Berlin, Heidelberg}, Author = {Lisitsa, Alexei and Potapov, Igor and Saleh, Rafiq}, BookTitle = {Language and Automata Theory and Applications}, Editor = {Dediu, Adrian-Horia and Inenaga, Shunsuke and Mart{\'\i}n-Vide, Carlos}, File = {Planarity of Knots, Register Automata and LogSpace Computability - Lisitsa2011_Chapter_PlanarityOfKnotsRegisterAutoma - d - d.pdf}, ISBN = {978-3-642-21254-3}, Pages = {366--377}, Publisher = {Springer Berlin Heidelberg}, Title = {Planarity of Knots, Register Automata and LogSpace Computability}, Year = {2011}, date-added = {2021-03-29 21:14:22 +0200}, date-modified = {2021-03-29 21:14:22 +0200}, doi = {10.1007/978-3-642-21254-3_29} }