Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
5 votes

Can we approximate the number of words accepted by an NFA?

And now there is a faster FPRAS: https://arxiv.org/abs/2312.13320
Umang's user avatar
  • 111
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686

Only top scored, non community-wiki answers of a minimum length are eligible