Fully Polynomial Time Randomized Approximation Scheme for Counting the number of words of an NFA

What is it about?

This article considers the counting problem for NFAs (short for non-deterministic finite automata) --- how many words of a given length does a given NFA accept? --- from a computational perspective. This problem is known to be "intractable" in general, i.e., no fast algorithm exists that can exactly compute how many words a given (arbitrary) NFA accepts. While exact counting cannot be solved using fast algorithm, how about approximating the count (also known as the "approximate counting" problem for NFAs)? The question "is there a fast algorithm that can approximate this answer?" was open for a long time, until in 2019 a faster algorithm was eventually proposed. This algorithm proposes a new algorithm for approximating this count which is significantly faster than the previous best known algorithm. This brings the theoretical improvements in the counting problem closer to being practical!

Featured Image