2 papers
cs.CC2015
Efficient Computation by Three Counter Machines
Holger Petersen
We show that multiplication can be done in polynomial time on a three counter machine that receives its input as the contents of two counters. The technique is generalized to funct…
cs.FL2014
On Practical Regular Expressions
Holger Petersen
We report on simulation, hierarchy, and decidability results for Practical Regular Expressions (PRE), which may include back references in addition to the standard operations union…