#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorAlberto Croquevielle, Luis
dc.contributor.authorJayaram, Rajesh
dc.contributor.authorRiveros, Cristian
dc.date.accessioned2024-01-10T14:22:58Z
dc.date.available2024-01-10T14:22:58Z
dc.date.issued2021
dc.description.abstractIn 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.
dc.description.abstractBoth 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 (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SPANL-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 SPANL admits an FPRAS.
dc.description.funderANID -Millennium Science Initiative Program
dc.description.funderFondecyt Grant
dc.description.funderANID BECAS/MAGISTER NACIONAL
dc.fechaingreso.objetodigital2024-05-14
dc.format.extent40 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1145/3477045
dc.identifier.eissn1557-735X
dc.identifier.issn0004-5411
dc.identifier.urihttps://doi.org/10.1145/3477045
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/80025
dc.identifier.wosidWOS:000744649600009
dc.information.autorucFacultad de Ingeniería; Arenas Saavedra, Marcelo Alejandro; S/I; 81488
dc.issue.numero6
dc.language.isoen
dc.nota.accesocontenido parcial
dc.publisherASSOC COMPUTING MACHINERY
dc.revistaJOURNAL OF THE ACM
dc.rightsacceso restringido
dc.subjectEnumeration
dc.subjectcounting
dc.subjectuniform generation
dc.subjectCOMPLEXITY
dc.subjectPROBABILITY
dc.subjectQUERIES
dc.title#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
dc.typeartículo
dc.volumen68
sipa.codpersvinculados81488
sipa.indexWOS
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
# NFA Admits an FPRAS - Efficient enumeration, counting, and uniform generation for logspace classes.pdf
Size:
3.06 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas