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

Prelegent(ci)

Karolina Drabik

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

26 lutego 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

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

Seminarium

Seminarium „Teoria automatów”

---

Two fundamental classes of finite automata are deterministic and nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word: unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It is known that deciding whether a given NFA is unambiguous and whether it is polynomially ambiguous is possible in quadratic time, and deciding finite ambiguity is possible in cubic time. We provide matching lower bounds showing these running times to be optimal, assuming popular fine-grained complexity hypotheses.

We improve the upper bounds for unary automata, which are essentially directed graphs with a source and a target. In this view, unambiguity asks whether all walks from the source to the target have different lengths. The running time analysis of our algorithm reduces to bounding the entry-wise 1-norm of a GCD matrix, yielding a near-linear upper bound. For finite and polynomial ambiguity, we provide simple linear-time algorithms in the unary case. 

This is joint work with Anita Dürr, Fabian Frei, Filip Mazowiecki and Karol Węgrzycki.

---