Showing 2019Show all
2 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…