#NFA admits an FPRAS

Speaker(s)

Cristian Riveros Jaeger

Affiliation

Pontificia Universidad Católica de Chile (PUC Chile)

Date

Jan. 31, 2024, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

#NFA is the following problem over non-deterministic finite automata (NFA) over words: you receive as input an NFA A and a length N (in unary), and you want to count the number of words of length N accepted by A. Counting the number of solution is a basic algorithmic problem for automata theory, and has several applications on information extraction of documents, data management, and software verification. If A is deterministic, one can count this number in time |A|*N by a dynamic programming strategy. Instead, if A is non-deterministic, the problem becomes intractable, namely, it is #P-complete under Turing reductions. Despite this negative result, this reduction does not exclude that one can find an "approximation" of the number of words. Indeed, it was open whether an FPRAS (Fully Polynomial Randomized Approximation Scheme) exists to solve it until recently Arenas, Croquevielle, Jayaram, and Riveros show that #NFA admits an FPRAS. In this talk, I will present the #NFA problem and the main algorithmic ideas behind this FPRAS to approximate it.

---