{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T10:04:24Z","timestamp":1695117864949},"reference-count":26,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[2005,11,1]],"date-time":"2005-11-01T00:00:00Z","timestamp":1130803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":2815,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2005,11]]},"DOI":"10.1016\/j.tcs.2005.07.024","type":"journal-article","created":{"date-parts":[[2005,8,25]],"date-time":"2005-08-25T11:29:37Z","timestamp":1124969377000},"page":"473-504","source":"Crossref","is-referenced-by-count":3,"title":["Sublogarithmic ambiguity"],"prefix":"10.1016","volume":"345","author":[{"given":"Klaus","family":"Wich","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2005.07.024_bib1","series-title":"The Theory of Parsing, Translation, and Compiling, Vol. I","author":"Aho","year":"1972"},{"key":"10.1016\/j.tcs.2005.07.024_bib2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","article-title":"Reversal-bounded multipushdown machines","volume":"8","author":"Baker","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.tcs.2005.07.024_bib3","series-title":"Transductions and Context-Free Languages","author":"Berstel","year":"1979"},{"key":"10.1016\/j.tcs.2005.07.024_bib4","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0304-3975(02)00892-7","article-title":"On the number of occurrences of a symbol in words of regular languages","volume":"302","author":"Bertoni","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2005.07.024_bib5","series-title":"The Book of Traces","article-title":"Counting techniques for inclusion","author":"Bertoni","year":"1995"},{"key":"10.1016\/j.tcs.2005.07.024_bib6","doi-asserted-by":"crossref","unstructured":"A. Bertoni, M. Goldwurm, M. Santini, Random generation and approximate counting of ambiguously described combinatorial structures, in: H. Reichel, S. Tison (Eds.), Proc. STACS 2000, Lecture Notes in Computer Science, Vol. 1770, Springer, Berlin, Heidelberg, New York, 2000, pp. 567\u2013580.","DOI":"10.1007\/3-540-46541-3_47"},{"key":"10.1016\/j.tcs.2005.07.024_bib7","series-title":"Automata, Languages and Programming","first-page":"377","article-title":"Un langage non ambigu dont le carr\u00e9 est d\u2019ambiguit\u00e9 non born\u00e9e","author":"Crestin","year":"1973"},{"key":"10.1016\/j.tcs.2005.07.024_bib8","unstructured":"J.C. Earley, An efficient context-free parsing algorithm, Ph.D. Thesis, Carnegie-Mellon University, 1968."},{"key":"10.1016\/j.tcs.2005.07.024_bib9","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/321386.321403","article-title":"One-way stack automata","volume":"14","author":"Ginsburg","year":"1967","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.tcs.2005.07.024_bib10","series-title":"Introduction to Formal Language Theory","author":"Harrison","year":"1978"},{"key":"10.1016\/j.tcs.2005.07.024_bib11","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/j.tcs.2005.07.024_bib12","series-title":"Handbook of Formal Languages, Vol. 1","first-page":"609","article-title":"Semirings and formal power series","author":"Kuich","year":"1997"},{"key":"10.1016\/j.tcs.2005.07.024_bib13","unstructured":"H. Maurer, The existence of context-free languages which are inherently ambiguous of any degree, Research Series, Department of Mathematics, University of Calgary, 1968."},{"key":"10.1016\/j.tcs.2005.07.024_bib14","unstructured":"M. Naji, Grad der Mehrdeutigkeit kontextfreier Grammatiken und Sprachen, diplomarbeit, FB Informatik, Johann-Wolfgang-Goethe-Universit\u00e4t, 1998."},{"issue":"3","key":"10.1016\/j.tcs.2005.07.024_bib15","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01694004","article-title":"A helpful result for proving inherent ambiguity","volume":"2","author":"Ogden","year":"1968","journal-title":"Math. Systems Theory"},{"key":"10.1016\/j.tcs.2005.07.024_bib16","unstructured":"R.J. Parikh, Language generating devices, in: Quarterly Progress Report, Vol. 60, Research Laboratory of Electronics, MIT, 1961, pp. 199\u2013212."},{"key":"10.1016\/j.tcs.2005.07.024_bib17","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","article-title":"On context-free languages","volume":"13","author":"Parikh","year":"1966","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.tcs.2005.07.024_bib18","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0020-0190(92)90212-E","article-title":"Observations on log(n) time parallel recognition of unambiguous cfl's","volume":"44","author":"Rossmanith","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.tcs.2005.07.024_bib19","series-title":"Automata Theoretic Aspects of Formal Power Series","author":"Salomaa","year":"1978"},{"key":"10.1016\/j.tcs.2005.07.024_bib20","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0019-9958(71)90455-4","article-title":"Some inherently ambiguous context-free languages","volume":"18","author":"Shamir","year":"1971","journal-title":"Inform. and Control"},{"key":"10.1016\/j.tcs.2005.07.024_bib21","series-title":"Proc. DLT, 1999","first-page":"125","article-title":"Exponential ambiguity of context-free grammars","author":"Wich","year":"2000"},{"key":"10.1016\/j.tcs.2005.07.024_bib22","doi-asserted-by":"crossref","unstructured":"K. Wich, Sublinear ambiguity, in: M. Nielsen, B. Rovan (Eds.), Proc. MFCS 2000, Lecture Notes in Computer Science, Vol. 1893, Springer, Berlin, Heidelberg, New York, 2000, pp. 690\u2013698.","DOI":"10.1007\/3-540-44612-5_64"},{"key":"10.1016\/j.tcs.2005.07.024_bib23","doi-asserted-by":"crossref","unstructured":"K. Wich, Characterization of context-free languages with polynomially bounded ambiguity, in: J. Sgall, A. Pultr, P. Kolman (Eds.), Proc. MFCS 2001, Mari\u00e1nsk\u00e9 L\u00e1zn\u011b, (Czech Republic), Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, Heidelberg, New York, 2001, pp. 703\u2013714.","DOI":"10.1007\/3-540-44683-4_61"},{"key":"10.1016\/j.tcs.2005.07.024_bib24","doi-asserted-by":"crossref","unstructured":"K. Wich, Universal inherence of cycle-free context-free ambiguity functions, in: P. Widmayer, et al. (Eds.), Proc. ICALP 2002, Lecture Notes in Computer Science, Vol. 2380, Springer, Berlin, Heidelberg, New York, 2002, pp. 669\u2013680.","DOI":"10.1007\/3-540-45465-9_57"},{"key":"10.1016\/j.tcs.2005.07.024_bib25","doi-asserted-by":"crossref","unstructured":"K. Wich, Sublogarithmic ambiguity, in: J. Fiala, V. Koubek, J. Kratochv\u00edl (Eds.), Proc. MFCS 2004, Lecture Notes in Computer Science, Vol. 3153, Springer, Berlin, Heidelberg, New York, 2004, pp. 794\u2013806.","DOI":"10.1007\/978-3-540-28629-5_62"},{"key":"10.1016\/j.tcs.2005.07.024_bib26","unstructured":"K. Wich, Ambiguity functions of context-free grammars and languages, Ph.D. Thesis, Universit\u00e4t Stuttgart, ftp:\/\/ftp.informatik.uni-stuttgart.de\/pub\/library\/ncstrl.ustuttgart_fi\/DIS-2005-01\/DIS-2005-01.pdf"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750500407X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750500407X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T10:36:28Z","timestamp":1552905388000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750500407X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":26,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["S030439750500407X"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2005.07.024","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2005,11]]}}}