Unary weighted automata over the tropical semiring admit a polynomial-time computable quadratic-size union representation of deterministic automata, implying coNP-completeness of determinisation and register minimisation.
Minimizing cost register automata over a field
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.FL 3years
2026 3verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
A bijection between a subclass of appending streaming string transducers and bimachines enables Ptime register minimization and NP minimization for states and registers, extended via asynchronous bimachines to prove NP-completeness of register minimization with fixed underlying automaton.
citing papers explorer
-
Representing One Letter Weighted Automata Over the Tropical Semiring
Unary weighted automata over the tropical semiring admit a polynomial-time computable quadratic-size union representation of deterministic automata, implying coNP-completeness of determinisation and register minimisation.
-
Minimization of Streaming Transducers
General criteria for minimal models of streaming transducers are established, yielding effective minimization for variants of streaming string-to-tree transducers that build terms at leaves or roots.
-
Minimizing Streaming String Transducers: An algebraic approach
A bijection between a subclass of appending streaming string transducers and bimachines enables Ptime register minimization and NP minimization for states and registers, extended via asynchronous bimachines to prove NP-completeness of register minimization with fixed underlying automaton.