Return to Answer

Question 4 (added following JDH's comment): Is there an algorithm which, given $A$ and $D$, with $D$ deterministic, decides whether $L(A) = L(D)$ holds? [Update: the answer to this is no, see note 2 below.]

Note 2: the answer to question 4 (for $(\mathbb{Z},\max,+)$-weighted automata) is negative, in fact even if $D$ is the trivial automaton which accepts every word (one state, both initial and finite, and no transition) so that $L(D) = \sigma^*$, there is no algorithm to decide whether $L(A) = \sigma^*$. See Krob, “The equality problem for rational series with multiplicities in the tropical semiring is undecidable”, International Journal of Algebra and Computation 4 (1994) 405–425, theorem 4.1 & corollary 4.3.

Question 4 (added following JDH's comment): Is there an algorithm which, given $A$ and $D$, with $D$ deterministic, decides whether $L(A) = L(D)$ holds? [Update: see note 2 below.]

Note 2: the answer to question 4 (for $(\mathbb{Z},\max,+)$-weighted automata) is negative, in fact even if $D$ is the trivial automaton which accepts every word (one state, both initial and finite, and no transition) so that $L(D) = \sigma^*$, there is no algorithm to decide whether $L(A) = \sigma^*$. See Almagor, Boker & Kupferman, “What's decidable about weighted automata?”, theorem 4.1 (taking care that since they use $(\mathbb{Z}\cup\{+\infty\},\min,+)$ as tropical semiring instead of $(\mathbb{Z}\cup\{-\infty\},\max,+)$ as above, the set of words of multiplicity $<1$ in their sense is the set of words of multiplicity $\geq 0$ in the above sense).

This is not an answer, but an attempt to rephrase the question into something both meaningful and understandable, so that hopefully someone can answer it.

Question 4 (added following JDH's comment): Is there an algorithm which, given $A$ and $D$, with $D$ deterministic, decides whether $L(A) = L(D)$ holds?

Note that if we consider the question of unweighted automata instead (i.e., all weights are assumed to be $0$), then the answer to questions 1 and 3 is “yes”: in this setup, to construct $D$ we consider the powerset of the set of states of $A$, and create a transition $(\mathbf{q},x,\mathbf{q}')$ in $D$ when $\mathbf{q}'$ is the set of $q'$ such that the transition $(q,x,q')$ exists in $A$ for some $q\in \mathbf{q}$; the accepting states of $D$ are those that contain some accepting state of $A$, and the initial state of $D$ is the singleton $\{q_0\}$ of the accepting state of $A$. This is a classical construction from automata theory (“determinization”). The answer to question 4 is also “yes” in this case (the argument proceeds by first determinizing as just explained, then minimizing the resulting automata, and the simply comparing them). But the fact that we can have negative multiplicities completely changes things.

This is a partial answer (see note 2 below), but mostly an attempt to rephrase the question into something both meaningful and understandable, so that hopefully someone can answer it.

Question 4 (added following JDH's comment): Is there an algorithm which, given $A$ and $D$, with $D$ deterministic, decides whether $L(A) = L(D)$ holds? [Update: the answer to this is no, see note 2 below.]

Note that if we consider the question of unweighted automata instead (i.e., all weights are assumed to be $0$), then the answer to questions 1 and 3 is “yes”: in this setup, to construct $D$ we consider the powerset of the set of states of $A$, and create a transition $(\mathbf{q},x,\mathbf{q}')$ in $D$ when $\mathbf{q}'$ is the set of $q'$ such that the transition $(q,x,q')$ exists in $A$ for some $q\in \mathbf{q}$; the accepting states of $D$ are those that contain some accepting state of $A$, and the initial state of $D$ is the singleton $\{q_0\}$ of the accepting state of $A$. This is a classical construction from automata theory (“determinization”). The answer to question 4 is also “yes” in this case (the argument proceeds by first determinizing as just explained, then minimizing the resulting automata, and the simply comparing them). But the fact that we can have negative multiplicities completely changes things.

Note 2: the answer to question 4 (for $(\mathbb{Z},\max,+)$-weighted automata) is negative, in fact even if $D$ is the trivial automaton which accepts every word (one state, both initial and finite, and no transition) so that $L(D) = \sigma^*$, there is no algorithm to decide whether $L(A) = \sigma^*$. See Krob, “The equality problem for rational series with multiplicities in the tropical semiring is undecidable”, International Journal of Algebra and Computation 4 (1994) 405–425, theorem 4.1 & corollary 4.3.

A $\mathbb{Z}$-weighted finite automaton on $\sigma$ is given by a finite set $Q$ of states, an element $q_0 \in Q$ known as the initial state, a subset $F \subseteq Q$ known as the accepting states, and a finite subset $\delta \subseteq Q \times \sigma \times \mathbb{Z} \times Q$ known as transitions of the automaton (read $(q,x,v,q') \in \delta$ as “the automaton can jump from state $q$ to state $q'$ while consuming symbol $x$ with multiplicity $v$).

For such an automaton, we define the multiplicity of the word $w = x_1\cdots x_n \in \sigma^*$ to be the sum of the $v_1\cdots v_n$ ranging over all accepting paths, that is, all $(q_1,\ldots,q_n)$ and $(v_1,\ldots,v_n)$ such that $q_n\in F$ and $(q_{i-1},x_i,v_i,q_i)\in\delta$ for $1\leq i\leq n$ (note that $q_0$ is the initial state defined with the automaton). The language $L(A)$ defined by the automaton $A$ is the set of words with nonnegative multiplicity.

Important note: this assumes that if a word has no accepting path whatsoever it is part of the language $L(A)$. This strikes me as an odd definition (but it would be even more bizarre to demand both that there exists an accepting path and that the sum of all multiplicities is $\geq 0$). So OP should clarify whether it is really what was intended.

Question 1: Is it true that, for every $\mathbb{Z}$-weighted finite automaton $A$ there is a deterministic one $D$ such that $L(D) = L(A)$?

Note that if we consider the question of unweighted automata instead (i.e., all weights are assumed to be $1$) and modify the definition of the language to be the set of words whose multiplicity is $>0$, then the answer to questions 1 and 3 is “yes”: in this setup, to construct $D$ we consider the powerset of the set of states of $A$, and create a transition $(\mathbf{q},x,\mathbf{q}')$ in $D$ when $\mathbf{q}'$ is the set of $q'$ such that the transition $(q,x,q')$ exists in $A$ for some $q\in \mathbf{q}$; the accepting states of $D$ are those that contain some accepting state of $A$, and the initial state of $D$ is the singleton $\{q_0\}$ of the accepting state of $A$. This is a classical construction from automata theory (“determinization”). [The answer to question 4 is also “yes” in this case, I sketched an explanation in a comment below.] But the fact that we can have negative multiplicities completely changes things.

A $(\mathbb{Z},\max,+)$-weighted finite automaton on $\sigma$ is given by a finite set $Q$ of states, an element $q_0 \in Q$ known as the initial state, a subset $F \subseteq Q$ known as the accepting states, and a finite subset $\delta \subseteq Q \times \sigma \times \mathbb{Z} \times Q$ known as transitions of the automaton (read $(q,x,v,q') \in \delta$ as “the automaton can jump from state $q$ to state $q'$ while consuming symbol $x$ with multiplicity $v$).

For such an automaton, we define the multiplicity of the word $w = x_1\cdots x_n \in \sigma^*$ to be the max of the $v_1+\cdots+v_n$ ranging over all accepting paths, that is, all $(q_1,\ldots,q_n)$ and $(v_1,\ldots,v_n)$ such that $q_n\in F$ and $(q_{i-1},x_i,v_i,q_i)\in\delta$ for $1\leq i\leq n$ (note that $q_0$ is the initial state defined with the automaton), or $-\infty$ if there is no accepting path at all. The language $L(A)$ defined by the automaton $A$ is the set of words having nonnegative multiplicity (i.e., such that there exists an accepting path with $v_1+\cdots+v_n \geq 0$).

[Note on edit: I had initially written this for automata with weights in the integer ring $(\mathbb{Z},+,\times)$ (so we take the sum of the $v_1\cdots v_n$). But I realize, after re-reading the question, that the indended meaning is for the weights to be in the tropical semiring $(\mathbb{Z}\cup\{-\infty\},\max,+)$ (we can forget about the weight $-\infty$ by simply omitting the transition). I'm sorry if this may have caused further confusion.]

Question 1: Is it true that, for every $(\mathbb{Z},\max,+)$-weighted finite automaton $A$ there is a deterministic one $D$ such that $L(D) = L(A)$?

Note that if we consider the question of unweighted automata instead (i.e., all weights are assumed to be $0$), then the answer to questions 1 and 3 is “yes”: in this setup, to construct $D$ we consider the powerset of the set of states of $A$, and create a transition $(\mathbf{q},x,\mathbf{q}')$ in $D$ when $\mathbf{q}'$ is the set of $q'$ such that the transition $(q,x,q')$ exists in $A$ for some $q\in \mathbf{q}$; the accepting states of $D$ are those that contain some accepting state of $A$, and the initial state of $D$ is the singleton $\{q_0\}$ of the accepting state of $A$. This is a classical construction from automata theory (“determinization”). The answer to question 4 is also “yes” in this case (the argument proceeds by first determinizing as just explained, then minimizing the resulting automata, and the simply comparing them). But the fact that we can have negative multiplicities completely changes things.