← All problems
Unverified
Does a ( min,+)-WA preserve REG by inverse image?
We are interested in functions realized by weighted automata over the semiring . An -weighted automaton over alphabet realizes a partial function . We want to decide given such a function if it preserves ``simple'' sets by inverse image. By simple we mean regular languages ( is viewed a the set of words over a unary alphabet, hence the regular languages are the semilinear sets). Let us state the decision problem. Input: , weighted automaton over Question: Does it hold that for all semilinear, is regular? Remark. This is equivalent to solving the problem over the semiring .
