← All problems
Unverified
Decidability of ( ,+)-weighted automata determinization
Is the following problem decidable: Given , a weighted automaton (WA) over the semiring, answer whether has an equivalent deterministic WA? Remarks: The problem is equivalent when considering only automata with weights in (a.k.a. distance automata). The problem is known to be decidable for polynomially-ambiguous WA. For the general case of exponentially-ambiguous WA, we don't even have any interesting examples where determinization incurs a significant state explosion.
