Browsing by Author "Alberto Croquevielle, Luis"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- Item#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes(ASSOC COMPUTING MACHINERY, 2021) Arenas, Marcelo; Alberto Croquevielle, Luis; Jayaram, Rajesh; Riveros, CristianIn 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.