{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:32:26Z","timestamp":1767929546540,"version":"3.49.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","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":[[2024,5,10]]},"abstract":"<jats:p>\n            Given a non-deterministic finite automaton (NFA) A with m states, and a natural number n (presented in unary), the #NFA problem asks to determine the size of the set L(A,n) of words of length n accepted by A. While the corresponding decision problem of checking the emptiness of L(A,n) is solvable in polynomial time, the #NFA problem is known to be #P-hard. Recently, the long-standing open question --- whether there is an FPRAS (fully polynomial time randomized approximation scheme) for #NFA --- was resolved by Arenas, Croquevielle, Jayaram, and Riveros in [ACJR19]. The authors demonstrated the existence of a fully polynomial randomized approximation scheme with a time complexity of ~O(m\n            <jats:sup>17<\/jats:sup>\n            n\n            <jats:sup>17<\/jats:sup>\n            \u2022 1\/\u03b5\n            <jats:sup>14<\/jats:sup>\n            \u2022 log (1\/\u03b4)), for a given tolerance \u03b5 and confidence parameter \u03b4.\n          <\/jats:p>\n          <jats:p>Given the prohibitively high time complexity in terms of each of the input parameters, and considering the widespread application of approximate counting (and sampling) in various tasks in Computer Science, a natural question arises: is there a faster FPRAS for #NFA that can pave the way for the practical implementation of approximate #NFA tools? In this work, we answer this question in the positive. We demonstrate that significant improvements in time complexity are achievable, and propose an FPRAS for #NFA that is more efficient in terms of both time and sample complexity.<\/jats:p>\n          <jats:p>\n            A key ingredient in the FPRAS due to Arenas, Croquevielle, Jayaram, and Riveros [ACJR19] is inter-reducibility of sampling and counting, which necessitates a closer look at the more informative measure --- the number of samples maintained for each pair of state q and length i &lt;= n. In particular, the scheme of [ACJR19] maintains O(m\n            <jats:sup>7<\/jats:sup>\n            \/n\n            <jats:sup>7<\/jats:sup>\n            \u03b5\n            <jats:sup>7<\/jats:sup>\n            ) samples per pair of state and length. In the FPRAS we propose, we systematically reduce the number of samples required for each state to be only poly-logarithmically dependent on m, with significantly less dependence on n and \u03b5, maintaining only ~O(n\n            <jats:sup>4<\/jats:sup>\n            \/\u03b5\n            <jats:sup>2<\/jats:sup>\n            ) samples per state. Consequently, our FPRAS runs in time ~O((m\n            <jats:sup>2<\/jats:sup>\n            n\n            <jats:sup>10<\/jats:sup>\n            + m\n            <jats:sup>3<\/jats:sup>\n            n\n            <jats:sup>6<\/jats:sup>\n            ) \u2022 1\/\u03b5\n            <jats:sup>4<\/jats:sup>\n            \u2022 log\n            <jats:sup>2<\/jats:sup>\n            (1\/\u03b4)). The FPRAS and its analysis use several novel insights. First, our FPRAS maintains a weaker invariant about the quality of the estimate of the number of samples for each state q and length i &lt;= n. Second, our FPRAS only requires that the distribution of the samples maintained is close to uniform distribution only in total variation distance (instead of maximum norm). We believe our insights may lead to further reductions in time complexity and thus open up a promising avenue for future work towards the practical implementation of tools for approximate #NFA.\n          <\/jats:p>","DOI":"10.1145\/3651613","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-22","source":"Crossref","is-referenced-by-count":3,"title":["A faster FPRAS for #NFA"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9423-5270","authenticated-orcid":false,"given":"Kuldeep S.","family":"Meel","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6204","authenticated-orcid":false,"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7610-0660","authenticated-orcid":false,"given":"Umang","family":"Mathur","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2024.15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319704"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477045"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950362"},{"key":"e_1_2_1_6_1","volume-title":"Music Technology meets Philosophy - From Digital Echos to Virtual Ethos: Joint Proceedings of the 40th International Computer Music Conference, ICMC. https:\/\/hdl.handle.net\/2027\/spo.bbp2372.2014.196","author":"Donz\u00e9 Alexandre","unstructured":"Alexandre Donz\u00e9, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel. 2014. Machine Improvisation with Formal Specifications. In Music Technology meets Philosophy - From Digital Echos to Virtual Ethos: Joint Proceedings of the 40th International Computer Music Conference, ICMC. https:\/\/hdl.handle.net\/2027\/spo.bbp2372.2014.196"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3330392"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2621"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460833.1460872"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(86)90174-X"},{"key":"e_1_2_1_11_1","volume-title":"Mahaney","author":"Kannan Sampath","year":"1995","unstructured":"Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. 1995. Counting and Random Generation of Strings in Regular Languages. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 551--557."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(85)90021--4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Axel Legay Beno\u00eet Delahaye and Saddek Bensalem. 2010. Statistical Model Checking: An Overview. In Runtime Verification. 122--135.","DOI":"10.1007\/978-3-642-16612-9_11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360606"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591281"},{"key":"e_1_2_1_16_1","volume-title":"Fuzzing: Brute Force Vulnerability Discovery","author":"Sutton Michael","year":"2007","unstructured":"Michael Sutton, Adam Greene, and Pedram Amini. 2007. Fuzzing: Brute Force Vulnerability Discovery. Addison-Wesley Professional."},{"key":"e_1_2_1_17_1","volume-title":"Meel","author":"van Bremen Timothy","year":"2023","unstructured":"Timothy van Bremen and Kuldeep S. Meel. 2023. Probabilistic Query Evaluation: The Combined FPRAS Landscape. In PODS. 339--347."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(93)90252-O"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651613","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:08Z","timestamp":1755898808000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651613"],"URL":"https:\/\/doi.org\/10.1145\/3651613","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}