| Links' Seminars and Public Events |   |
Fri, June 23, 2023 11:00 am 12:00 pm | Seminar by Florent Capelli Speaker: Florent Capelli — florent.capelli.me/ Title: A simpler FPRAS for nOBDD Abstract: A simpler FPRAS for nOBDD Abstract: In this talk, we revisit the algorithm by Arenas, Croquevielle, Jayaram and Riveros that allows to approximate the number of words of length n of a non deterministic finite automaton. We explain the algorithm and techniques in a modular and general way, without relating to the particular case of counting words in automaton. We illustrate the soundness of the approach by applying it to the problem of approximatively counting the number of satisfying assignments of a non-deterministic OBDD.  B21 |
