{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:20:01Z","timestamp":1777105201894,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["414325841"],"award-info":[{"award-number":["414325841"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["EQUUS ANR-19-CE48-0019"],"award-info":[{"award-number":["EQUUS ANR-19-CE48-0019"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>Motivated by recent connections to factorised databases, we analyse the efficiency of representations by context free grammars (CFGs). Concretely, we prove a recent conjecture by Kimelfeld, Martens, and Niewerth (ICDT 2025), that for finite languages representations by general CFGs can be doubly-exponentially smaller than those by unambiguous CFGs. To do so, we show the first exponential lower bounds for representation by unambiguous CFGs of a finite language that can efficiently be represented by ambiguous CFGs. Our proof first reduces the problem to proving a lower bound in a non-standard model of communication complexity. Then, we argue similarly in spirit to a recent discrepancy argument to show the required communication complexity lower bound. Our result also implies that a finite language may admit an exponentially smaller representation as a nondeterministic finite automaton than as an unambiguous CFG.<\/jats:p>","DOI":"10.1145\/3725225","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-19","source":"Crossref","is-referenced-by-count":1,"title":["A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1386-8784","authenticated-orcid":false,"given":"Stefan","family":"Mengel","sequence":"first","affiliation":[{"name":"Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2422-9435","authenticated-orcid":false,"given":"Harry","family":"Vinall-Smeeth","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Ilmenau, Ilmenau, Th\u00fcringen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.111"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3685980.3685982"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526232"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_6_1","first-page":"1008","volume-title":"Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016","author":"Bova Simone","year":"2016","unstructured":"Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Knowledge compilation meets communication complexity. In Subbarao Kambhampati, editor, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9--15 July 2016, pages 1008-1014. IJCAI\/AAAI Press, 2016. URL: http:\/\/www.ijcai.org\/Abstract\/16\/147."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(81)90044-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.25596\/jalc-2004--189"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020--10013-w"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019--9958(59)90362--6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--19225--3_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.11.10.57"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.05.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.06.006"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.126"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--94631--3_13"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850665"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2309.11663"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651141"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802208"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2022.19"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.7"},{"key":"e_1_2_1_26_1","series-title":"AAAI Technical Report","volume-title":"Beyond NP, Papers from the 2016 AAAI Workshop","author":"Olteanu Dan","year":"2016","unstructured":"Dan Olteanu. Factorized databases: A knowledge compilation perspective. In Adnan Darwiche, editor, Beyond NP, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA, February 12, 2016, volume WS-16-05 of AAAI Technical Report. AAAI Press, 2016. URL: http:\/\/www.aaai.org\/ocs\/index.php\/WS\/AAAIW16\/paper\/view\/12638."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3635138.3654763"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108671644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.138"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304--3975(02)00568--6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458325"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526069"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524158"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206039"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--44522--8_3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891587"},{"key":"e_1_2_1_41_1","volume-title":"Introduction to the theory of computation","author":"Sipser Michael","year":"1997","unstructured":"Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2024\/398"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841161"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:17:43Z","timestamp":1755904663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725225"],"URL":"https:\/\/doi.org\/10.1145\/3725225","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}