Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs

Karolina Drabik, Anita Dürr, Fabian Frei +2

In the field of computational logic, two classes of finite automata are considered fundamental: deterministic and nondeterministic automata (DFAs and NFAs). In a more fine-grained…