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

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

Browse the full STOC paper archive.