On counting functions and slenderness of languages (Q2422037)

The counting function \(f_L(n)\) of a language \(L\) is equal to the number of strings of length \(n\) in \(L\). A language \(L\) is counting-regular if there is a regular language \(L'\) with the same counting function as \(L\), and strongly counting-regular if for any regular language \(L_1\), the intersection \(L\cap L_1\) is counting regular. It was already known that all languages accepted by one-way deterministic counter machines with reversal-bounded counter are counting-regular, but there are also arbitrarily complex languages (even non-recursively enumerable ones) that are counting-regular. Therefore, it is of interest to restrict the scope of investigations to (subclasses of) context-free languages. The main result of the paper states that the languages accepted by unambiguous nondeterministic Turing machines with one-way read-only input tape and a reversal-bounded worktape are strongly counting-regular. The other results show that bounded languages in any semilinear trio (a family of semilinear languages closed under \(\epsilon\)-free homomorphism, inverse homomorphism, and intersection with regular languages) are counting-regular. A section is devoted to different types of closure properties; for example, counting-regular languages (and counting-regular context-free languages) are not closed under union, intersection with regular languages, concatenation with regular languages, or right and left quotient with a symbol. Concerning decidability questions, counting-regularity is undecidable for languages of (1) 2-ambiguous nondeterministic pushdown automata which make only one reversal on the stack, (2) nondeterministic one-counter machines that make only one reversal on the counter, and (3) 2-ambiguous nondeterministic one-counter machines. In the last two sections decidability properties for slender languages are discussed (a language is slender if its counting function is bounded by a given \(k\) for all \(n\)). It is shown that for any semilinear full trio (where certain closure properties are constructive), \(k\)-slenderness and the containment or equality of two \(k\)-slender languages are decidable. It is also shown that every slender language in such a family is counting-regular. Most of these results are general enough to also cover families that are not semilinear if they satisfy certain other closure properties (such families include, for example, the languages generated by matrix grammars).