Representing One Letter Weighted Automata Over the Tropical Semiring
Pith reviewed 2026-06-25 19:08 UTC · model grok-4.3
The pith
A unary weighted automaton over the tropical semiring converts to an equivalent union of deterministic automata via a quadratic-size representation computable in polynomial time, making determinisation coNP-complete.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Every weighted automaton over ℤ_∞(min, +) with a unary alphabet can be effectively turned into an equivalent union of deterministic weighted automata; moreover this union admits a representation by a single weighted automaton of quadratic size that is computable in polynomial time. The construction generalizes Chrobak's normal form. Determinisation and register minimisation are therefore coNP-complete, the boundedness problem is coNP-complete, and all three problems are coW[1]-hard when parameterized by the number of deterministic automata in the union.
What carries the argument
The quadratic-size weighted automaton that represents the union of deterministic automata, obtained by generalizing Chrobak's normal form to the tropical semiring.
If this is right
- Determinisation of unary tropical weighted automata is coNP-complete.
- Register minimisation, which generalises determinisation, is coNP-complete.
- The boundedness problem for these automata is coNP-complete.
- All three problems remain coW[1]-hard when parameterized by the number of automata in the union.
Where Pith is reading between the lines
- The unary restriction is essential to obtaining both the polynomial-time quadratic construction and the coNP upper bounds.
- The coNP upper bound for determinisation follows directly from a close reading of Lombardy’s 2001 decidability proof.
- The parameterization result suggests that the number of components in the union is an inherently hard parameter even when the alphabet is unary.
Load-bearing premise
The algebraic properties of the tropical semiring together with the unary-alphabet restriction permit both the quadratic-size representation and the hardness reductions.
What would settle it
A concrete unary tropical weighted automaton whose smallest equivalent union of deterministic automata requires more than quadratic size, or a polynomial-time algorithm that decides determinisability.
read the original 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies weighted automata over the tropical semiring ℤ_∞(min,+) restricted to a unary alphabet. It shows that Gaubert's effective conversion of any such automaton into an equivalent union of deterministic weighted automata can be realized by a single weighted automaton of quadratic size that is computable in polynomial time; this construction is presented as a generalization of Chrobak's normal form for unary NFAs. Using the construction, the authors prove that both determinisation and the more general register-minimisation problem are coNP-complete (upper bound via inspection of Lombardy 2001, hardness via explicit reductions exploiting tropical arithmetic). They further establish coNP-completeness of the boundedness problem by reduction from determinisation and show coW[1]-hardness when the problems are parametrized by the number of deterministic automata in the union.
Significance. If the central claims hold, the quadratic-size poly-time construction supplies a concrete algorithmic strengthening of Gaubert's theorem and directly enables the complexity results; the explicit hardness reductions and the generalization of Chrobak's form are clear strengths. Establishing coNP-completeness for determinisation and register minimisation in this setting would be a useful addition to the complexity landscape of weighted automata over semirings.
major comments (1)
- [the paragraph on Lombardy’s 2001 proof and the subsequent complexity claims] The paragraph stating the coNP upper bound for determinisation and register minimisation asserts that 'a close inspection of [Lombardy 2001] yields a coNP upper bound' but supplies no explicit nondeterministic polynomial-time procedure (e.g., a poly-size witness consisting of a register assignment or a violating cycle together with a verification routine). Because the coNP upper bound is load-bearing for the coNP-completeness theorem, this omission must be repaired by exhibiting the nondeterministic algorithm inside the manuscript.
minor comments (1)
- The abstract claims that boundedness is shown coNP-complete 'by reductions with determinisation'; the precise reduction (including how the unary restriction and tropical weights are preserved) should be stated explicitly in the main text even if it is routine.
Simulated Author's Rebuttal
We thank the referee for the careful review and for identifying the need to make the coNP upper bound fully explicit. We agree that the current reference to Lombardy 2001 is insufficient on its own and will revise the manuscript to include a self-contained description of the nondeterministic polynomial-time procedure.
read point-by-point responses
-
Referee: The paragraph stating the coNP upper bound for determinisation and register minimisation asserts that 'a close inspection of [Lombardy 2001] yields a coNP upper bound' but supplies no explicit nondeterministic polynomial-time procedure (e.g., a poly-size witness consisting of a register assignment or a violating cycle together with a verification routine). Because the coNP upper bound is load-bearing for the coNP-completeness theorem, this omission must be repaired by exhibiting the nondeterministic algorithm inside the manuscript.
Authors: We accept the referee’s observation. Lombardy’s 2001 construction for decidability of determinisation over the tropical semiring can be adapted to yield an NP procedure for the complement: the nondeterministic machine guesses a finite set of registers together with a candidate violating cycle (or a pair of paths that witness non-equivalence to any deterministic automaton), then verifies in polynomial time that the guessed registers produce a strictly smaller value on the cycle than any deterministic equivalent while preserving the accepted weighted language on all other inputs. We will insert a new subsection (immediately after the citation of Lombardy) that spells out this witness format, the verification routine, and why it runs in polynomial time. The same witness works for register minimisation by additionally guessing the target number of registers. This change will be incorporated in the revised manuscript. revision: yes
Circularity Check
No significant circularity; central claims rest on external citations and explicit reductions
full rationale
The paper derives the coNP upper bound for determinisation by citing and inspecting Lombardy 2001 (external, non-self citation). Hardness follows from explicit reductions from known coNP-complete problems. The quadratic-size union representation is presented as an efficient generalisation of Gaubert's result (external citation) and Chrobak's normal form for unary NFA, with the construction claimed computable in polynomial time. No load-bearing step reduces by definition, fitted parameter, or self-citation chain to the target result. The derivation is self-contained against the cited external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Tropical semiring (Z_infty, min, +) satisfies the required algebraic identities for weighted automata
- domain assumption Chrobak’s normal form for unary NFAs extends to the weighted setting without asymptotic blow-up beyond quadratic
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.