Representing One Letter Weighted Automata Over the Tropical Semiring
2026-06-24 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors study weighted automata working with the tropical semiring and focus on the problem of determinising these automata when the input alphabet has only one symbol. They refine earlier results by showing this problem and its related register minimisation are coNP-complete, meaning they are computationally hard but still decidable. They also improve prior work by efficiently converting any weighted automaton into an equivalent combination of deterministic ones of manageable size. Lastly, they explore the complexity of related problems, showing certain parameterised versions are unlikely to be efficiently solvable.
weighted automatatropical semiringdeterminisationcoNP-completenessunary alphabetregister minimisationChrobak's normal formboundedness problemparameterised complexitycoW_1-hardness
Authors
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki, Łukasz Orlikowski, David Purser, Henery Sinclair-Banks
Abstract
We consider weighted automata over the tropical semiring $\mathbb{Z}_\infty(min, +)$. Recently, it was shown that determinisation is decidable; in this paper we focus on the complexity when the alphabet is unary. In 2001, Lombardy showed this problem is decidable, a close inspection of his proof yields a coNP upper bound on the complexity. Earlier Gaubert showed that every weighted automaton in this setting can be effectively turned into an equivalent union of deterministic weighted automata. We prove Gaubert's result efficiently, presenting it as a generalisation of Chrobak's normal form for unary NFA. In particular, we prove that the equivalent union of deterministic weighted automata can be represented by a weighted automaton of quadratic size in the size of the original one, and this representation can be computed in polynomial time. Building on this, we show that determinisation, and even register minimisation (which generalises determinisation), is coNP-complete. We complete the paper with observations that the boundedness problem is also coNP-complete by reductions with determinisation. Lastly, we provide evidence that all of these problems are not FPT (by proving $coW_1$-hardness) when parametrised by the number of deterministic automata in the union.