{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T06:16:29Z","timestamp":1784873789582,"version":"3.55.0"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p> A language [Formula: see text] is said to be dense if every word in the universe is an infix of some word in [Formula: see text]. This notion has been generalized from the infix operation to arbitrary word operations [Formula: see text] in place of the infix operation ([Formula: see text]-dense, with infix-dense being the standard notion of dense). It is shown here that it is decidable, for a language [Formula: see text] accepted by a one-way nondeterministic reversal-bounded pushdown automaton, whether [Formula: see text] is infix-dense. However, it becomes undecidable for both deterministic pushdown automata (with no reversal-bound), and for nondeterministic one-counter automata. When examining suffix-density, it is undecidable for more restricted families such as deterministic one-counter automata that make three reversals on the counter, but it is decidable with less reversals. Other decidability results are also presented on dense languages, and contrasted with a marked version called [Formula: see text]-marked-density. Also, new languages are demonstrated to be outside various deterministic language families after applying different deletion operations from smaller families. Lastly, bounded-dense languages are defined and examined. <\/jats:p>","DOI":"10.1142\/s0129054118400051","type":"journal-article","created":{"date-parts":[[2018,4,11]],"date-time":"2018-04-11T07:34:45Z","timestamp":1523432085000},"page":"233-250","source":"Crossref","is-referenced-by-count":5,"title":["On the Density of Context-Free and Counter Languages"],"prefix":"10.1142","volume":"29","author":[{"given":"Joey","family":"Eremondi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oscar H.","family":"Ibarra","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2018,4,11]]},"reference":[{"key":"S0129054118400051BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"S0129054118400051BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"S0129054118400051BIB003","volume-title":"Theory of Codes","author":"Berstel J.","year":"1985"},{"key":"S0129054118400051BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.04.002"},{"key":"S0129054118400051BIB006","volume-title":"The Mathematical Theory of Context-Free Languages","author":"Ginsburg S.","year":"1966"},{"key":"S0129054118400051BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80019-0"},{"key":"S0129054118400051BIB008","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054118400051BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.034"},{"key":"S0129054118400051BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"S0129054118400051BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400539"},{"key":"S0129054118400051BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57163-9_3"},{"key":"S0129054118400051BIB014","doi-asserted-by":"publisher","DOI":"10.1080\/00207160108805105"},{"key":"S0129054118400051BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_8"},{"key":"S0129054118400051BIB016","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"S0129054118400051BIB017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"S0129054118400051BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00285-1"},{"key":"S0129054118400051BIB019","volume-title":"Free Monoids and Languages","author":"Shyr H. J.","year":"2001"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118400051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:27:31Z","timestamp":1565180851000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118400051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":17,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,4,11]]},"published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.1142\/S0129054118400051"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118400051","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}