{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:25:40Z","timestamp":1790814340426,"version":"4.1.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID - Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]},{"name":"Fondecyt","award":["1191337"],"award-info":[{"award-number":["1191337"]}]},{"name":"ANID BECAS\/MAGISTER NACIONAL","award":["2017-22171763"],"award-info":[{"award-number":["2017-22171763"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>In this work, we study two simple yet general complexity classes, based on logspace Turing machines, that provide a unifying framework for efficient query evaluation in areas such as information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting, and uniform generation of solutions, and show that they have several desirable properties in this respect.<\/jats:p>\n          <jats:p>\n            Both complexity classes are defined in terms of non-deterministic logspace transducers (NL-transducers). For the first class, we consider the case of unambiguous NL-transducers, and we prove constant delay enumeration and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL-transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomial-time randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm (with preprocessing) for uniform generation. Remarkably, the key idea to prove these results is to show that the fundamental problem # NFA admits an FPRAS, where # NFA is the problem of counting the number of strings of length\n            <jats:italic>n<\/jats:italic>\n            (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be P-complete and, more precisely,\n            <jats:sc>SpanL<\/jats:sc>\n            -complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem and obtain as a welcome corollary that every function in\n            <jats:sc>SpanL<\/jats:sc>\n            admits an FPRAS.\n          <\/jats:p>","DOI":"10.1145\/3477045","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T17:40:31Z","timestamp":1635442831000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes"],"prefix":"10.1145","volume":"68","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica &amp; IMFD, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luis Alberto","family":"Croquevielle","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica &amp; IMFD, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajesh","family":"Jayaram","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica &amp; IMFD, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"42","article-title":"Data, responsibly (Dagstuhl seminar 16291)","volume":"6","author":"Abiteboul Serge","year":"2016","journal-title":"Dagstuhl Rep."},{"key":"e_1_2_1_2_1","volume-title":"Hopcroft","author":"Aho Alfred V.","year":"1974"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"A circuit-based approach to efficient enumeration","volume":"111","author":"Amarilli Antoine","year":"2017","journal-title":"Proceedings of ICALP."},{"key":"e_1_2_1_5_1","volume-title":"Connecting knowledge compilation classes and width parameters. CoRR abs\/1811.02944","author":"Amarilli Antoine","year":"2018"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005150"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.021"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_15_1","volume-title":"Constant delay algorithms for regular document spanners. arXiv preprint arXiv:1803.05277","author":"Florenzano Fernando","year":"2018"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"A logic for document spanners","volume":"13","author":"Freydenberger Dominik D.","year":"2017","journal-title":"Proceedings of ICDT."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2621"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/203610.203611","article-title":"The satanic notations: Counting classes beyond #P and other definitional adventures","volume":"26","author":"Hemaspaandra Lane A.","year":"1995","journal-title":"SIGACT News"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of SODA. 551\u2013557","author":"Kannan Sampath"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of FOCS. 56\u201364","author":"Richard"},{"key":"e_1_2_1_25_1","article-title":"The complexity of regular expressions and property paths in SPARQL","volume":"38","author":"Losemann Katja","year":"2013","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1039"},{"key":"e_1_2_1_30_1","volume-title":"Enumeration: Algorithms and complexity.","author":"Schmidt Johannes","year":"2009"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3477045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:47Z","timestamp":1750188647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3477045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3477045"],"URL":"https:\/\/doi.org\/10.1145\/3477045","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}