Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21254-3_29 | LATA |
Keywords | Field | DocType |
gauss word,infinite alphabet,logspace computability,logspace bounded classical computation,deterministic register automaton,generic result,finite alphabet,unsigned gauss word,deterministic logarithmic space,automata working,classical logarithmic space complexity | Discrete mathematics,Gauss,Combinatorics,Planarity testing,Automaton,Computability,Knot (unit),Mathematics,Logarithmic space,Computation,Bounded function | Conference |
Volume | ISSN | Citations |
6638 | 0302-9743 | 1 |
PageRank | References | Authors |
0.39 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexei Lisitsa | 1 | 272 | 45.94 |
| Igor Potapov | 2 | 319 | 38.31 |
| Rafiq Saleh | 3 | 3 | 1.46 |