Two-Way Counter Machines and Diophantine
โ
Gurari, Eitan M.; Ibarra, Oscar H.
๐
Article
๐
1982
๐
Association for Computing Machinery
๐
English
โ 548 KB
Let Q be the class of determmistlc two-way l-counter machines accepting only bounded languages Each machine m Q has the property that m every accepting computation, the counter makes at most a fixed number of reversals It is shown that the emptiness problem for Q is decidable. When the counter is un