pith. sign in

arxiv: 2606.26038 · v2 · pith:6IPMWJHWnew · submitted 2026-06-24 · 💻 cs.FL

Representing One Letter Weighted Automata Over the Tropical Semiring

Shaull Almagor , Isma\"el Jecker , Filip Mazowiecki , {\L}ukasz Orlikowski , David Purser , Henry Sinclair-Banks This is my paper

Pith reviewed 2026-06-26 05:40 UTC · model grok-4.3

classification 💻 cs.FL
keywords weighted automatatropical semiringdeterminisationunary alphabetcoNP-completenessChrobak normal formregister minimisation
0
0 comments X

The pith

Determinisation of unary tropical weighted automata is coNP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to convert any unary weighted automaton over the tropical semiring into an equivalent union of deterministic weighted automata, with the conversion running in polynomial time and producing a quadratic-size representation. This construction generalizes Chrobak's normal form for ordinary unary automata. The representation is then used to prove that deciding determinisability is coNP-complete, and that the same holds for register minimisation, a problem that generalizes determinisation. Reductions from determinisation also establish coNP-completeness for the boundedness problem.

Core claim

Every weighted automaton over the tropical semiring with a unary alphabet can be effectively converted into an equivalent union of deterministic weighted automata. The conversion produces a representation of quadratic size and can be carried out in polynomial time. This fact is used to show that determinisation and register minimisation are coNP-complete, and that boundedness is coNP-complete by reduction.

What carries the argument

Polynomial-time conversion of a unary tropical weighted automaton to a quadratic-size equivalent union of deterministic weighted automata, presented as a generalization of Chrobak's normal form.

If this is right

  • Determinisation is coNP-complete.
  • Register minimisation is coNP-complete.
  • The boundedness problem is coNP-complete via reduction from determinisation.
  • The problems are coW[1]-hard when parametrized by the number of deterministic automata in the union.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The quadratic representation may allow verification algorithms to run on the converted form for moderate-size inputs.
  • Similar conversions could be investigated for weighted automata over other semirings.
  • The coW[1]-hardness result indicates that hardness persists even when the union size is treated as a fixed parameter.

Load-bearing premise

Every weighted automaton can be turned into an equivalent union of deterministic weighted automata with quadratic size in polynomial time.

What would settle it

A unary tropical weighted automaton whose smallest equivalent union of deterministic automata requires more than quadratic size, or for which no polynomial-time conversion exists.

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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that every unary weighted automaton over the tropical semiring admits an equivalent union of deterministic weighted automata that can be represented by a quadratic-size weighted automaton and computed in polynomial time, generalizing Chrobak's normal form. From this construction the authors derive coNP-completeness of determinisation and of register minimisation (which generalises determinisation), coNP-completeness of the boundedness problem via reductions from determinisation, and coW[1]-hardness of the same problems when parameterised by the number of deterministic automata in the union.

Significance. If the central construction is correct, the paper supplies a constructive, efficient normal-form result that extends a classical unary-NFA technique to the weighted setting and yields matching upper and lower bounds for several decision problems. The explicit quadratic-size representation and polynomial-time algorithm constitute a concrete algorithmic contribution that may be reusable beyond the complexity results.

