Journal article

Publication year: 2021

Pages: 121-136

Journal: Theoretical Computer Science

Volume number: 870

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2021.01.032

Publisher: Elsevier

Abstract: 
The model of deterministic input-driven multi-counter automata is introduced and studied. On such devices, the input letters uniquely determine the operations on the underlying data structure that is consisting of multiple counters. We study the computational power of the resulting language families and compare them with known language families inside the Chomsky hierarchy. In addition, it is possible to prove a proper counter hierarchy depending on the alphabet size. This means that any input alphabet induces an upper bound which depends on the alphabet size only, such that k + 1counters are more powerful than kcounters as long as kis less than this bound. The hierarchy interestingly collapses at the level of the bound. Furthermore, we investigate the closure properties of the language families. For input-driven multi-counter automata with 0 or 1counter, we discuss the computational complexity of their decidable problems. For k >= 2counters, the decidability problems of emptiness, finiteness, universality, inclusion, equivalence, regularity, and context-freeness are shown to be non-semidecidable. Finally, we study descriptional complexity aspects of input-driven multi-counter automata. It is shown that a nondeterministic device can be determinized and that 2(n)- 1is a necessary and sufficient blow-up in the number of states for the determinization. For the operational state complexity of deterministic input-driven multi-counter automata under Boolean operations, tight bounds on the number of states are established. Finally, it turns out that the size trade-offs between deterministic input-driven multi-counter automata with k + 1and kcounters are non-recursive, that is, they are not bounded by any recursive function. (C) 2021 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M., Malcher, A. and Wendlandt, M. (2021) Input-driven multi-counter automata, Theoretical Computer Science, 870, pp. 121-136. https://doi.org/10.1016/j.tcs.2021.01.032

APA Citation style: Kutrib, M., Malcher, A., & Wendlandt, M. (2021). Input-driven multi-counter automata. Theoretical Computer Science. 870, 121-136. https://doi.org/10.1016/j.tcs.2021.01.032