On counting functions and slenderness of languages

Abstract

We study counting-regular languages -- these are languages $L$ for which there is a regular language $L^{\prime }$ such that the number of strings of length $n$ in $L$ and $L^{\prime }$ are the same for all $n$. We show that the languages accepted by unambiguous nondeterministic Turing machines with a one-way read-only input tape and a reversal-bounded worktape are counting-regular. Many one-way acceptors are a special case of this model, such as reversal-bounded deterministic pushdown automata, reversal-bounded deterministic queue automata, and many others, and therefore all languages accepted by these models are counting-regular. This result is the best possible in the sense that the claim does not hold for either $2$-ambiguous PDA's, unambiguous PDA's with no reversal-bound, and other models. We also study closure properties of counting-regular languages, and we study decidability problems in regards to counting-regularity. For example, it is shown that the counting-regularity of even some restricted subclasses of PDA's is undecidable. Lastly, $k$-slender languages -- where there are at most $k$ words of any length -- are also studied. Amongst other results, it is shown that it is decidable whether a language in any semilinear full trio is $k$-slender.

Cited by in corpus (2)

• On Families of Full Trios Containing Counter Machine Languages
• Relationships Between Bounded Languages, Counter Machines, Finite-Index Grammars, Ambiguity, and Commutative Regularity