DBScholar

Back to papers

Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation

Summary: Two logspace classes via NL transducers: unambiguous class gives constant‑delay enumeration plus polytime exact counting and uniform generation. Unrestricted class gives poly‑delay enumeration, an FPRAS for counting and polytime Las Vegas uniform generation by proving #NFA (thus all SpanL) admits an FPRAS. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1798
Venue
PODS
Year
2019
Pagerank
7.3870922e-05
Overall Rank
3,472 | 76.19%
DOI
10.1145/3294052.3319704

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{arenas_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319704},
        doi = {10.1145/3294052.3319704},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arenas, Marcelo and Croquevielle, Luis Alberto and Jayaram, Rajesh and Riveros, Cristian},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1,528 Joining Extractions of Regular Expressions 2018 PODS 0.00010486718
2,348 Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity 2018 PODS 8.7135317e-05
2,619 Constant Delay Algorithms for Regular Document Spanners 2018 PODS 8.336529e-05
Previous Page 1 / 1 Next

Semantically Similar Papers