Paper Info
Title
On Counting Functions of Languages.
Abstract
We study counting-regular languages—these are languages L for which there is a regular language (Lu0027) such that the number of strings of length n in L and (Lu0027) are the same for all n. Our main result is that the languages accepted by the class of one-way unambiguous, reversal-bounded pushdown automata ((textsf {PDA})’s) are counting-regular. This generalizes an old result of Baron and Kuich that such languages have rational generating functions. We show that this result is the best possible in the sense that the claim does not hold for either 2-ambiguous (textsf {PDA})’s, unambiguous (textsf {PDA})’s with no reversal-bound, and other generalizations. We provide a number of examples of languages that are (and are not) counting-regular. We study closure properties of the class of context-free languages that are counting-regular. We also show the undecidability of counting-regularity of (textsf {PDA})’s. The undecidability is shown to hold for even the subclass of 2-ambiguous (textsf {PDA})’s which make only one reversal on the stack.
Year
Venue
Field
2018
DLT
Generating function,Discrete mathematics,Combinatorics,Generalization,Computer science,Pushdown automaton,Regular language
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
6
3
Name
Order
Citations
PageRank
Oscar H. Ibarra1650101.57
Ian McQuillan29724.72
bala ravikumar326228.23