Zerotesting bounded one-way multicounter machines. (English) Zbl 0619.68048
One-way multicounter machines with bounds on the number of counter reversals and zero-tests in accepting computations are studied. The bounds are considered as functions of the length of the input word. The first lower bound and some hierarchy results for nonconstant bounds on the number of zero-tests are obtained. Futher results relate the reversal complexity and zero-test complexity to nondeterminism, time, and the number of counters as additional complexity parameters. It is proved that quasirealtime, determinism and one counter with one zero-test can be sufficient for the recognition of a specific language, for which nondeterminism, unbounded time, arbitrary large number of counters and o(n) reversals do not suffice.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
References:
| [1] | T. Chan: Reversal complexity of counter machines. Proc. IEEE Symposium on Theory of Computiong 1981, IEEE New York, pp. 146-157. |
| [2] | P. Ďuriš, Z. Galil: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store. Inform. and Control 54 (1982), 3, 217-227. · Zbl 0523.68037 |
| [3] | P. Ďuriš, J. Hromkovič: One-way simple multihead finite automata are not closed under concatenation. Theoret. Comput. Sci. 27 (1983), 121-125. |
| [4] | S. Ginsburg: Algebraic and Automata - Theoretic Properties of Formal Languages. North-Holland Publ. Comp., Amsterdam 1975. · Zbl 0325.68002 |
| [5] | S. A. Greibach: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci 7 (1978), 311-324. · Zbl 0389.68030 · doi:10.1016/0304-3975(78)90020-8 |
| [6] | M. Hack: Petri Net Languages, Computation Structures. Group Memo 124, Project MAC, MIT, 1975. |
| [7] | J. Hromkovič: Closure properties of the family of languages reoginized by one-way two-head deterministic finite state automata. Mathematical Foundation of Computer Science 1981 - Proc. 16th Symposium, Štrbské pleso, Czechoslovakia, August 31 - September 4, 1981 (J. Gruska, M. Chytil.(Lecture Notes in Computer Science 118.) Springer-Velag Berlin - Heidelberg - New York 1981, pp. 304-313. |
| [8] | J. Hromkovič: Hierarchy of reversal and zerotesting bounded multicounter machines. Mathematicl Foundations of Computer Science 1984 - Proc. 11th Symposium, Prague, Czechoslovakia, September 3-7, 1984 (M. P. Chytil, V. Koubek.(Lecture Notes in Computer Science 176.) Springer-Velag Berlin - Heidelberg - New York - Tokoy 1984, pp. 312-321. · Zbl 0582.68049 |
| [9] | J. Hromkovič: Reversal bounded multicounter machines. Computers and Artificial Intelligence 4 (1985), 4, 361-366. · Zbl 0579.68032 |
| [10] | J. Hromkovič: Hierarchy of reversal bounded one-way multicounter machines. Kybernetika 22 (1986), 2, 200-206. · Zbl 0607.68034 |
| [11] | O. H. Ibarra: REcersal bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach. 25 (1978), 116-133. · Zbl 0365.68059 · doi:10.1145/322047.322058 |
| [12] | M. Jantzen: On zerotesting-bounded multicounter machines. Proc. 4th GI Conference, 1979, Springer-Velag Berlin - Heidelberg - New York , pp. 158-169. · Zbl 0411.68070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
