International Journal of Foundations of Computer Science 19(3), pp. 717-727.
ISSN/ISBN: 0129-0541 DOI: 10.1142/S0129054108005905
Abstract: For a string w ∈ {0,1, 2,..., d-1}*, let val_{d}(w) denote the integer whose base d representation is the string w and let MSD_{d}(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and KarhumÃ¤ki [9] studied the problem of computing the leading digit in the ternary representation of 2^{x} ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of A^{B} for given inputs A and B. In this paper, we study this problem from a formal language point of view. Formally, we consider the language L_{b,d,j} = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSD_{b}(d^{valb(w)})) = j} (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs.
Bibtex:
@article {MR2417964,
AUTHOR = {Ravikumar, Bala},
TITLE = {The {B}enford-{N}ewcomb distribution and unambiguous
context-free languages},
JOURNAL = {Internat. J. Found. Comput. Sci.},
FJOURNAL = {International Journal of Foundations of Computer Science},
VOLUME = {19},
YEAR = {2008},
NUMBER = {3},
PAGES = {717--727},
ISSN = {0129-0541},
MRCLASS = {68Q42 (68Q25 68Q45)},
MRNUMBER = {2417964 (2009h:68068)},
DOI = {10.1142/S0129054108005905},
URL = {http://dx.doi.org/10.1142/S0129054108005905},
}
Reference Type: Journal Article
Subject Area(s): Computer Science