2 citations · 5 across the 14 of their papers we have counts for
17 papers
LIKE Patterns and Complexity
Holger Petersen
We investigate the expressive power and complexity questions for the LIKE operator in SQL.
Some Remarks on Real-Time Turing Machines
Holger Petersen
The power of real-time Turing machines using sublinear space is investigated. In contrast to a claim appearing in the literature, such machines can accept non-regular languages, ev…
Busy Beaver Scores and Alphabet Size
Holger Petersen
We investigate the Busy Beaver Game introduced by Rado (1962) generalized to non-binary alphabets. Harland (2016) conjectured that activity (number of steps) and productivity (numb…
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.
Counting Ones Without Broadword Operations
Holger Petersen
A lower time bound for counting the number of ones in a binary input word of length is presented, where is the number of ones. The operations…
The Complexity of Some Combinatorial Puzzles
Holger Petersen
We show that the decision versions of the puzzles Knossos and The Hour-Glass are complete for NP.