5 papers
A Note on Nested String Replacements
Holger Petersen
We investigate the number of nested string replacements required to reduce a string of identical characters to one character.
An NL-Complete Puzzle
Holger Petersen
We investigate the complexity of a puzzle that turns out to be NL-complete.
A Non-Oblivious Reduction of Counting Ones to Multiplication
Holger Petersen
An algorithm counting the number of ones in a binary word is presented running in time where is the number of ones. The operations available include bit-wise lo…
Simpler, faster and shorter labels for distances in graphs
Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen +1
We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to deter…
A Note on Kolmogorov-Uspensky Machines
Holger Petersen
Solving an open problem stated by Shvachko, it is shown that a language which is not real-time recognizable by some variants of pointer machines can be accepted by a Kolmogorov-Usp…