@online{Drabik2501.14725,
TITLE = {Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs},
AUTHOR = {Drabik, Karolina and D{\"u}rr, Anita and Frei, Fabian and Mazowiecki, Filip and W{\k e}grzycki, Karol},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2501.14725},
EPRINT = {2501.14725},
EPRINTTYPE = {arXiv},
YEAR = {2025},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Two fundamental classes of finite automata are deterministic and<br>nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from<br>bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word:<br>unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It<br>is known that deciding whether a given NFA is unambiguous and whether it is<br>polynomially ambiguous is possible in quadratic time, and deciding finite<br>ambiguity is possible in cubic time. We provide matching lower bounds showing<br>these running times to be optimal, assuming popular fine-grained complexity<br>hypotheses.<br> We improve the upper bounds for unary automata, which are essentially<br>directed graphs with a source and a target. In this view, unambiguity asks<br>whether all walks from the source to the target have different lengths. The<br>running time analysis of our algorithm reduces to bounding the entry-wise<br>1-norm of a GCD matrix, yielding a near-linear upper bound. For finite and<br>polynomial ambiguity, we provide simple linear-time algorithms in the unary<br>case.<br> Finally, we study the twins property for weighted automata over the tropical<br>semiring, which characterises the determinisability of unambiguous weighted<br>automata. It occurs naturally in our context as deciding the twins property is<br>an intermediate step in determinisability algorithms for weighted automata with<br>bounded ambiguity. We show that Allauzen and Mohri's quadratic-time algorithm<br>checking the twins property is optimal up to the same fine-grained hypotheses<br>as for unambiguity. For unary automata, we show that the problem can be<br>rephrased to whether all cycles in a weighted directed graph have the same<br>average weight and give a linear-time algorithm.<br>},
}