← All problems
Unverified

Decidability of ( ,+)-weighted automata determinization

Is the following problem decidable: Given AA, a weighted automaton (WA) over the (min⁡,+)(\min,+) semiring, answer whether AA has an equivalent deterministic WA? Remarks: The problem is equivalent when considering only automata with weights in {0,1}\{0,1\} (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.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu