{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:25:13Z","timestamp":1648535113323},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> For a string w \u2208 {0,1, 2,\u2026, d-1}*, let val<jats:sub>d<\/jats:sub>(w) denote the integer whose base d representation is the string w and let MSD<jats:sub>d<\/jats:sub>(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\u00e4ki [9] studied the problem of computing the leading digit in the ternary representation of 2<jats:sup>x<\/jats:sup> 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<jats:sup>B<\/jats:sup> 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<jats:sub>b,d,j<\/jats:sub> = {w|w \u2208 {0,1, 2,\u2026, d-1}*, 1 \u2264 j \u2264 9, MSD<jats:sub>b<\/jats:sub>(d<jats:sup>val<jats:sub>b<\/jats:sub>(w)<\/jats:sup>)) = 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. <\/jats:p>","DOI":"10.1142\/s0129054108005905","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T10:27:20Z","timestamp":1212488840000},"page":"717-727","source":"Crossref","is-referenced-by-count":0,"title":["THE BENFORD-NEWCOMB DISTRIBUTION AND UNAMBIGUOUS CONTEXT-FREE LANGUAGES"],"prefix":"10.1142","volume":"19","author":[{"given":"BALA","family":"RAVIKUMAR","sequence":"first","affiliation":[{"name":"Department of Computer Science, Sonoma State University, Rohnert Park, CA 94928, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"197","volume":"457","author":"Berger A.","journal-title":"Trans. Amer. Math. Soc"},{"key":"rf3","volume-title":"Mathematics by Experiment","author":"Borwein J.","year":"2003"},{"key":"rf4","first-page":"72","author":"Diaconis P.","journal-title":"Annals of Probability"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0015-1"},{"key":"rf7","volume-title":"An introduction to the theory of numbers","author":"Hardy G. H.","year":"1979"},{"key":"rf8","volume-title":"Introduction to Automata, Formal Languages and Theory Computation","author":"Hopcroft J.","year":"1979"},{"key":"rf10","first-page":"887","volume":"123","author":"Hill T.","journal-title":"Proc. of the American Mathematical Society"},{"key":"rf11","first-page":"8","volume":"26","author":"Hill T.","journal-title":"Chance"},{"key":"rf12","first-page":"295","author":"Kemp R.","journal-title":"Acta Informatica"},{"key":"rf13","volume-title":"Uniform Distribution of Sequences","author":"Kuipers L.","year":"1974"},{"key":"rf14","volume-title":"The Art of Computer Programming, Volume 2: Semi-Numerical Algorithms","author":"Knuth D.","year":"1998"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.2307\/2319349"},{"key":"rf17","first-page":"131","volume":"105","author":"Ravikumar B.","journal-title":"Information Processing Letters"},{"key":"rf18","volume-title":"Elementary Number Theory and Its Applications","author":"Rosen K.","year":"2005"},{"key":"rf19","volume-title":"Cryptography Theory and Practice","author":"Stinson D.","year":"1995"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:33:38Z","timestamp":1565138018000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":15,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0129054108005905"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005905","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}