Guest Talk

Speaker: Julian Dörfler

Title: Functional Closure Properties of Finite $\IN$-weighted Automata

Abstract:

We can define the counting class #FA, analogously to #P, but instead of counting the number of accepting paths of a polynomial time non-deterministic Turing machine, we count the number of accepting paths of a non-deterministic finite automaton.

We now fully characterize the functional closure properties of this counting class, i.e. for which functions ϕ: ℕ^m→ℕ is ϕ(f_1(w), …, f_m(w)) guaranteed to be computable in #FA, whenever f_1, …, f_m are contained in #FA.

We also determine all univariate closure properties in the promise setting, and all multivariate closure properties under certain assumptions on the promise, in particular we determine all multivariate closure properties where the output vector lies on a monotone algebraic graph variety.