10:30 am, Lecture Hall 5
Weighted Tiling Automata on Graphs: Evaluation Complexity
C. Aiswarya
Chennai Mathematical Institute.
04-03-20

---

Abstract

We consider weighted automata on graphs that can model interesting algorithmic questions - like computing the clique number of a graph or computing the permanent of a matrix. We are interested in the problem of computing the value of an input graph in an input weighted automaton. We will also consider decision versions – given an automaton, a graph and a value s, is the computed value {equal to, at least} s? These questions can also be asked for fixed s. We study the computational complexity of these problems for different semirings, and give tight upper and lower bounds for each.