Paper Info
Title
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′ such that the number of strings of length n in L and L′ 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 NPDA's, unambiguous NPDA's with no reversal-bound, and other models.
Year
DOI
Venue
2019
10.1016/j.tcs.2018.11.021
Theoretical Computer Science
Keywords
Field
DocType
Counting functions,Finite automata,Full trios,Context-free languages
Discrete mathematics,Nondeterministic algorithm,Deterministic pushdown automaton,Automaton,Decidability,Turing machine,Regular language,Mathematics,Special case,Undecidable problem
Journal
Volume
ISSN
Citations 
777
0304-3975
0
PageRank 
References 
Authors
0.34
20
3
Name
Order
Citations
PageRank
Oscar H. Ibarra13235741.44
Ian McQuillan29724.72
bala ravikumar326228.23