View Complete Reference

Ravikumar, B (2008)

The Benford-Newcomb Distribution and Unambiguous Context-Free Languages

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 vald(w) denote the integer whose base d representation is the string w and let MSDd(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 2x 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 AB 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 Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(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