minor comments (2)
  1. [Abstract] Abstract: the sentence stating the quadratic-size representation would benefit from an explicit reference to the section containing the construction and its complexity analysis.
  2. The paper should clarify whether the quadratic-size bound is measured in the number of states or in the total size including weights and transitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our results and for recommending minor revision. The report does not enumerate any specific major comments, so there are no individual points requiring detailed rebuttal or revision at this stage. We note that the referee conditions the significance assessment on the correctness of the central construction; we maintain that the quadratic-size polynomial-time representation of the union of deterministic weighted automata (generalizing Chrobak's normal form) is correctly established in the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central construction is an explicit new polynomial-time algorithm that converts a unary WA over the tropical semiring into an equivalent quadratic-size union of deterministic WAs, presented as a generalization of Chrobak's normal form. This construction is independent of the subsequent coNP-completeness claims, which follow from standard reductions. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear; the argument rests on external prior results (Gaubert, Lombardy, Chrobak) plus the new explicit construction, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim relies on standard properties of the tropical semiring and automata theory, with the key domain assumption being the generalizability of Chrobak's normal form to the weighted setting.

axioms (2)
  • standard math The tropical semiring operations (min as addition, + as multiplication) define the semantics of weighted automata correctly.
    Fundamental to all weighted automata over this semiring.
  • domain assumption Chrobak's normal form for unary NFA can be generalized to weighted automata.
    Invoked as the basis for the representation result.

pith-pipeline@v0.9.1-grok · 5778 in / 1261 out tokens · 34808 ms · 2026-06-26T05:40:11.863405+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 22 canonical work pages

  1. [1]

    Determinization of min-plus weighted automata is decidable

    Shaull Almagor, Guy Arbel, and Sarai Sheinvald. Determinization of min-plus weighted automata is decidable. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 247--257. SIAM, 2026

    2026

  2. [2]

    Unambiguisability and register minimisation of min-plus models

    Shaull Almagor, Guy Arbel, and Sarai Sheinvald. Unambiguisability and register minimisation of min-plus models. In ICALP 2026 , 2026

    2026

  3. [3]

    What's decidable about weighted automata? Inf

    Shaull Almagor, Udi Boker, and Orna Kupferman. What's decidable about weighted automata? Inf. Comput. , 282:104651, 2022. https://doi.org/10.1016/J.IC.2020.104651 doi:10.1016/J.IC.2020.104651

    work page doi:10.1016/j.ic.2020.104651 2022

  4. [4]

    Regular functions and cost register automata

    Rajeev Alur, Loris DAntoni, Jyotirmoy Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science , pages 13--22. IEEE, 2013

    2013

  5. [5]

    Decision problems for additive regular functions

    Rajeev Alur and Mukund Raghothaman. Decision problems for additive regular functions. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II , Lecture Notes in Computer Science, pages 37--48. S...

    work page doi:10.1007/978-3-642-39212-2_7 2013

  6. [6]

    38th Annual

    Jason P. Bell and Daniel Smertnig. Computing the linear hull: Deciding deterministic? and unambiguous? for weighted automata over fields. In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023 , pages 1--13. IEEE , 2023. https://doi.org/10.1109/LICS56636.2023.10175691 doi:10.1109/LICS56636.2023.10175691

    work page doi:10.1109/lics56636.2023.10175691 2023

  7. [7]

    Minimizing cost register automata over a field

    Yahia Idriss Benalioua, Nathan Lhote, and Pierre - Alain Reynier. Minimizing cost register automata over a field. In Rastislav Kr \' a lovic and Anton \' n Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024 , LIPIcs, pages 23:1--23:15. Schloss Dagstuhl - Leibni...

    work page doi:10.4230/lipics.mfcs.2024.23 2024

  8. [8]

    Murawski, and David Purser

    Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, and David Purser. The big-o problem. Log. Methods Comput. Sci. , 18(1), 2022. https://doi.org/10.46298/LMCS-18(1:40)2022 doi:10.46298/LMCS-18(1:40)2022

    work page doi:10.46298/lmcs-18(1:40)2022 2022

  9. [9]

    Une caract \'e risation des fonctions s \'e quentielles et des fonctions sous-s \'e quentielles en tant que relations rationnelles

    Christian Choffrut. Une caract \'e risation des fonctions s \'e quentielles et des fonctions sous-s \'e quentielles en tant que relations rationnelles. Theoretical Computer Science , 5(3):325--337, 1977

    1977

  10. [10]

    Finite automata and unary languages

    Marek Chrobak. Finite automata and unary languages. Theor. Comput. Sci. , 47(3):149--158, 1986. https://doi.org/10.1016/0304-3975(86)90142-8 doi:10.1016/0304-3975(86)90142-8

    work page doi:10.1016/0304-3975(86)90142-8 1986

  11. [11]

    Register complexity and determinisation of max-plus automata

    Laure Daviaud. Register complexity and determinisation of max-plus automata. ACM SIGLOG News , 7(2):4--14, 2020. https://doi.org/10.1145/3397619.3397621 doi:10.1145/3397619.3397621

    work page doi:10.1145/3397619.3397621 2020

  12. [12]

    Fined-grained complexity of ambiguity problems on automata and directed graphs

    Karolina Drabik, Anita D \" u rr, Fabian Frei, Filip Mazowiecki, and Karol Wegrzycki. Fined-grained complexity of ambiguity problems on automata and directed graphs. CoRR , abs/2501.14725, 2025. https://arxiv.org/abs/2501.14725 arXiv:2501.14725 , https://doi.org/10.48550/ARXIV.2501.14725 doi:10.48550/ARXIV.2501.14725

    work page doi:10.48550/arxiv.2501.14725 2025

  13. [13]

    Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited , 2021

    Henning Fernau, Stefan Hoffmann, and Michael Wehar. Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited , 2021. URL: https://arxiv.org/abs/2108.05244, https://arxiv.org/abs/2108.05244 arXiv:2108.05244

    arXiv 2021

  14. [14]

    Parameterized Complexity Theory

    J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

    work page doi:10.1007/3-540-29953-x 2006

  15. [15]

    Rational series over dioids and discrete event systems

    St \'e phane Gaubert. Rational series over dioids and discrete event systems. In 11th International Conference on Analysis and Optimization of Systems Discrete Event Systems: Sophia-Antipolis, June 15--16--17, 1994 , pages 247--256. Springer, 2005

    1994

  16. [16]

    Probabilistic automata on finite words: Decidable and undecidable problems

    Hugo Gimbert and Youssouf Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Pa...

    work page doi:10.1007/978-3-642-14162-1_44 2010

  17. [17]

    Transience bounds for long walks

    Mark Hartmann and Cristina Arguelles. Transience bounds for long walks. Mathematics of operations research , 24(2):414--439, 1999

    1999

  18. [18]

    Limitedness theorem on finite automata with distance functions

    Kosaburo Hashiguchi. Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci. , 24(2):233--244, 1982. https://doi.org/10.1016/0022-0000(82)90051-4 doi:10.1016/0022-0000(82)90051-4

    work page doi:10.1016/0022-0000(82)90051-4 1982

  19. [19]

    Regular languages of star height one

    Kosaburo Hashiguchi. Regular languages of star height one. Inf. Control. , 53(3):199--210, 1982. https://doi.org/10.1016/S0019-9958(82)91028-2 doi:10.1016/S0019-9958(82)91028-2

    work page doi:10.1016/s0019-9958(82)91028-2 1982

  20. [20]

    Determinisation and unambiguisation of polynomially-ambiguous rational weighted automata

    Isma \" e l Jecker, Filip Mazowiecki, and David Purser. Determinisation and unambiguisation of polynomially-ambiguous rational weighted automata. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024 , pages 46:1--46:13. A...

    work page doi:10.1145/3661814.3662073 2024

  21. [21]

    A characterization of the minimum cycle mean in a digraph

    Richard M Karp. A characterization of the minimum cycle mean in a digraph. Discrete mathematics , 23(3):309--311, 1978

    1978

  22. [22]

    Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata

    Daniel Kirsten and Sylvain Lombardy. Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 , pages 589--600. IBFI Schloss Dagstuhl, 2009

    2009

  23. [23]

    Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton

    Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science , 327(3):349--373, 2004

    2004

  24. [24]

    Determinisability of unary weighted automata over the rational numbers

    Peter Kostol \' a nyi. Determinisability of unary weighted automata over the rational numbers. Theor. Comput. Sci. , 898:110--131, 2022. URL: https://doi.org/10.1016/j.tcs.2021.11.002, https://doi.org/10.1016/J.TCS.2021.11.002 doi:10.1016/J.TCS.2021.11.002

    work page doi:10.1016/j.tcs.2021.11.002 2022

  25. [25]

    Sequentialization and unambiguity of (max,+) rational series over one letter

    Sylvain Lombardy. Sequentialization and unambiguity of (max,+) rational series over one letter. In Workshop on max-plus algebras and Their Applications to Discrete-event Systems, Theoretical Computer Science, and Optimization , page 6pp. IFAC, Elsevier Sciences, 2001

    2001

  26. [26]

    Sequential? Theor

    Sylvain Lombardy and Jacques Sakarovitch. Sequential? Theor. Comput. Sci. , 356(1-2):224--244, 2006. https://doi.org/10.1016/J.TCS.2006.01.028 doi:10.1016/J.TCS.2006.01.028

    work page doi:10.1016/j.tcs.2006.01.028 2006

  27. [27]

    u rgen Dassow, Maia Hoeberechts, Helmut J \

    Andrew Martinez. Efficient computation of regular expressions from unary nfas. In J \" u rgen Dassow, Maia Hoeberechts, Helmut J \" u rgensen, and Detlef Wotschke, editors, Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21 - 24, 2002. Pre-proceedings , pages 174--187. Department of Computer ...

    2002

  28. [28]

    Compact representations by finite-state transducers

    Mehryar Mohri. Compact representations by finite-state transducers. In 32nd Annual Meeting of the Association for Computational Linguistics , pages 204--209, 1994

    1994

  29. [29]

    Finite-state transducers in language and speech processing

    Mehryar Mohri. Finite-state transducers in language and speech processing. Computational linguistics , 23(2):269--311, 1997

    1997

  30. [30]

    Powers of matrices over an extremal algebra with applications to periodic graphs

    Karl Nachtigall. Powers of matrices over an extremal algebra with applications to periodic graphs. Mathematical Methods of Operations Research , 46(1):87--102, 1997

    1997

  31. [31]

    On linear recurrence sequences and loop termination

    Jo \" e l Ouaknine and James Worrell. On linear recurrence sequences and loop termination. ACM SIGLOG News , 2(2):4--13, 2015. https://doi.org/10.1145/2766189.2766191 doi:10.1145/2766189.2766191

    work page doi:10.1145/2766189.2766191 2015

  32. [32]

    Papadimitriou and Mihalis Yannakakis

    Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. , 28(2):244--259, 1984. https://doi.org/10.1016/0022-0000(84)90068-0 doi:10.1016/0022-0000(84)90068-0

    work page doi:10.1016/0022-0000(84)90068-0 1984

  33. [33]

    Factoring through monomial representations: arithmetic characterizations and ambiguity of weighted automata

    Antoni Puch and Daniel Smertnig. Factoring through monomial representations: arithmetic characterizations and ambiguity of weighted automata. CoRR , abs/2410.03444, 2024. https://arxiv.org/abs/2410.03444 arXiv:2410.03444 , https://doi.org/10.48550/ARXIV.2410.03444 doi:10.48550/ARXIV.2410.03444

    work page doi:10.48550/arxiv.2410.03444 2024

  34. [34]

    The covering and boundedness problems for vector addition systems

    Charles Rackoff. The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. , 6:223--231, 1978. https://doi.org/10.1016/0304-3975(78)90036-1 doi:10.1016/0304-3975(78)90036-1

    work page doi:10.1016/0304-3975(78)90036-1 1978

  35. [35]

    On the definition of a family of automata

    Marcel Paul Sch \" u tzenberger. On the definition of a family of automata. Inf. Control. , 4(2-3):245--270, 1961. https://doi.org/10.1016/S0019-9958(61)80020-X doi:10.1016/S0019-9958(61)80020-X

    work page doi:10.1016/s0019-9958(61)80020-x 1961

  36. [36]

    Csr expansions of matrix powers in max algebra

    Serge Sergeev and Hans Schneider. Csr expansions of matrix powers in max algebra. Transactions of the American Mathematical society , 364(11):5969--5994, 2012

    2012

  37. [37]

    Convex language semantics for nondeterministic probabilistic automata

    Gerco van Heerdt, Justin Hsu, Jo \" e l Ouaknine, and Alexandra Silva. Convex language semantics for nondeterministic probabilistic automata. Theor. Comput. Sci. , 1040:115191, 2025. https://doi.org/10.1016/J.TCS.2025.115191 doi:10.1016/J.TCS.2025.115191

    work page doi:10.1016/j.tcs.2025.115191 2025

  38. [38]

    On the Complexity of Intersection Non-Emptiness Problems

    Michael Wehar. On the Complexity of Intersection Non-Emptiness Problems . PhD thesis, University at Buffalo, State University of New York, USA , 2016. URL: http://www.michaelwehar.com/documents/mwehar_dissertation.pdf

    2016

  39. [39]

    Unary finite automata vs

    Anthony W idjaja To (Lin). Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. , 109(17):1010--1014, 2009. https://doi.org/10.1016/J.IPL.2009.06.005 doi:10.1016/J.IPL.2009.06.005

    work page doi:10.1016/j.ipl.2009.06.005 2009