On Families of Full Trios Containing Counter Machine Languages
arXiv:2212.03791 · doi:10.1016/j.tcs.2019.09.045
Abstract
We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework.
28 pages, 1 figure
References in corpus (5)
- Insertion Operations on Deterministic Reversal-Bounded Counter Machines
- On the Density of Context-Free and Counter Languages
- On counting functions and slenderness of languages
- On Families of Full Trios Containing Counter Machine Languages
- Relationships Between Bounded Languages, Counter Machines, Finite-Index Grammars, Ambiguity, and Commutative Regularity