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

DOI10.1145/3477045zbMath1499.68124arXiv1906.09226OpenAlexW3210082818MaRDI QIDQ5056438

Luis Alberto Croquevielle, Marcelo Arenas, Rajesh Jayaram, Cristian Riveros

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.09226

zbMATH Keywords

enumerationcountinguniform generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Formal languages and automata (68Q45) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (2)

Answer Counting under Guarded TGDs ⋮ The Complexity of Aggregates over Extractions by Regular Expressions

This page was built for publication:

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