{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T04:41:01Z","timestamp":1648701661181},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> The density of a language is defined as the function d<jats:sub>L<\/jats:sub>(n) = |L \u2229 \u03a3<jats:sup>n<\/jats:sup>| and counts the number of words of a certain length accepted by L. The study of the density of regular and context-free languages has attracted some attention culminating in the fact that such languages are either sparse, when the density can be bounded by a polynomial, or dense otherwise. We show that for all nonambiguous context-free languages the number of accepted words of a given length n can also be computed recursively using a finite combination of the number of accepted words smaller than n, or [Formula: see text]. This extends an old result by Chomsky and provides us with a more expressive description and new insights into possible applications of the density function for such languages as well as possible characterizations of the density of higher languages. <\/jats:p>","DOI":"10.1142\/s179383091000084x","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T08:21:26Z","timestamp":1295252486000},"page":"505-514","source":"Crossref","is-referenced-by-count":0,"title":["ON THE DENSITY OF REGULAR AND CONTEXT-FREE LANGUAGES"],"prefix":"10.1142","volume":"02","author":[{"given":"MICHAEL","family":"HARTWIG","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, Multimedia University, Cyberjaya, Selangor 63100, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(58)90082-2"},{"key":"rf2","volume-title":"Introduction to Computer Theory","author":"Cohen D. I. A.","year":"1996"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00286-X"},{"key":"rf4","first-page":"219","author":"Eisman G.","journal-title":"ACSC"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90011-9"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00152-3"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"rf11","first-page":"494","author":"Szilard A.","journal-title":"MFCS"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091000084X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:15:56Z","timestamp":1565111756000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091000084X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":8,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S179383091000084X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091000084x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}