Some Remarks on Lower Bounds for Queue Machines (Preliminary Report)
Holger Petersen · arXiv (Cornell University) · 2013
We first give an improved lower bound for the deterministic online simulation of tapes or pushdown stores by queues. Then we inspect some proofs in a classical work on queue machines in the area of Formal Languages and outline why a main argument in the proofs is incomplete. Based on descriptional complexity, we show the intuition behind the argument to be correct.