A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)

DOI10.1145/3406325.3465353MaRDI QIDQ6086980zbMATH OpenOpenAlexWikidataFDO

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

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3406325.3465353

zbMATH Keywords

approximate countingnon-deterministic finite automataregular languagesuniform generation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(1)

• A quasi-polynomial-time algorithm for sampling words from a context-free language

This page was built for publication: A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086980)