Showing cs.CCShow all
4 papers · 1 filter
cs.CC2019
LIKE Patterns and Complexity
Holger Petersen
We investigate the expressive power and complexity questions for the LIKE operator in SQL.
cs.CC2019
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…
cs.CC2015
An NL-Complete Puzzle
Holger Petersen
We investigate the complexity of a puzzle that turns out to be NL-complete.
cs.CC2012
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…