Efficient logspace classes for enumeration, counting and uniform generation

Simple item page
dc.contributor.advisorArenas Saavedra, Marcelo Alejandro
dc.contributor.authorCroquevielle Rendic, Luis Alberto
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2022-10-07T20:10:07Z
dc.date.available2022-10-07T20:10:07Z
dc.date.issued2019
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019
dc.description.abstractIn this work, we study two simple yet general complexity classes, based on logspace Turing machines, which provide a unifying framework for efficient query evaluation in areas like 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. 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 for uniform generation. Interestingly, 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 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.format.extentx, 77 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/tesisUC/ING/65006
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/65006
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/65006
dc.information.autorucEscuela de ingeniería ; Arenas Saavedra, Marcelo Alejandro ; S/I ; 81488
dc.information.autorucEscuela de ingeniería ; Croquevielle Rendic, Luis Alberto ; S/I ; 203873
dc.language.isoen
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subjectLogspace transducerses_ES
dc.subjectConstant delay enumerationes_ES
dc.subjectApproximate countinges_ES
dc.subjectUniform generationes_ES
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleEfficient logspace classes for enumeration, counting and uniform generationes_ES
dc.typetesis de maestría
sipa.codpersvinculados81488
sipa.codpersvinculados203873
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Tesis Croquevielle Luis - EFFICIENT LOGSPACE.pdf
Size:
509.46 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster