*This is an extended version of [Gra21]

# A Nivat theorem for weighted alternating automata over commutative semirings

Gustav Gravolle  Institute of Computer Science, Leipzig University, 04109
Leipzig, Germany<EMAIL_ADDRESS>
###### Abstract.

In this paper, we give a Nivat-like characterization for weighted alternating
automata over commutative semirings (WAFA). We investigate the use of trees in
the run semantics for WAFA and prove that weighted alternating automata can be
characterized as the concatenation of weighted finite tree automata (WFTA) and
a specific class of tree homomorphism. We show that the class of series
recognized by weighted alternating automata is closed under inverses of
homomorphisms, but not under homomorphisms. We give a logical characterization
of weighted alternating automata, which uses weighted MSO logic for trees.
Finally we investigate the strong connection between weighted alternating
automata and polynomial automata. Using the corresponding result for
polynomial automata, we are able to prove that the ZERONESS problem for
weighted alternating automata with the rational numbers as weights is
decidable.

###### Key words and phrases:

automata theory, weighted automata, alternating automata, weighted logics,
tree automata

This work was supported by Deutsche Forschungsgemeinschaft (DFG),
Graduiertenkolleg 1763 (QuantLA)

##  1\. Introduction

Non-determinism, a situation with several possible outcomes, is usually
interpreted as a choice. An (existential) automaton accepts if there exists at
least one successful run. Contrary to this, one can view non-determinism as an
obligation. A universal automaton would accept if all possible runs are
successful. While this notion of non-determinism is less prominent, it is
equally natural. Allowing for the simultaneous use of existential and
universal determinism leads to the concept of alternation, such as in
alternating Turing machines [CKS81] or alternating automata on finite [BL80],
or infinite structures [DS87]. States of an alternating finite automaton (AFA)
are either existential, or universal. For an existential state at least one of
the outgoing runs needs to be successful, for a universal state all of the
outgoing runs need to be successful to make the entire run successful. It is
even possible to mix both modes by assigning a propositional formula over the
states to each pair of state and letter. Alternating finite automata have been
known for a long time. They are more succinct than finite automata and
constructions like the complement, or intersection are easy for them. Due to
this, they have many uses such as a stepping stone between logics and automata
[DGV13], or in program verification [Var95].

While alternating automata recognize the same class of languages as finite
automata, the situation is different in the weighted setting. A weighted
finite automaton (WFA) assigns a weight to each of its transitions. The weight
of a run is computed by multiplying its transition weights. Finally, the
automaton assigns to each input the sum over all weights of runs corresponding
to this input. By this, a weighted automaton recognizes a quantitative
language a mapping from the set of words into a weight structure. Depending on
the weight structure used, we may view a quantitative language, as a
probability distribution over the words, as a cost or yield assignment, or as
the likelihood or quantity of success for each input. To simultaneously allow
for a multitude of interesting weight structures, weighted automata have been
studied over arbitrary semirings [DKV09].

To adapt alternating automata into the weighted setting, we observe that the
existence of a run in a finite automaton becomes a sum over all runs in a
weighted automaton. Analogously, the demand for all runs to be successful
becomes a product over all runs. More precisely, if a weighted alternating
finite automaton (WAFA) is in an additive state, it will evaluate to the sum
over the values of all outgoing runs. If the weighted alternating automaton is
in a multiplicative state, it will evaluate to the product over the values of
all outgoing runs. And again, we are able to mix both modes, this time by
assigning polynomials over the states to each pair of state and letter.
Weighted alternating automata over infinite words where studied in [CDH09] and
in [AK11] over finite words. While these authors focused on very specific
weight structures, a more recent approach defines weighted alternating
automata over arbitrary commutative semirings [KM18].

Weighted alternating automata have the same expressive power as weighted
automata if and only if the semiring used is locally finite [KM18]. However,
for many interesting semirings such as the rational numbers, weighted
alternating automata are strictly more expressive than weighted automata.
While we have a fruitful framework for weighted automata, woven by results
like the Nivat theorem for weighted automata [DKar], the equivalence of
weighted automata and weighted rational expressions [Sch61] and weighted
restricted MSO logic [DG07], or the decidability of equality due to
minimization if weights are taken from a fields [Sch61] and many more, no such
results are known for weighted alternating automata. In this paper we will
extend the results on weighted alternating automata by connecting them to
known formalisms and thereby establishing further characterizations of
quantitative languages recognized by weighted alternating automata. From there
on, we will use these connections to prove interesting properties for weighted
alternating automata, but also to translate known results for weighted
alternating automata into other settings.

After a brief recollection of basic notions and notations in Section 2,
Section 3 will establish several normal forms for weighted alternating
automata (Lemma 1, Lemma 2) that are used as the basis of later proofs.
Section 4 includes our core result (Theorem 6), a characterization of weighted
alternating automata by the concatenation of weighted finite tree automata
(WFTA) together with certain homomorphisms. More precisely, we consider word-
to-tree homomorphisms that translate words viewed as trees into trees over
some arbitrary ranked alphabet. We can show that a quantitative language is
recognized by a weighted alternating automata if, and only if there exists
word-to-tree homomorphism and a weighted tree automaton such that the
evaluation of the weighted alternating automata on any given word is the same
as the evaluation of the weighted tree automaton on the image of the
homomorphism of this word.

In Section 5 we will use this result to prove that the class of quantitative
languages recognized by weighted alternating automata is closed under inverses
of homomorphisms (Corollary 9). However, we can prove the same is not true for
homomorphisms in general (Lemma 10). Since the closure under homomorphisms
plays a key part in the proof of the Nivat theorem for weighted automata this
prohibits a one-to-one translation of the Nivat theorem for weighted automata
into the setting of weighted alternating automata. Nonetheless, we will
utilize the connection between weighted alternating automata and weighted tree
automata, as well as a Nivat theorem for weighted tree automata, to prove an
adequate result for weighted alternating automata (Theorem 13). This will lead
us directly into a logical characterization of quantitative languages
recognized by weighted alternating automata with the help of weighted
restricted MSO logic for weighted tree automata (Section 6 Theorem 15). It is
well known that recognizable tree languages are closed under inverses of tree
homomorphisms. However, the same does not hold in the weighted setting for
arbitrary commutative semirings. Section 7 gives a precise characterization of
the class of semirings for which weighted tree automata are closed under
inverses of homomorphisms (Theorem 16). For this purpose, we will use our core
theorem, and a result form [KM18].

Lastly, in Section 8, we investigate the connection between weighted
alternating automata and recently introduced polynomial automata [BTSW17] to
prove the decidability of the ZERONESS and EQUALITY problems for weighted
alternating automata if weights are taken from the rational numbers (Corollary
20).

##  2\. Preliminaries

Let $\mathbb{N}=\\{0,1,2,\ldots\\}$ denote the set of non-negative integers.
For sets $M,N$ we denote the cardinality of $M$ by $|M|$, the set of subsets
of $M$ by $\operatorname{\mathcal{P}}(M)$, the Cartesian product of $M$ and
$N$ by $M\times N$, and the set of mappings from $M$ to $N$ by $N^{M}=\\{f\mid
f:M\rightarrow N\\}$. If $M$ is finite and non-empty, it is also called
alphabet.

For the remainder of this paper, let $\Sigma,\Gamma$ and $\Lambda$ denote
alphabets. The set of all (finite) words over $\Sigma$ is denoted by
$\Sigma^{*}$. Let $|w|$ denote the length of a word $w$ and
$\Sigma^{k}=\\{w\in\Sigma^{*}\mid|w|=k\\}$. The unique word in $\Sigma^{0}$ is
called empty word and denoted by $\varepsilon$. The concatenation of words
$u,v$ is denoted by $u\cdot v$ or just $uv$. A mapping
$h:\Lambda^{*}\rightarrow\Sigma^{*}$ is called homomorphism if $h(u\cdot
v)=h(u)\cdot h(v)$ and $h$ is non-deleting if $h(a)\neq\varepsilon$ for all
$a\in\Lambda$.

A monoid is an algebraic structure $(M,\cdot,1)$, where $\cdot$ is a binary
associative internal operation and $m\cdot 1=1\cdot m$ for all $m\in M$. A
monoid is commutative if $\cdot$ is commutative.

A semiring is an algebraic structure $(S,+,\cdot,0,1)$, where $(S,+,0)$ is a
commutative monoid, $(S,\cdot,1)$ is a monoid, $s\cdot 0=0=0\cdot s$ for all
$s\in S$, and $s_{3}\cdot(s_{1}+s_{2})=s_{3}\cdot s_{1}+s_{3}\cdot s_{2}$ and
$(s_{1}+s_{2})\cdot s_{3}=s_{1}\cdot s_{3}+s_{2}\cdot s_{3}$ for all
$s_{1},s_{2},s_{3}\in S$. A semiring is commutative if $(S,\cdot,1)$ is
commutative.

_For the remainder of this paper, let $S$ denote a commutative semiring._

For any set $M$, we denote $S^{M}$ by $S\langle\mkern-4.0mu\langle
M\rangle\mkern-4.0mu\rangle$. For $L\subseteq M$ we define the characteristic
function $\mathbb{1}_{L}\in S\langle\mkern-4.0mu\langle
M\rangle\mkern-4.0mu\rangle$ by $\mathbb{1}_{L}(w)=1$ if $w\in L$ and
$\mathbb{1}_{L}(w)=0$ otherwise for all $w\in M$. An element $s\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ is called
$S$-weighted $\Sigma$-language (for short: weighted language).

Let $X_{n}$ always denote a linear ordered set with $|X_{n}|=n\in\mathbb{N}$,
we refer to the $i$-th element of $X_{n}$ by $x_{i}$. Let $S\langle
X_{n}\rangle$ denote the semiring of polynomials with coefficients in $S$ and
commuting indeterminates $x_{1},\ldots,x_{n}$. We say $m\in S\langle
X_{n}\rangle$ is a monomial if $m=s\cdot x_{1}^{k_{1}}\cdot\ldots\cdot
x_{n}^{k_{n}}$ for some $s\in S$ and $k_{1},\ldots,k_{n}\in\mathbb{N}$. The
degree of $m$ is $\sum_{i=1}^{n}k_{i}$. A monomial $m$ is a constant monomial
if its degree is zero. Each polynomial which can be written as a sum of
distinct non-constant monomials is called a non-constant polynomial and the
set of all non-constant polynomials is denoted by ${S\langle
X_{n}\rangle}_{\text{const}=0}$. For $p,p_{1},\ldots,p_{n}\in S\langle
X_{n}\rangle$ let $p\langle p_{1},\ldots,p_{n}\rangle$ denote the simultaneous
substitution of $x_{i}$ by $p_{i}$ in $p$ for all $1\leq i\leq n$.

A ranked alphabet is an ordered pair $(\Gamma,\operatorname{Rank})$, where
$\operatorname{Rank}:\Gamma\rightarrow\mathbb{N}$ is a mapping. Without loss
of generality, we assume $X_{n}\cap\Gamma=\varnothing$. Moreover, let
$\Gamma^{(r)}=\\{\gamma\in\Gamma\mid\operatorname{Rank}(\gamma)=r\\}$ and
$\operatorname{Rank}(\Gamma)=\max(\\{\operatorname{Rank}(\gamma)\mid\gamma\in\Gamma\\})$.

The set of $\Gamma$-terms over $X_{n}$ is the smallest set $T_{\Gamma}[X_{n}]$
such that $\Gamma^{(0)}\cup X_{n}\subseteq T_{\Gamma}[X_{n}]$; and
$g(t_{1},\ldots,t_{\operatorname{Rank}(g)})\in T_{\Gamma}[X_{n}]$ for all
$g\in\Gamma$ and all $t_{1},\ldots,t_{\operatorname{Rank}(g)}\in
T_{\Gamma}[X_{n}]$. We denote $T_{\Gamma}(X_{0})=T_{\Gamma}(\varnothing)$ by
$T_{\Gamma}$. We extend $\operatorname{Rank}$ by putting
$\operatorname{Rank}(x_{i})=0$ for all $i\in\mathbb{N}$. If
$\operatorname{Rank}$ is clear from the context, we just write
$g(t_{1},\ldots,t_{k})$. Moreover, we identify $g$ and $g()$ for
$g\in\Gamma^{(0)}\cup X_{n}$. Hence, all terms $t\in T_{\Gamma}[X_{n}]$ are of
the form $t=g(t_{1},\ldots,t_{k})$ for some $g\in\Gamma\cup X_{n}$ and
$t_{1},\ldots,t_{k}\in T_{\Gamma}[X_{n}]$.

We define
$\operatorname{Pos}:T_{\Gamma}[X_{n}]\rightarrow\operatorname{\mathcal{P}}(\mathbb{N}^{*}):g(t_{1},\ldots,t_{k})\mapsto\\{\varepsilon\\}\cup\bigcup_{i=1}^{k}\\{i\\}\cdot\operatorname{Pos}(t_{i})$.
Let $t=g(t_{1},\ldots,t_{k})$. The mapping
$\operatorname{Label}_{t}:\operatorname{Pos}(t)\rightarrow\Gamma\cup X_{n}$ is
defined by $\operatorname{Label}_{t}(\varepsilon)=g$; and
$\operatorname{Label}_{t}(w)=\operatorname{Label}_{t_{i}}(v)$ if
$w=iv\in\operatorname{Pos}(t)$. We will identify $t$ and the mapping
$\operatorname{Label}_{t}$: We write $t(w)$ to denote
$\operatorname{Label}_{t}(w)$ and refer to terms as trees. Consequently, we
have
$t^{-1}(g)=\\{w\in\operatorname{Pos}(t)\mid\operatorname{Label}_{t}(w)=g\\}$
for all $g\in T_{\Gamma}[X_{n}]$.

For $t=g(t_{1},\ldots,t_{k}),t^{\prime}\in T_{\Gamma}[X_{n}]$, and
$w\in\operatorname{Pos}(t)$, the subtree of $t$ at $w$, denoted by $t|_{w}$
and the substitution of $t^{\prime}$ in $t$ at $w$, denoted by $t\langle
w\leftarrow t^{\prime}\rangle$ are defined by $t|_{\varepsilon}=t$ and
$t\langle\varepsilon\leftarrow t^{\prime}\rangle=t^{\prime}$ if
$w=\varepsilon$; and $t|_{w}=t_{i}|_{v}$ and $t\langle w\leftarrow
t^{\prime}\rangle=g(t_{1},\ldots,t_{i-1},t_{i}\langle v\leftarrow
t^{\prime}\rangle,t_{i+1},\ldots,t_{k})$ for $w=iv\in\operatorname{Pos}(t)$.
Moreover, let $M\subseteq\operatorname{Pos}(t)$ and $|M|=l$. We define
$t\langle M\leftarrow(t^{\prime}_{1},\ldots,t^{\prime}_{l})\rangle=t\langle
m_{l}\leftarrow t^{\prime}_{l}\rangle\cdots\langle m_{1}\leftarrow
t^{\prime}_{1}\rangle$, where $m_{i}$ is the $i$-th element of $M$ regarding
to the lexicographical order on $\mathbb{N}^{*}$. In case
$t^{\prime}_{1}=\ldots=t^{\prime}_{l}=t^{\prime}$, we abbreviate $t\langle
M\leftarrow(t^{\prime}_{1},\ldots,t^{\prime}_{l})\rangle$ by $t\langle
M\leftarrow t^{\prime}\rangle$. If $M=t^{-1}(x_{i})$, we write $t\langle
x_{i}\leftarrow(t^{\prime}_{1},\ldots,t^{\prime}_{l})\rangle$ to denote
$t\langle M\leftarrow(t^{\prime}_{1},\ldots,t^{\prime}_{l})\rangle$. Finally,
let $t\langle t^{\prime}_{1},\ldots,t^{\prime}_{n}\rangle=t\langle
t^{-1}(x_{1})\leftarrow t^{\prime}_{1}\rangle\cdots\langle
t^{-1}(x_{n})\leftarrow t^{\prime}_{n}\rangle$ denote the simultaneous
substitution in trees.

We say a tree $t$ is non-deleting in $l$ variables if it contains at least one
symbol from $\Gamma$ and each of the variables $x_{1},\ldots,x_{l}$ occurs at
least once in $t$. We say $t$ is linear in $l$ variables if it is non-deleting
in $l$ variables and each of the variables occurs at most once in $t$.
Moreover, let $\operatorname{r}(t)=\sum_{i=1}^{n}|t^{-1}(x_{i})|$ and
$T_{\Gamma}^{(r)}(X_{n})=\\{t\in
T_{\Gamma}(X_{n})\mid\operatorname{r}(t)=r\\}$ for all $r\in\mathbb{N}$.

A tree homomorphism $h:T_{\Gamma}\rightarrow T_{\Lambda}$ is a mapping such
that for all $g\in\Gamma^{(r)}$ there exists $t_{g}\in T_{\Lambda}[X_{r}]$
with $h(g(t_{1},\ldots,t_{r}))=t_{g}\langle h(t_{1}),\ldots,h(t_{r})\rangle$
for all $t_{1},\ldots,t_{r}\in T_{\Gamma}$. We will denote $t_{g}$ by $h(g)$,
even though $t_{g}$ is not necessarily in $T_{\Lambda}$. A tree homomorphism
is non-deleting (resp. linear) if each $h(g)$ is non-deleting (resp. linear)
in $\operatorname{Rank}(g)$ variables.

##  3\. Weighted alternating finite automata

This section introduces weighted alternating finite automata (WAFA) and shows
how to achieve desirable normal forms of WAFA (Lemma 1, Lemma 2). We will
follow the definitions of [KM18].

A weighted alternating finite automaton (WAFA) is a 5-tuple
$\mathcal{A}=(Q,\Sigma,\delta,P_{0},\tau)$, where $Q=\\{q_{1},\ldots,q_{n}\\}$
is a finite set of states, $\Sigma$ is an alphabet,
$\delta:Q\times\Sigma\rightarrow S\langle Q\rangle$ is a transition function,
$P_{0}\in S\langle Q\rangle$ an initial polynomial, and $\tau:Q\rightarrow S$
a final weight function.

Let $\mathcal{A}=(Q,\Sigma,\delta,P_{0},\tau)$ be a WAFA. Its state behavior
$[\mathcal{A}]:Q\times\Sigma^{*}\rightarrow S$ is the mapping defined by

$[A](q,w)=\begin{cases}\tau(q)&\text{if }w=\varepsilon,\\\
\delta(q,a)\big{\langle}[\mathcal{A}](q_{1},v),\ldots,[\mathcal{A}](q_{n},v)\big{\rangle}&\text{if
}w=av\text{ for }a\in\Sigma\enspace.\end{cases}$

Usually, we will write $[\mathcal{A}]_{q}(w)$ instead of $[\mathcal{A}](q,w)$.
Now, the behavior of $\mathcal{A}$ is the weighted language
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]:\Sigma^{*}\rightarrow S$ defined by

$[\mkern-3.0mu[A]\mkern-3.0mu](w)=P_{0}\big{\langle}[\mathcal{A}]_{q_{1}}(w),\ldots,[\mathcal{A}]_{q_{n}}(w)\big{\rangle}\enspace.$

A weighted language $s$ is recognized by $\mathcal{A}$ if and only if
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=s$. Two WAFA are said to be
equivalent if they recognize the same weighted language. To ease late proofs,
let $M_{(q,a)}$ denote the set of monomials that appear in $\delta(q,a)$.

We say a WAFA $(Q,\Sigma,\delta,P_{0},\tau)$ with $Q=\\{q_{1},\ldots,q_{n}\\}$
is a weighted finite automaton (WFA) if $P_{0}=\sum_{j=1}^{n}s_{j}\cdot q_{j}$
and $\delta(q_{i},a)=\sum_{j=1}^{n}s^{a}_{ij}\cdot q_{j}$ for all $1\leq i\leq
n$, $a\in\Sigma$. This definition coincides with the usual definition
[DG09],[DG07]. We can see this by defining the initial weight function by
$\lambda(q_{i})=s_{i}$, the transition weight function by
$\mu(a)(q_{i},q_{j})=s^{a}_{ij}$, and the final weight function by
$\gamma(q_{i})=\tau(q_{i})$ for all $1\leq i,j\leq n$ and all $a\in\Sigma$.

We say $\mathcal{A}$ is nice if it has the following properties:

  1. (1)

$\delta(q,a)$ is a finite sum of pairwise distinct, monomials of the form
$s\cdot q_{1}^{k_{1}}\cdot\ldots\cdot q_{n}^{k_{n}}$ for all $q\in
Q,a\in\Sigma$,

  2. (2)

all monomials in $P_{0}$ and $\delta$ are non-constant,

  3. (3)

$P_{0}=q_{1}$.

Moreover, we say that $\mathcal{A}$ is purely polynomial if:

  1. (iv)

all monomials (in $P_{0}$ and $\delta$) have coefficient $1$.

We want to show that we can always assume a WAFA to be nice and purely
polynomial.

######  Lemma 1.

For each WAFA $\mathcal{A}$ there exists an equivalent WAFA
$\mathcal{A}^{\prime}$ such that (i)-(iv) hold for $\mathcal{A}^{\prime}$.

######  Proof 3.1.

Let $\mathcal{A}=(Q,\Sigma,\delta,P_{0},\tau)$ be a WAFA.

  1. (1)

Since $\cdot$ is distributive and commutative in $S\langle Q\rangle$ there
exists an equivalent WAFA $\mathcal{A}^{\prime}$ such that (i) holds.

  2. (2)

Assume (i) holds for $\mathcal{A}=(Q,\Sigma,\delta,P_{0},\tau)$. We define a
WAFA
$\mathcal{A}^{\prime}=(Q^{\prime},\Sigma,\delta^{\prime},P_{0}^{\prime},\tau^{\prime})$
which includes a new state $q_{c}$ for each constant $c$ occurring in
$\mathcal{A}$. Furthermore, $\delta^{\prime}$ and $P_{0}^{\prime}$ are as
$\delta$ and $P_{0}$, respectively, but each occurrence of each constant $c$
is replaced by $q_{c}$. Moreover, $\delta^{\prime}(q_{c},a)=q_{c}$ for all
$a\in\Sigma$ and $\tau^{\prime}(q_{c})=c$. There is a finite number of
constants in $\mathcal{A}$. Thus, $\mathcal{A}^{\prime}$ is a WAFA. It is easy
to see that $\mathcal{A}$ and $\mathcal{A}^{\prime}$ are equivalent and that
(i)-(ii) hold for $\mathcal{A}^{\prime}$.

  3. (3)

Assume (i)-(ii) hold for $\mathcal{A}$. Due to Lemma 6.3 of [KM18], there
exists an equivalent WAFA $\mathcal{A}^{\prime}$ such that (i)-(iii) hold for
$\mathcal{A}^{\prime}$.

  4. (4)

Assume that (i)-(iii) hold for $\mathcal{A}$. We define

$Q^{\prime}=Q\cup\\{q_{s}\mid s\text{ is the coefficient of some monomial in
}\mathcal{A}\\}.$

Without loss of generality, we can assume that these sets are disjoint.
Furthermore, let $\delta^{\prime}$ be defined by

$\delta^{\prime}(q,a)=\begin{cases}\sum\limits_{s\cdot{q_{1}}^{k_{1}}\ldots{q_{n}}^{k_{n}}\in
M_{(q,a)}}{q_{1}}^{k_{1}}\ldots{q_{n}}^{k_{n}}\cdot q_{s}&\text{if }q\in
Q\text{ and}\\\ q&\text{otherwise}\end{cases}$

for all $q\in Q^{\prime}$, $a\in\Sigma$. Moreover, let $\tau^{\prime}$ be
defined by

$\tau^{\prime}(q)=\begin{cases}\tau(q)&\text{if }q\in Q\text{ and}\\\
s&\text{if }q=q_{s}\end{cases}$

for all $q\in Q^{\prime}$. Consider the WAFA
$\mathcal{A}^{\prime}=(Q^{\prime},\Sigma,P_{0},\delta^{\prime},\tau^{\prime})$.
It is easy to see that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=[\mkern-3.0mu[\mathcal{A}^{\prime}]\mkern-3.0mu]$
and that every monomial in $\mathcal{A}^{\prime}$ has $1$ as coefficient.

If the appropriate order on $Q^{\prime}$ is chosen, properties (i)-(iii) hold
for $\mathcal{A}^{\prime}$, too. However, if this construction is applied to a
WFA $\mathcal{A}$, the resulting $\mathcal{A}^{\prime}$ does not have to be a
WFA.

In [KM18] the transition function and the initial polynomial are not allowed
to contain constants. This corresponds to the property that runs are not
allowed to terminate before the entire word is read. Since it will ease later
constructions, we allowed constants in our definition. Nevertheless, as Lemma
1 (ii) shows, the introduction of constants does not increase expressiveness
since it is possible to simulate terminating transitions by „deadlock“-states.

We say a WAFA $(Q,\Sigma,\delta,P_{0},\tau)$ is equalized if all monomials
occurring in $\delta$ have the same degree.

######  Lemma 2.

For each WAFA $\mathcal{A}$ there exists an equivalent and equalized WAFA
$\mathcal{A}^{\prime}$.

######  Proof 3.2.

Let $\mathcal{A}=(Q,\Sigma,\delta,q_{1},\tau)$ be a nice WAFA and $d$ the
maximum degree of monomials occurring in $\delta$. Let $q_{n+1}$ be a new
state and

$\delta^{\prime}(q,a)=\begin{cases}\sum\limits_{s{q_{1}}^{k_{1}}\ldots{q_{n}}^{k_{n}}\in
M_{(q,a)}}s\cdot{q_{1}}^{k_{1}}\ldots{q_{n}}^{k_{n}}\cdot
q_{n+1}^{d-\sum_{u=1}^{n}k_{u}}&\text{if }q\in Q\text{ and}\\\
q_{n+1}^{d}&\text{otherwise}\end{cases}$

for all $q\in Q^{\prime}$, $a\in\Sigma$. As well as,

$\tau^{\prime}(q)=\begin{cases}\tau(q)&\text{if }q\in Q\text{ and}\\\
1&\text{if }q=q_{n+1}\end{cases}$

for all $q\in Q^{\prime}$. Clearly,
$\mathcal{A}^{\prime}=(Q\cup\\{q_{n+1}\\},\Sigma,\delta^{\prime},q_{1},\tau^{\prime})$
is equalized. Also, it is easy to see that $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ are equivalent and that $\mathcal{A}^{\prime}$ is nice.

Please note that the coefficients of monomials in $\mathcal{A}$ where not
changed, thus we also can assume that all these coefficients are $1$.

Nice WAFA can be represented in the following way: As usual we depict each
state by a circle. Then, each monomial $s\cdot q_{1}^{k_{1}}\ldots
q_{n}^{k_{n}}$ in $\delta(q_{i},a)$ is represented by a multi-arrow which is
labeled by $a:s$, begins in $q_{i}$, and has $k_{j}$ heads in $q_{j}$ for all
$1\leq j\leq n$, respectively. In case a multi-arrow has more than one head,
we join these heads by a . If $s=1$, we omit the $s$-label. If $s=0$, we omit
the complete multi-arrow. The initial polynomial is represented analogously.
The final weights are represented as usual. Note that the multi-arrows can be
viewed as a parallel or simultaneous transitions and that this representation
coincides with the usual representation if the automaton is a WFA. Consider
the following example:

Let $S=(\mathbb{N},+,\cdot,0,1)$, $\Sigma=\\{a,b\\}$, and $s$ the weighted
language

$\begin{array}[]{llcl}s:&\Sigma^{*}&\rightarrow&S:\\\
&w&\mapsto&\begin{cases}{(2^{j})}^{2^{i}}&\text{if }w=a^{i}b^{j}\enspace,\\\
0&\text{otherwise.}\end{cases}\end{array}$

We consider the WAFA $\mathcal{A}=(\\{q,p\\},\Sigma,P_{0},\delta,\tau)$,
defined by:

$\begin{array}[]{lcllclclcllcl}P_{0}&=&q&&&&&\delta(q,a)&=&{q}^{2}&\delta(q,b)&=&p\\\
\tau(q)&=&1&\tau(p)&=&2&&\delta(p,a)&=&0&\delta(p,b)&=&2\cdot p\end{array}$

A depiction of this automaton can be seen in Figure 2. One can check that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=s$, for example:

$\begin{array}[]{clclcl}&[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](aabb)&=&q\big{\langle}[\mathcal{A}]_{q}(aabb),[\mathcal{A}]_{p}(aabb)\big{\rangle}&&\\\
=&[\mathcal{A}]_{q}(aabb)&=&q^{2}\big{\langle}[\mathcal{A}]_{q}(aabb),[\mathcal{A}]_{p}(aabb)\big{\rangle}&&\\\
=&\big{(}[\mathcal{A}]_{q}(abb)\big{)}^{2}&=&\big{(}[\mathcal{A}]_{q}(bb)\big{)}^{2\cdot
2}&=&\big{(}[\mathcal{A}]_{p}(b)\big{)}^{2\cdot 2}\\\
=&\big{(}2\cdot[\mathcal{A}]_{p}(\varepsilon)\big{)}^{2\cdot
2}&=&\big{(}2\cdot\tau(p)\big{)}^{2\cdot 2}&=&{(2^{2})}^{2^{2}}\end{array}$

$q$$1$$p$$2$$h_{1}$$1$$b$$a$$b$:$2$ Figure 1. Representation of $\mathcal{A}$

$q$$1$$p$$2$$h_{1}$$1$$b$$a$$\Sigma$$b$:$2$ Figure 2. Representation of
equalized, nice $\mathcal{A}$

Two-mode alternating automata are a subclass of alternating automata. In a
two-mode alternating automaton each state $q$ is either existential
($\delta(q,a)=\sum_{i=1}^{n}s^{a}_{i}\cdot q_{i}$ for all $a\in\Sigma$) or
universal ($\delta(q,a)=s^{a}\cdot q_{1}^{k_{1}}\cdot\ldots\cdot
q_{n}^{k_{n}}$ for all $a\in\Sigma$). In [KM18] run semantics were defined for
two-mode alternating automata. However, they can be defined for alternating
automata with mixed states, in an analogue fashion. Here, we give the
definition of runs for nice WAFA. For one, as seen above, we can transform
every WAFA into a nice one. For another, it is only a technicality to define
runs for arbitrary WAFA, based on the definition below.

Let $\mathcal{A}=(Q,\Sigma,\delta,q_{1},\tau)$ be a nice WAFA, we define the
ranked alphabet $\Gamma_{\mathcal{A}}=\\{(q,x)\in Q\times S\langle
Q\rangle\mid x=\tau(q)\text{ or }x\in M_{(q,a)}\text{ for some }a\in\Sigma\\}$
where $\operatorname{Rank}(q,x)$ is the rank of $x$ as a polynomial. A run
over $w=a_{1}\ldots a_{n}$ in $\mathcal{A}$ is a $\Gamma_{\mathcal{A}}$-tree
$t_{\mathcal{R}}$ with the following properties:

  1. (1)

If $|p|=0$, then $t_{\mathcal{R}}(p)=(q_{1},x)$.

  2. (2)

If $|p|<n$ and $t_{\mathcal{R}}(p)=(q,s\cdot q_{1}^{k_{1}}\cdot\ldots\cdot
q_{n}^{k_{n}})$, then $s\cdot q_{1}^{k_{1}}\cdot\ldots\cdot q_{n}^{k_{n}}\in
M_{(q,a_{|p|+1})}$ and $t_{\mathcal{R}}(pi)=(q_{l},x)$ for all
$\sum_{u=1}^{l-1}k_{u}\leq i<\sum_{u=1}^{l}k_{u}$.

  3. (3)

If $|p|=n$, then $\operatorname{Rank}(t_{\mathcal{R}}(p))=0$.

The idea of reading monomials as multi-transitions was already introduced
above. Having this in mind, a run tree is a tree labeled by states such that:
$(i)$ Our run begins in the initial state, $(ii)$ if a vertex at depth $k$ is
$q$ labeled, then the labels of its children fit the states of an $a_{k}$
labeled multi-transition beginning in state $q$, and $(iii)$ our run halts
after $n$ steps.

The weight of a run tree $t_{\mathcal{R}}$ is defined by

$\operatorname{Weight}(t_{\mathcal{R}})=\hskip
40.0pt\prod_{\mathclap{(q,s\cdot q_{1}^{k_{1}}\cdot\ldots\cdot
q_{n}^{k_{n}})\in
t_{\mathcal{R}}(\operatorname{Pos}(t_{\mathcal{R}}))}}s\enspace.$

Note that the final weights are accounted for, since they are the labels of
the leaves of our run tree.

And as usual we have (Theorem 5.15 & Theorem 5.17 in [KM18]):

$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=\sum_{t_{\mathcal{R}}\text{ run
over }w}\operatorname{Weight}(t_{\mathcal{R}})\enspace.$

Later we will use the connection between WAFA and trees heavily. For a better
understanding of this connection we want to point out the following:

First of, let us observe that $|M_{(q,a)}|=1$ if $\delta(q,a)$ is a monomial.
Consequently, if $\delta(q,a)$ is a monomial for all $q\in Q,a\in\Sigma$, then
every run is unique. We call a WAFA with this property universal. Universality
for WAFA is as determinism for finite automata. However, in general universal
WAFA and WFA are incomparable it terms of expressive power (cf. Corollary 3 in
[AK11]).

Second, we consider the non-universal automaton from Figure 4. This automaton
is not universal since $\delta(q,a)=q+p$. As a consequence, we may have
several runs, whenever the letter $a$ is to be processed in stat $q$ we can
choose one of two possible children in our tree. Figure 4 shows these run-
trees for the input $aba$. This connection becomes more clear, if we observe
the behavior of the automaton on $aba$:

$q\overset{a}{\rightarrow}q+p\overset{b}{\rightarrow}(q\cdot
p)+(q)\overset{a}{\rightarrow}((q+p)\cdot p)+(q+p)=q\cdot p+p\cdot p+q+p$

Clearly, every monomial in the final polynomial correspond to one of the run-
trees and since the weight of a run-tree is just the product of the
coefficients in its nodes and its leave correspond to the final weights of
their state, we get that the sum of all run-weights is the behavior of the
automaton.

$q$$p$112$a$$b$$a$$b$$a$ Figure 3. A non-universal WAFA

$(q,q)$$(q,q\cdot p)$$(q,q)$$(p,p)$$(q,1)$$(p,2)$$(q,q)$$(q,q\cdot
p)$$(q,p)$$(p,p)$$(p,2)$$(p,2)$$(q,p)$$(p,q)$$(q,q)$$(q,1)$$(q,p)$$(p,q)$$(q,p)$$(q,2)$
Figure 4. Runs of WAFA from Figure 4 on $aba$

It is easy to see that $s$ from Example 3 is not recognizable by a WFA. Thus,
WAFA are more expressive than WFA when weights are taken from the non-negative
integers. However, this is not the case for every semiring. A semiring $S$ is
locally finite if for every finite $X\subseteq S$ the generated subsemiring
$\langle X\rangle$ is finite. The following result characterizes semirings on
which WAFA and WFA are equally expressive:

######  Theorem 3 (Theorem 7.1 in [KM18]).

The class of $S$-weighted $\Sigma$-languages recognizable by WAFA and the
class of $S$-weighted $\Sigma$-languages recognizable by WFA are equal if and
only if $S$ is locally finite.

##  4\. A characterization of WAFA via weighted finite tree automata

Our central result Theorem 6 is included in this section, as well as the
definition for weighted finite tree automata.

The connection between alternating automata and trees is well known. Often
trees are used to define the runs of alternating automata. As seen above, this
is possible for WAFA too. We want to strengthen this connection by the use of
tree automata and tree homomorphisms. In order to do so, we need some
additional definitions.

An element $r\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is called ($S$-weighted) tree language.
A weighted finite tree automaton (WFTA) is a 4-tuple
$\mathcal{A}=(Q,\Gamma,\delta,\lambda)$, where $Q=\\{q_{1},\ldots,q_{n}\\}$ is
a finite set of states, $\Gamma$ is a ranked alphabet, $\delta=(\delta_{k}\mid
1\leq k\leq\operatorname{Rank}(\Gamma))$ is a family of transition functions
$\delta_{k}:\Gamma^{(k)}\rightarrow S^{Q^{k}\times Q}$, and
$\lambda:Q\rightarrow S$ a root weight function.

If $k$ is clear from the context, we will denote tuples $(p_{1},\ldots,p_{k})$
by $\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu$. Moreover,
since $k$ in $\delta_{k}(g)$ is clear from $g$, we will denote $\delta_{k}(g)$
by $\delta_{g}$.

Let $\mathcal{A}=(Q,\Gamma,\delta,\lambda)$ be a WFTA. Its state behavior
$[\mathcal{A}]:Q\times T_{\Gamma}\rightarrow S$ is the mapping defined by

$[A]\big{(}q,g(t_{1},\ldots,t_{k})\big{)}=\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod_{i=1}^{k}[\mathcal{A}](p_{i},t_{i})\enspace.$

Usually, we will write $[\mathcal{A}]_{q}(t)$ instead of $[\mathcal{A}](q,t)$.
Now, the behavior of $\mathcal{A}$ is the weighted tree language
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]:T_{\Gamma}\rightarrow S$ defined by

$[\mkern-3.0mu[A]\mkern-3.0mu](t)=\sum_{i=1}^{n}\lambda(q_{i})\cdot[\mathcal{A}]_{q_{i}}(t)\enspace.$

A weighted tree language $s$ is recognized by $\mathcal{A}$ if and only if
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=s$.

It is well known that a word over $\Sigma$ can be represented as a $1$-ary
tree: Each letter of $\Sigma$ is given rank one and a new end-symbol $\\#$ of
rank zero is added. Then $w_{0}w_{1}\ldots w_{n}$ translates to the tree
$w_{0}(w_{1}(\ldots w_{n}(\\#)\ldots))$. Here, we want to represent words as
full $r$-ary trees for any arbitary $r\in\mathbb{N}$. Given an alphabet
$\Sigma$ and $r\geq 1$, we define the ranked alphabet
$\Sigma_{\\#}^{r}=\Sigma\cup\\{\\#\\}$ with $\operatorname{Rank}(\\#)=0$ and
$\operatorname{Rank}(a)=r$ for all $a\in\Sigma$. For all $w\in\Sigma^{*}$ the
tree $t_{w}^{r}\in T_{\Sigma_{\\#}^{r}}$ is defined by
$t^{r}_{\varepsilon}=\\#$; and $t^{r}_{w}=a(t^{r}_{v},\ldots,t^{r}_{v})$ if
$w=av$ with $a\in\Sigma$. We call $h^{r}:\Sigma^{*}\rightarrow
T_{\Sigma_{\\#}^{r}}:w\mapsto t_{w}^{r}$ the generic tree homomorphism (of
rank $r$). The case $r=1$ is special since for all $t\in T_{\Sigma_{\\#}^{1}}$
there exists $w\in\Sigma^{*}$ such that $t=t_{w}^{1}$. Therefore, if clear
from the context, we will identify $\Sigma$ and $\Sigma_{\\#}^{1}$,
$\Sigma^{*}$ and $T_{\Sigma_{\\#}^{1}}$, as well as $w$ and $t_{w}^{1}$. It is
well known that a weighted $\Sigma$ language is recognizable by a WFA over
$\Sigma$ if and only if it is recognizable by a WFTA over $\Sigma_{\\#}^{1}$.

The key observation is that the behavior of a WAFA $\mathcal{A}$ on $w$ can be
characterized by the behavior of a WFTA on $t_{w}^{r}$ where $r$ is the degree
of polynomials in an equalized version of $\mathcal{A}$. Even more, the
behavior of a WFTA on $h(w)$ (where $h$ is a tree homomorphism) can be
characterized by the behavior of a WAFA on $w$.

######  Lemma 4.

If $s\in S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ is
recognized by a WAFA, then $s=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ
h^{r}$ for some WFTA $\mathcal{B}$ and $r\in\mathbb{N}$.

######  Proof 4.1.

Assume $s$ is recognized by a WAFA. Due to Lemma 1 and Lemma 2, we may assume
that $s$ is recognized by a nice and equalized WAFA
$\mathcal{A}=(Q,\Sigma,\alpha,P_{0},\tau)$. Let $r$ be the unique degree of
monomials in $\mathcal{A}$. Our goal is to define a WFTA $\mathcal{B}$ with
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ
h^{r}$. To this purpose, we observe that the equalized $\mathcal{A}$ can be
viewed as a WFTA over a ranked alphabet where each letter has rank $r$ and
where each multi-arrow in the representation of $\mathcal{A}$ corresponds to
one transition in $\mathcal{B}$. Formally, we define the WFTA
$\mathcal{B}=(Q,\Sigma^{r}_{\\#},\beta,\lambda)$ with
$\lambda=\mathbb{1}_{\\{q_{1}\\}}$ and

$\begin{array}[]{lcl}\beta_{\\#}(\varepsilon,q)&=&\tau(q)\enspace,\\\
\beta_{a}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)&=&\begin{cases}s&\text{if }s\cdot p_{1}\cdot\ldots\cdot p_{r}\in
M_{(q,a)}\enspace,\\\ 0&\text{otherwise}\enspace.\end{cases}\end{array}$

Please note that the order of $p_{1},\ldots,p_{r}$ is of importance. Thus, due
to the fact that $\mathcal{A}$ is nice, $\beta_{a}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,q)$ becomes always zero
if the $p_{i}$ are not ordered according to the linear order on the states of
$\mathcal{A}$.

Now, we will show that $[\mathcal{A}]_{q}(w)=[\mathcal{B}]_{q}(t_{w}^{r})$ for
all $q\in Q$ and $w\in\Sigma^{*}$ by induction on $|w|\in\mathbb{N}$. If
$|w|=0$, then $w=\varepsilon$. Thus,
$[\mathcal{A}]_{q}(w)=\tau(q)=\beta_{\\#}(\varepsilon,q)=[\mathcal{B}]_{q}(t^{r}_{w})$
for all $q\in Q$. Assume there exists $l\in\mathbb{N}$ such that the claim
holds for all $w^{\prime}\in\Sigma^{l}$ and all $q\in Q$. For the induction
step let $w=aw^{\prime}\in\Sigma\cdot\Sigma^{l}$. For $\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in Q^{k}$ let
$k_{i}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu)$ denote
the number of $q_{i}$’s in $\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu$. Then, we get

$\begin{array}[]{cl}&[\mathcal{A}]_{q}(w)\\\
=&\alpha(q,a)\langle[\mathcal{A}]_{q_{1}}(w^{\prime}),\ldots,[\mathcal{A}]_{q_{n}}(w^{\prime})\rangle\\\
\overset{\mathclap{\textup{(IH)}}}{=}&\alpha(q,a)\langle[\mathcal{B}]_{q_{1}}(t^{r}_{w^{\prime}}),\ldots,[\mathcal{B}]_{q_{n}}(t^{r}_{w^{\prime}})\rangle\\\
=&\sum\limits_{s\cdot q_{1}^{k_{1}}\ldots q_{n}^{k_{n}}\in
M_{(q,a)}}s\cdot\prod\limits_{i=1}^{n}{\big{(}[\mathcal{B}]_{q_{i}}(t^{r}_{w^{\prime}})\big{)}}^{k_{i}}\\\
=&\sum\limits_{s\cdot q_{1}^{k_{1}}\ldots q_{n}^{k_{n}}\in
M_{(q,a)}}\beta_{a}(\overbrace{\underbrace{q_{1},\ldots,q_{1}}_{k_{1}\text{
times}},\ldots,\underbrace{q_{n},\ldots,q_{n}}_{k_{n}\text{ times}}}^{\sum
k_{i}=r\text{
times}},q)\cdot\prod\limits_{i=1}^{n}{\big{(}[\mathcal{B}]_{q_{i}}(t^{r}_{w^{\prime}})\big{)}}^{k_{i}}\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{r}}\beta_{a}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{n}{\big{(}[\mathcal{B}]_{q_{i}}(t^{r}_{w^{\prime}})\big{)}}^{k_{i}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu)}\\\
=&[\mathcal{B}]_{q}\big{(}a(\underbrace{t^{r}_{w^{\prime}},\ldots,t^{r}_{w^{\prime}}}_{r\text{
times}})\big{)}\\\ =&[\mathcal{B}]_{q}(t_{w}^{r})\end{array}$

for all $q\in Q$. Which completes our induction.

Since $\mathcal{A}$ is nice and thus $P_{0}=q_{1}$, we consequently have

$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=[\mathcal{A}]_{q_{1}}(w)=[\mathcal{B}]_{q_{1}}(t_{w}^{r})=\sum_{i=1}^{n}\lambda(q_{i})\cdot[\mathcal{B}]_{q_{i}}(t_{w}^{r})=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](t_{w}^{r})$

for all $w\in\Sigma^{*}$. Since $h^{r}(w)=t_{w}^{r}$, this finishes our proof.

The following example illustrates this connection between WAFA and WFTA.

We consider the automaton $\mathcal{A}$ from Example 3. It is easy to
construct the corresponding WFTA $\mathcal{B}=(Q,\Gamma,\beta,\lambda)$ from
the equalized version $\mathcal{A}^{\prime}$ (Figure 2). First, we copy the
set of states (in order) $Q=\\{q,p,h_{1}\\}$. Since the maximum degree of
polynomials in $\mathcal{A}$ was $2$ we get
$\Gamma=\\{a^{(2)},b^{(2)},{\\#}^{(0)}\\}$. The root weight function
corresponds to the initial weights. However, $\mathcal{A}^{\prime}$ is nice
and thus $\lambda=\mathbb{1}_{\\{q\\}}$. The transition weight functions
$\beta_{a}$ and $\beta_{b}$ can be defined using the multi arrows in Figure 2.
For example, the $b$-labeled multi arrow in the middle corresponds to
$\beta_{b}(ph_{1},q)=1$. Finally, the final weights in $\mathcal{A}^{\prime}$
are captured by
$\beta_{\\#}(\varepsilon,q)=1,\beta_{\\#}(\varepsilon,h_{1})=1$, and
$\beta_{\\#}(\varepsilon,p)=2$. The only non-zero run on $t^{2}_{ab}$ can be
seen in Figure 5.

#ba$1$$q$$q$$q$$p$$h_{1}$$p$$h_{1}$$2$$1$$2$$1$$2$$2$$1$ Figure 5. Run of
translated WFTA on $t^{2}_{ab}$

######  Lemma 5.

Let $\mathcal{B}=(Q,\Gamma,\delta,\lambda)$ a WFTA and
$h:\Sigma^{*}\rightarrow T_{\Gamma}$ a tree homomorphism, then
$[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ h$ is recognized by a WAFA.

######  Proof 4.2.

Assume $s=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ h\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$, where
$\mathcal{B}=(Q,\Gamma,\delta,\lambda)$ is a WFTA with $|Q|=n$ and
$h:\Sigma^{*}\rightarrow T_{\Gamma}$ a tree homomorphism. We want to construct
a WAFA $\mathcal{A}$ such that $[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=s$.

If $h$ would be the generic homomorphism, we could define
$\delta^{\prime}(q,a)=\sum_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{r}}\delta_{a}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)$ and use the same proof as in the first direction. However, we want
to prove this for arbitrary homomorphisms. To achieve this, we give some
additional definitions.

Under $h$, each letter becomes a tree. Nonetheless, we are not interested in
the structure of $h(a)$, but want to handle it as if it is a ranked letter.
Therefore, we use $h(a)\langle x_{1}\leftarrow(p_{1},\ldots,p_{r})\rangle$ to
disambiguate its $r=\operatorname{r}(h(a))$ variables. Furthermore, we extend
the family of transition functions $(\delta_{k})_{0\leq
k\leq\operatorname{Rank}{\Gamma}}$ into a family
$(\delta^{\prime}_{k})_{k\in\mathbb{N}}$ with
$\delta^{\prime}_{k}:T_{\Gamma}^{(k)}(\\{x_{1}\\})\rightarrow S^{Q^{k}\times
Q}$. We use the same notations for $\delta^{\prime}$ as for $\delta$ and
define $\delta^{\prime}_{k}$ recursively as follows.

  1. (1)

For all $g\in\Gamma^{(0)}$ let
$\delta^{\prime}_{g}(\varepsilon,q)=\delta_{g}(\varepsilon,q)$ for all $q\in
Q$,

  2. (2)

$\delta^{\prime}_{x_{1}}(p,q)=\mathbb{1}_{\\{q\\}}(p)$ for all $(p,q)\in
Q\times Q$, and

  3. (3)

if $t=g(t_{1},\ldots,t_{k})$ for some $g\in\Gamma^{(k)}$, we define

$\delta^{\prime}_{t}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{1},\ldots,\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{k},q)=\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu^{\prime}\in
Q^{k}}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\prod_{i=1}^{k}\delta^{\prime}_{t_{i}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i},p^{\prime}_{i})\enspace$

for all $(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{1},\ldots,\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{k},q)\in Q^{\operatorname{r}(t_{1})}\times\ldots\times
Q^{\operatorname{r}(t_{k})}\times Q$.

Please note, for $t\in T_{\Gamma}$ we have
$\delta^{\prime}_{t}(\varepsilon,q)=[\mathcal{A}]_{q}(t)$ by definition.

Now, we are well equipped to define the WAFA
$\mathcal{A}=(Q,\Sigma,\alpha,P_{0},\tau)$. Let
$P_{0}=\sum_{i=1}^{n}{\lambda(q_{i})\cdot q_{i}}$,
$\tau(q_{i})=\delta^{\prime}_{h(\\#)}(\varepsilon,q_{i})$ for all $1\leq i\leq
n$, and $\alpha(q,a)=\sum_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{\operatorname{r}(h(a))}}{\delta^{\prime}_{h(a)}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod_{i=1}^{\operatorname{r}(h(a))}p_{i}}$ for all $q\in Q$,
$a\in\Sigma$.

Next, we show $[\mathcal{B}]_{q}(h(w))=[\mathcal{A}]_{q}(w)$ for all $q\in Q$,
$w\in\Sigma^{*}$. Again, by induction on $|w|\in\mathbb{N}$. Before we can do
so, we have to prove the following auxiliary claim about $\delta^{\prime}$.
Let $\mathcal{A}=(Q,\Gamma,\delta,\lambda)$ be a WFTA, $t\in T_{\Gamma}$,
$\hat{t}\in T_{\Gamma\cup\\{x_{1}\\}}$, and $t_{1},\ldots,t_{k}\in T_{\Gamma}$
such that $t=\hat{t}\langle x_{1}\leftarrow(t_{1},\ldots,t_{k})\rangle$, then

$[\mathcal{A}]_{q}(t)=\sum_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\delta^{\prime}_{\hat{t}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod_{i=1}^{k}[\mathcal{A}]_{p_{i}}(t_{i})$

for all $q\in Q$.

######  Proof 4.3.

We prove this claim via induction on the depth of $\hat{t}$. The claim is
clear if $k=0$. Therefore, we assume $k>0$. If $\hat{t}=x_{1}$, we know
$t=t_{1}$ and get

$\begin{array}[]{ll}&[\mathcal{A}]_{q}(t)\\\ =&\sum_{p\in
Q}\mathbb{1}_{\\{q\\}}(p)\cdot[\mathcal{A}]_{p}(t_{1})\\\ =&\sum_{p\in
Q}\delta^{\prime}_{x_{1}}(p,q)\cdot[\mathcal{A}]_{p}(t_{1})\enspace.\end{array}$

Now, assume the claim holds for all $\hat{t}\in T_{\Gamma}$ with depth $\leq
n$ for some $n\in\mathbb{N}$. Assume $\hat{t}$ has depth $n+1$ and
$\hat{t}=g(\hat{t}_{1},\ldots,\hat{t}_{r})$ for some $g\in\Gamma^{(r)}$ and
$\hat{t}_{1},\ldots,\hat{t}_{r}\in T_{\Gamma\cup\\{x_{1}\\}}$. Of the $k$
trees only the first $\operatorname{r}(\hat{t}_{1})$ will be substituted in
$\hat{t}_{1}$, only the second $\operatorname{r}(\hat{t}_{2})$ will be
substituted in $\hat{t}_{1}$, and so on. To mark this, let
$k(i)=\sum_{l=1}^{i}\operatorname{r}(\hat{t}_{l})$, $\mkern
1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu_{i}=(t_{k(i-1)+1},\ldots,t_{k(i)})$, and $\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i}=(p_{k(i-1)+1},\ldots,p_{k(i)})$ for all $1\leq i\leq r$. We get:

$\begin{array}[]{ll}&[\mathcal{A}]_{q}(t)\\\ =&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu^{\prime}\in
Q^{r}}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\prod\limits_{i=1}^{r}[\mathcal{A}]_{p^{\prime}_{i}}(\hat{t}_{i}\langle
x_{1}\leftarrow\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu_{i}\rangle)\\\ \overset{\mathclap{\textup{(IH)}}}{=}&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu^{\prime}\in
Q^{r}}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\prod\limits_{i=1}^{r}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu_{i}\in
Q^{\operatorname{r}(\hat{t}_{i})}}\delta^{\prime}_{\hat{t}_{i}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i},p^{\prime}_{i})\cdot\prod\limits_{j=r(i-1)+1}^{r(i)}[\mathcal{A}]_{p_{j}}(t_{j})\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime}\in Q^{r}}\delta_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\sum\limits_{(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu_{1},\ldots,\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu_{r})\in
Q^{k}}\prod\limits_{i=1}^{r}\big{(}\delta^{\prime}_{\hat{t}_{i}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i},p^{\prime}_{i})\big{)}\cdot\prod\limits_{j=1}^{k}[\mathcal{A}]_{p_{j}}(t_{j})\\\
=&\sum\limits_{(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{1},\ldots,\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{r})\in Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu^{\prime}\in
Q^{r}}\Big{(}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\prod\limits_{i=1}^{r}\big{(}\delta^{\prime}_{\hat{t}_{i}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i},p^{\prime}_{i})\big{)}\cdot\prod\limits_{j=1}^{k}[\mathcal{A}]_{p_{j}}(t_{j})\Big{)}\\\
=&\sum\limits_{(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{1},\ldots,\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{r})\in Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu^{\prime}\in
Q^{r}}\Big{(}\delta_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu^{\prime},q)\cdot\prod\limits_{i=1}^{r}\big{(}\delta^{\prime}_{\hat{t}_{i}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{i},p^{\prime}_{i})\big{)}\Big{)}\cdot\prod\limits_{j=1}^{k}[\mathcal{A}]_{p_{j}}(t_{j})\\\
=&\sum\limits_{(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{1},\ldots,\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{r})\in Q^{k}}\delta^{\prime}_{\hat{t}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu_{1},\ldots,\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu_{r},q)\cdot\prod\limits_{j=1}^{k}[\mathcal{A}]_{p_{j}}(t_{j})\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\delta^{\prime}_{\hat{t}}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{j=1}^{k}[\mathcal{A}]_{p_{j}}(t_{j})\end{array}$

This finishes the proof of our claim.

We return to our main proof. If $|w|=0$, then $w=\varepsilon$. Therefore,
$[\mathcal{B}]_{q}(w)=\tau(q)=\delta^{\prime}_{h(\\#)}(\varepsilon,q)\overset{*}{=}[\mathcal{A}]_{q}(h(w))$.
Here $*$ holds due to Claim 4.2 with $k=0$ and $\hat{t}=t=h(\\#)$. Assume
there exists some $l\in\mathbb{N}$ such that
$[\mathcal{B}]_{q}(h(w))=[\mathcal{A}]_{q}(w)$ for all $q\in Q$,
$w\in\Sigma^{l}$. For the induction step let
$w=aw^{\prime}\in\Sigma\cdot\Sigma^{l}$ and $k=\operatorname{r}(h(a))$.
Similar to the first direction, we have

$\begin{array}[]{ll}&[\mathcal{A}]_{q}(aw^{\prime})\\\ =&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\delta^{\prime}_{h(a)}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\prod\limits_{i=1}^{k}[\mathcal{A}]_{p_{i}}(w^{\prime})\\\
\overset{\mathclap{\textup{(IH)}}}{=}&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\delta^{\prime}_{h(a)}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\prod\limits_{i=1}^{k}[\mathcal{B}]_{p_{i}}(h(w^{\prime}))\\\
\overset{\mathclap{\text{Claim
}\ref{clm:aux1}}}{=}&[\mathcal{B}]_{q}(h(a)\langle h(w^{\prime})\rangle)\\\
=&[\mathcal{B}]_{q}(h(w))\end{array}$

for all $q\in Q$. Via induction, this finishes our proof of the second
direction.

Finally, for all $w\in\Sigma^{*}$ we get:

$[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](h(w))=\sum_{i=1}^{n}\lambda(q_{i})\cdot[\mathcal{B}]_{q_{i}}(h(w))=\sum_{i=1}^{n}\lambda(q_{i})\cdot[\mathcal{A}]_{q_{i}}(w)=P_{0}\langle[\mathcal{B}^{\prime}]_{q_{1}}(w),\ldots,[\mathcal{A}]_{q_{n}}(w)\rangle=[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)$

This leads us to our main result.

######  Theorem 6.

A weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ is recognized
by a WAFA if and only if there exists a ranked alphabet $\Gamma$, a tree
homomorphism $h:\Sigma^{*}\rightarrow T_{\Gamma}$, and a WFTA
$\mathcal{A}=(Q,\Gamma,\delta,\lambda)$ such that
$s=[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]\circ h$.

######  Proof 4.4.

This is an immediate consequence of Lemma 4 and Lemma 5.

This result allows us to transfer results from WFTA to WAFA. Moreover,
additional observations in the proofs show that one can give a weight
preserving, bijective mapping between the runs of $\mathcal{A}$ and
$\mathcal{B}$. This allows us to translate results about runs of WFTA into
results of runs of WAFA.

######  Corollary 7.

Non-weighted alternating automata and finite automata are equally expressive.

This result goes back to [CKS81]. However, it is well known that the non-
weighted setting corresponds to the weighted setting, if weights are taken
from the Boolean semiring. We observe that $\mathbb{1}_{L}\circ
h=\mathbb{1}_{h^{-1}(L)}$ for any tree language $L\subseteq T_{\Lambda}$ and
tree homomorphism $h:T_{\Gamma}\rightarrow T_{\Lambda}$. Assume
$\mathbb{1}_{L}$ is recognized by a WAFA. By Lemma 4, we get
$\mathbb{1}_{L}=\mathbb{1}_{L^{\prime}}\circ h=\mathbb{1}_{h^{-1}(L)}$ with
$h=h^{r}$ for some $r\in\mathbb{N}$ and $L^{\prime}\subseteq
T_{\Sigma^{r}_{\\#}}$ regular. Since regular tree languages are closed under
inverses of homomorphisms and since WFA and WFTA are equally expressive over
$\Sigma_{\\#}^{1}$, we get that $\mathbb{1}_{L}$ is recognized by a WFA. The
authors in [CKS81] also show that the translation of an alternating finite
automaton into an equivalent deterministic finite automaton leads to (worst
case) a doubly exponential blowup in states. By our proof we can see that one
exponent is needed to determinize $\mathcal{B}$ (from the Proof of Lemma 4)
and one exponent is needed to determinize the nondeterministic finite
automaton recognizing $[\mkern-3.0mu[B]\mkern-3.0mu]\circ h$ (the construction
of the automaton recognizing $[\mkern-3.0mu[B]\mkern-3.0mu]\circ h$ itself is
linear in states).

##  5\. A Nivat theorem for WAFA

This section leads to the Nivat-like characterization of WAFA (Theorem 13),
but first we will prove that weighted languages recognized by WAFA are closed
under inverses of homomorphisms (Corollary 9), but not under homomorphisms
(Lemma 10).

Let $s_{1}\odot s_{2}$ denote the Hadamard product (pointwise product) of two
weighted languages $s_{1},s_{2}\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$. Furthermore,
a word homomorphism $h:\Gamma^{*}\rightarrow\Sigma^{*}$ is called non-deleting
if and only if $h(a)\neq\varepsilon$ for all $a\in\Sigma$. Let $r\in
S\langle\mkern-4.0mu\langle\Gamma^{*}\rangle\mkern-4.0mu\rangle$. For
$h:\Gamma^{*}\rightarrow\Sigma^{*}$ a non-deleting homomorphism, we define
$h(r)\in S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ by
$h(r)(w)=\sum_{v\in h^{-1}(w)}r(v)$ for all $w\in\Sigma^{*}$. For
$h:\Sigma^{*}\rightarrow\Gamma^{*}$ we define $h^{-1}(r)\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ by
$h^{-1}(r)(w)=r(h(w))$ for all $w\in\Sigma^{*}$. Note that we have
$h(\mathbb{1}_{L})(w)=1$ if and only if there exists $v\in\Gamma^{*}$ with
$h(v)=w$ and $v\in L$ in the boolean setting. Thus,
$h(\mathbb{1}_{L})=\mathbb{1}_{h(L)}$. Analogously, we get
$h^{-1}(\mathbb{1}_{L})=\mathbb{1}_{h^{-1}(L)}$. Hence, $h(r)$ corresponds to
the application of a homomorphism, while $h^{-1}(r)$ corresponds to the
application of the inverse of a homomorphism in the non-weighted setting.

The original Nivat Theorem [Niv68] characterizes word-to-word transducers. A
generalized version for WFA over arbitrary semirings (Theorem 6.3 in [DKar])
can be stated in the following way:

######  Theorem 8 (Nivat-like theorem for WFA [DKar]).

A weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ is recognized
by a WFA if and only if there exist an alphabet $\Gamma$, a non-deleting
homomorphism $h:\Gamma^{*}\rightarrow\Sigma^{*}$, a regular language
$L\subseteq\Gamma^{*}$, and a WFA $\mathcal{A}_{w}$ with exactly one state
such that:

$s=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})\enspace.$

Please note, $\mathcal{A}_{w}$ does not depend on any input and is called
$\mathcal{A}_{w}$ since it is responsible for the application of weights. Our
goal is, to generalize this result up to WAFA. This Nivat-like theorem is
strongly connected to the closure of weighted languages recognized by WFA
under (inverses) of homomorphisms. Thus, we will investigate these properties
for WAFA.

###  5.1. Closure properties

A class $K$ of $S$-weighted languages is said to be closed under homomorphisms
if $s\in S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle\cap
K$ and $h:\Gamma^{*}\rightarrow\Sigma^{*}$ a homomorphism implies $h(s)\in K$.
Moreover, $K$ is closed under inverses of homomorphisms if $s^{\prime}\in
S\langle\mkern-4.0mu\langle\Gamma^{*}\rangle\mkern-4.0mu\rangle\cap K$ and
$h:\Gamma^{*}\rightarrow\Sigma^{*}$ a homomorphism implies
$h^{-1}(s^{\prime})\in K$. The same notions are used for weighted tree
languages.

The class of weighted languages recognized by WFA is closed under (inverses
of) homomorphisms (Lemma 6.2 in [DKar]). WAFA are also closed under inverses
of homomorphisms. In fact, this is an easy corollary of Lemma 4 and Lemma 5.

######  Corollary 9.

The class of weighted languages recognized by WAFA is closed under inverses of
homomorphisms.

######  Proof 5.1.

Let $h^{\prime}:\Lambda^{*}\rightarrow\Sigma^{*}$ be a homomorphism and $s\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ recognized by
a WAFA. Due to Lemma 4, we get $s=[\mkern-3.0mu[B]\mkern-3.0mu]\circ h^{r}$.
Clearly, $h^{r}\circ h^{\prime}:\Lambda^{*}\rightarrow\Sigma^{r}_{\\#}$ is a
tree homomorphism. Thus, due to Lemma 5,
${h^{\prime}}^{-1}(s)=([\mkern-3.0mu[B]\mkern-3.0mu]\circ h^{r})\circ
h^{\prime}=[\mkern-3.0mu[B]\mkern-3.0mu]\circ(h^{r}\circ h^{\prime})$ is
recognized by a WAFA.

However, the same is not true for the closure under homomorphisms.

######  Lemma 10.

The class of weighted languages recognized by WAFA is not closed under
homomorphisms.

######  Proof 5.2.

Let $\Sigma=\\{a,b,\\#\\}$, $\mathbb{B}$ the Boolean semiring, and
$\mathbb{B}[x]$ the semiring of polynomials in one indeterminate. Consider

$r_{B}:\Sigma^{*}\rightarrow\mathbb{B}[x]:w\mapsto\begin{cases}\sum\limits_{k=0}^{j}x^{ki}&\text{if
}w=a^{i}\\#b^{j}\enspace,\\\ 0&\text{otherwise.}\end{cases}$

Due to Lemma 8.3 from [KM18], we know $r_{B}$ is not recognized by a WAFA. Let
$\Gamma=\\{a,c,d,\\#\\}$, $h:\Gamma^{*}\rightarrow\Sigma^{*}$ the non-deleting
homomorphism induced by $h(a)=a,h(\\#)=\\#,h(c)=h(d)=b$, and

$r_{R}:\Gamma^{*}\rightarrow\mathbb{B}[x]:w\mapsto\begin{cases}x^{ki}&\text{if
}w=a^{i}\\#c^{k}d^{l}\enspace,\\\ 0&\text{otherwise.}\end{cases}$

Then

$\begin{array}[]{llll}h(r_{R})(w)&=\sum\limits_{v\in
h^{-1}(w)}r_{R}(v)&=\begin{cases}\sum\limits_{v\in h^{-1}(w)}r_{R}(v)&\text{if
}w=a^{i}\\#b^{j}\\\ 0&\text{otherwise}\end{cases}&\\\
&=\begin{cases}\sum\limits_{k=0}^{j}r_{R}(a^{i}\\#c^{k}d^{j-k})&\text{if
}w=a^{i}\\#b^{j}\\\
0&\text{otherwise}\end{cases}&=\begin{cases}\sum\limits_{k=0}^{j}x^{ki}&\text{if
}w=a^{i}\\#b^{j}\\\ 0&\text{otherwise}\end{cases}&=r_{B}(w)\end{array}$

for all $w\in\Sigma^{*}$. Thus, $h(r_{R})$ is not recognized by a WAFA. The
weighted language $r_{R}$ is recognized by the WAFA
$\mathcal{A}_{R}=(\\{q_{\iota},q_{1},q_{a},q_{c},q_{d}\\},\\{a,\\#,c,d\\},\delta_{R},q_{\iota},\tau_{R})$
with $\delta_{R}$ and $\tau_{R}$ defined by:

$\begin{array}[]{l|c|c|c|c|c}&q_{\iota}&q_{1}&q_{a}&q_{c}&q_{d}\\\
\hline\cr\delta_{R}(*,a)&q_{\iota}q_{a}&0&q_{a}&0&0\\\
\hline\cr\delta_{R}(*,\\#)&q_{1}&0&q_{c}&0&0\\\
\hline\cr\delta_{R}(*,c)&0&q_{1}&0&x\cdot q_{c}&0\\\
\hline\cr\delta_{R}(*,d)&0&q_{d}&0&q_{d}&q_{d}\\\
\hline\cr\tau_{R}(*)&0&1&0&1&1\\\ \end{array}$

A depiction of $\mathcal{A}_{R}$ can be seen in Figure 6. This completes our
proof.

$q_{\iota}$$q_{1}$$q_{a}$$q_{c}$$q_{d}$$\\#$$a$$\\#$$d$$a$$c$:$x$$d$$c$$d$
Figure 6. WAFA $\mathcal{A}_{R}$

Nonetheless, the proof of the second direction of Theorem 8 relies on the
closure under homomorphisms. Thus, due to Lemma 10, a one to one translation
of Theorem 8 into the framework of alternating automata is prohibited.
Moreover, in the proof of the first direction of Theorem 8, $L$ is defined as
a language of runs of $\mathcal{A}$. As mentioned above, runs of WAFA are
trees. Therefore, we will utilize a Nivat-like theorem for WFTA to prove the
corresponding result for WAFA.

###  5.2. A Nivat-like characterization of WFTA

Nivat-like characterizations for weighted tree languages have been
investigated in the past. Unranked trees were considered in [DG17], while a
very general result for graphs can be found in [DD15]. Here, for the readers
convenience, we want to restate a more restricted version for ranked trees.

Let $h:T_{\Gamma}\rightarrow T_{\Lambda}$ be a non-deleting tree homomorphism,
$s\in S\langle\mkern-4.0mu\langle T_{\Lambda}\rangle\mkern-4.0mu\rangle$. In
analogy to words, we define $h(s)\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ by $h(s)(t)=\sum_{t^{\prime}\in
h^{-1}(t)}s(t^{\prime})$ for all $t\in T_{\Gamma}$. For linear homomorphisms
the following is known:

######  Lemma 11 (Theorem 3.8 in [FV09]).

The class of weighted tree languages recognized by WFTA is closed under linear
homomorphisms.

Based on this, it is easy to prove the following result:

######  Theorem 12 (Nivat-like theorem for WFTA (Theorem 12 in [DG17])).

A weighted tree language $s\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is recognized by a WFTA if and only if
there exist a ranked alphabet $\Lambda$, a linear tree homomorphism
$h:T_{\Lambda}\rightarrow T_{\Gamma}$, a regular tree language $L\subseteq
T_{\Lambda}$, and a WFTA $\mathcal{A}_{w}$ with exactly one state such that:

$s=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})\enspace.$

######  Proof 5.3.

A proof can be found in [DG17]. There, the $\Rightarrow$-direction is proved
based on a WFTA $\mathcal{A}$ recognizing $s$. The components $\Lambda$, $h$,
$L$, and $\mathcal{A}_{w}$ are chosen to be the set of transition in
$\mathcal{A}$, the mapping to the letters in $\Gamma$, the tree language of
runs in $\mathcal{A}$, and an automaton adding weights to the transitions,
respectively. This yields the desired equation. Here, for the convenience of
the reader, we want to give a precise construction, as well as a proof of
correctness for the second direction of the proof of Theorem 12.

Let $s$ be recognized by a WFTA $\mathcal{A}=(Q,\Gamma,\alpha,\lambda)$.
First, we define $\Lambda$. Let $P=Q\cup Q_{\text{fin}}$ where
$Q_{\text{fin}}$ is a disjoint copy of $Q$ including an element
$q_{\text{fin}}$ for each $q\in Q$. Now,
$\Lambda=\bigcup_{i=0}^{\operatorname{Rank}(\Gamma)}Q^{i}\times\Gamma^{(i)}\times
P$. For reasons of readability, we sometimes abbreviate a letter
$\big{(}(q_{1},\ldots,q_{\operatorname{Rank}(g)}),g,p\big{)}\in\Lambda$ by
$[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p]$. We
define $\operatorname{Rank}([\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p])=\operatorname{Rank}(g)$. Let $h$ be the tree homomorphism induced
by $h\big{(}[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p](x_{1},\ldots,x_{k})\big{)}=g(x_{1},\ldots,x_{k})$ for all
$g\in\Gamma^{(k)}$. Clearly, $h$ is linear and non-deleting.

Next, we consider the WFTA $\mathcal{B}$ with weights taken from the Boolean
semiring $\mathbb{B}$. Let
$\mathcal{B}=(P,\Lambda,\beta,\mathbb{1}_{Q_{\text{fin}}})$ with $\beta$
defined by

$\beta_{[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p]}(\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu^{\prime},p^{\prime})=\begin{cases}1&\text{if }[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu^{\prime},g,p^{\prime}]=[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p]\enspace,\\\
0&\text{otherwise}\end{cases}$

for all $[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p]\in\Lambda$, $(\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu^{\prime},p^{\prime})\in
Q^{k+1}$. Clearly, $[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]=\mathbb{1}_{L}$,
for some tree language $L\subseteq T_{\Lambda}$. It is well known, that the
support of a recognizable $\mathbb{B}$-weighted weighted tree language is a
recognizable tree language (cf. Lemma 3.11 & Theorem 3.12 in [FV09]). Hence,
$L$ is a recognizable tree language.

Finally, we define the WFTA
$\mathcal{A}_{w}=(\\{q_{w}\\},\Lambda,\omega,\mathbb{1}_{\\{q_{w}\\}})$ with

$\omega_{[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p]}\big{(}(\underbrace{q_{w},\ldots,q_{w}}_{\operatorname{Rank}(g)\text{
times}}),q_{w}\big{)}=\begin{cases}\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,q^{\prime})&\text{if
}p=q^{\prime}\in Q\\\ \alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,q^{\prime})\cdot\lambda(q^{\prime})&\text{if
}p=q^{\prime}_{\text{fin}}\in Q_{\text{fin}}\end{cases}$

for all $[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p]\in\Lambda$. Please note that
$[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]=[\mathcal{A}_{w}]_{q_{w}}$. Thus,
we will not distinguish between those two semantics.

To prove that

$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=h^{-1}\circ([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})$

holds for this construction, we will prove the following claim first.

For all $q\in Q$ it holds
$[\mathcal{A}]_{q}(t)=\big{(}h^{-1}\circ([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q})\big{)}(t)$
for all $t\in T_{\Gamma}$.

######  Proof 5.4.

The proof is by induction on the depth of $t$. If $t=g$ for some
$g\in\Gamma^{(0)}$, we get

$\begin{array}[]{ll}&[\mathcal{A}]_{q}(t)\\\ =&\alpha_{g}(\varepsilon,q)+0\\\
=&\sum\limits_{p\in
Q}\big{(}\alpha_{g}(\varepsilon,p)\cdot\mathbb{1}_{\\{q\\}}(p)\big{)}+\sum\limits_{p_{\text{fin}}\in
Q_{\text{fin}}}\big{(}\alpha_{g}(\varepsilon,p)\cdot\lambda(p)\cdot\mathbb{1}_{\\{q\\}}(p_{\text{fin}})\big{)}\\\
=&\sum\limits_{[\varepsilon,g,p]\in\Lambda^{(0)}}[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]_{w}([\varepsilon,g,p])\cdot[\mathcal{B}]_{q}([\varepsilon,g,p])\\\
=&\sum\limits_{t^{\prime}\in
h^{-1}(g)}\big{(}[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]_{w}\odot[\mathcal{B}]_{q}\big{)}(t^{\prime})\\\
=&\big{(}h^{-1}\circ([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q})\big{)}(g)\end{array}$

for all $q\in Q$.

Assume the claim holds for all $t\in T_{\Gamma}$ of depth lower or equal to
$n$ for some $n\in\mathbb{N}$.

We consider some $t\in T_{\Gamma}$ of depth $n+1$. There exist
$g\in\Gamma^{(k)}$ and $t_{1},\ldots,t_{k}\in T_{\Gamma}$ such that
$t=g(t_{1},\ldots,t_{k})$. Clearly, $t_{i}$ has a depth lower or equal to $n$
for all $1\leq i\leq k$. Let us denote the tuple $(t_{1},\ldots,t_{k})$ by
$\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern 1.5mu$ and
$h^{-1}(t_{1})\times\ldots\times h^{-1}(t_{k})$ by $h^{-1}(\mkern
1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern 1.5mu)$. First, we observe

$t^{\prime}\in h^{-1}(t)\Leftrightarrow t^{\prime}=[\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,g,q](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)$

for some $q\in P$, $\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu\in Q^{k}$, and $\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern 1.5mu)$.
Moreover, we have

$[\mathcal{B}]_{q}\big{(}[\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,g,q^{\prime}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu)\big{)}=1\Leftrightarrow q=q^{\prime}\wedge\forall 1\leq i\leq
k.\big{(}[\mathcal{B}]_{p_{i}}(t_{i}^{\prime})=1\big{)}\enspace.$

Therefore,

$\sum_{t^{\prime}\in
h^{-1}(t)}r\odot[\mathcal{B}]_{q}(t^{\prime})=\sum_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in Q^{k}}\sum_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}r\odot[B]_{q}\big{(}[\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,g,q](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}$ (1)

holds for all $r\in S\langle\mkern-4.0mu\langle
T_{\Lambda}\rangle\mkern-4.0mu\rangle$.

By this, we get

$\begin{array}[]{ll}&[\mathcal{A}]_{q}(t)\\\ =&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\alpha_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\prod\limits_{i=1}^{k}[\mathcal{A}]_{p_{i}}(t_{i})\\\
\overset{\mathclap{\textup{(IH)}}}{=}&\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\alpha_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\prod\limits_{i=1}^{k}\big{(}h^{-1}\circ([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{p_{i}})\big{)}(t_{i})\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\alpha_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\prod\limits_{i=1}^{k}\big{(}\sum\limits_{t_{i}^{\prime}\in
h^{-1}(t_{i})}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{p_{i}}(t_{i}^{\prime})\big{)}\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\alpha_{g}(\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}\prod\limits_{i=1}^{k}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{p_{i}}(t_{i}^{\prime})\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}\big{(}\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{k}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu](t_{i}^{\prime})\big{)}\cdot\big{(}1\cdot\prod\limits_{i=1}^{k}[\mathcal{B}]_{p_{i}}(t_{i}^{\prime})\big{)}\\\
=&\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,g,q](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu)\big{)}\cdot[B]_{q}\big{(}[\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern 1.5mu,g,q](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}\\\
\overset{\mathclap{\ref{qtn:sumOStuff}}}{=}&\sum\limits_{t^{\prime}\in
h^{-1}(t)}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q}(t^{\prime})\\\
=&h^{-1}\circ\big{(}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q}\big{)}(t)\end{array}$

This finishes the proof of the claim.

We return to our main proof, it remains to show that we are able to apply the
final weights. We consider some $t\in T_{\Gamma}$. There exists
$g\in\Gamma^{(k)}$ and $\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu\in T_{\Gamma}^{k}$ (we use the same notation as above) with $t=g(\mkern
1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern 1.5mu)$. First, we make a
similar observation as in the proof of our claim. Namely,

$[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu)\big{)}=1\Leftrightarrow p\in Q_{\text{fin}}\wedge\forall{1\leq i\leq
k}.\big{(}[\mathcal{B}]_{q_{i}}(t_{i}^{\prime})=1\big{)}$

for all $\mkern 1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu\in h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)$. Thus,

$\sum_{t^{\prime}\in
h^{-1}(t)}r\odot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](t^{\prime})=\sum_{p\in
Q}\sum_{\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum_{\mkern 1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu\in h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}r\odot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p_{\text{fin}}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}$ (2)

for all $r\in S\langle\mkern-4.0mu\langle
T_{\Lambda}\rangle\mkern-4.0mu\rangle$. Finally, analogously to the proof of
Claim 5.3, we are able to deduce

$\begin{array}[]{ll}&[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](t)\\\
=&\sum\limits_{p\in Q}\lambda(p)\cdot{[\mathcal{A}]_{p}(t)}\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\lambda(p)\cdot\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{k}[\mathcal{A}]_{q_{i}}(t_{i})\\\
\overset{\mathclap{\text{Claim \ref{clm:aux2}}}}{=}&\sum\limits_{p\in
Q}\sum\limits_{\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\lambda(p)\cdot\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{k}h^{-1}\big{(}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q_{i}}\big{)}(t_{i})\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\lambda(p)\cdot\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{k}\sum\limits_{t_{i}^{\prime}\in
h^{-1}(t_{i})}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mathcal{B}]_{q_{i}}(t_{i}^{\prime})\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}\big{(}\lambda(p)\cdot\alpha_{g}(\mkern
1.5mu\overline{\mkern-1.5mup\mkern-1.5mu}\mkern
1.5mu,q)\cdot\prod\limits_{i=1}^{k}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu](t_{i}^{\prime})\big{)}\cdot\big{(}1\cdot\prod\limits_{i=1}^{k}[\mathcal{B}]_{q_{i}}(t_{i}^{\prime})\big{)}\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}\big{(}\omega_{[\mkern 1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern
1.5mu,g,p_{\text{fin}}]}(q_{w},(q_{w},\ldots,q_{w}))\cdot\prod\limits_{i=1}^{k}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu](t_{i}^{\prime})\big{)}\cdot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p_{\text{fin}}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p_{\text{fin}}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern
1.5mu)\big{)}\cdot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p_{\text{fin}}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}\\\
=&\sum\limits_{p\in Q}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu\in
Q^{k}}\sum\limits_{\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu\in
h^{-1}(\mkern 1.5mu\overline{\mkern-1.5mut\mkern-1.5mu}\mkern
1.5mu)}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{(}[\mkern
1.5mu\overline{\mkern-1.5muq\mkern-1.5mu}\mkern 1.5mu,g,p_{\text{fin}}](\mkern
1.5mu\overline{\mkern-1.5mut^{\prime}\mkern-1.5mu}\mkern 1.5mu)\big{)}\\\
\overset{\mathclap{\ref{qtn:sumOStuff2}}}{=}&\sum\limits_{t^{\prime}\in
h^{-1}(t)}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](t^{\prime})\\\
=&h^{-1}\big{(}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\big{)}(t)=h^{-1}\big{(}[\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L}\big{)}(t)\enspace.\end{array}$

Since $t$ was arbitrary, this completes our proof.

Based on this result and Theorem 6 a characterization of WAFA via a Nivat-like
Theorem is immediate.

######  Theorem 13 (Nivat-like theorem for WAFA).

A weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma\rangle\mkern-4.0mu\rangle$ is recognized by
a WAFA if and only if there exist a rank $r\in\mathbb{N}$, a ranked alphabet
$\Lambda$, a linear tree homomorphism $h:T_{\Lambda}\rightarrow
T_{\Sigma^{r}_{\\#}}$, a regular tree language $L\subseteq T_{\Lambda}$, and a
WFTA $\mathcal{A}_{w}$ with exactly one state. And for all $w\in\Sigma^{*}$,
it holds:

$s(w)=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})(t_{w}^{r})\enspace.$

######  Proof 5.5.

$\Rightarrow$: Let $\mathcal{A}$ be a nice, equalized WAFA such that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=s$. Due to Lemma 4, $r\in\mathbb{N}$
and a WFTA $\mathcal{B}$ exist such that
$s(w)=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ
h^{r}(w)=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](t_{w}^{r})$. Applying Theorem
12 to $[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]$ gives us the desired result.

$\Leftarrow$: By Theorem 12, there exists a WFTA $\mathcal{B}$ such that
$[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})$.
Let $h^{r}:\Sigma^{*}\rightarrow T_{\Sigma_{\\#}^{r}}$ be the generic
homomorphism. In consequence of Theorem 6, a WAFA $\mathcal{A}$ exists such
that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](h^{r}(w))=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})(h^{r}(w))=h([\mkern-3.0mu[\mathcal{A}_{w}]\mkern-3.0mu]\odot\mathbb{1}_{L})(t_{w}^{r})$
for all $w\in\Sigma$. This finishes our proof.

##  6\. A logical characterization of WAFA

Based on Theorem 6 we are able to give a logical characterization of WAFA
(Theorem 15). For this purpose, we will use the logical characterization by
weighted MSO logic for trees which was introduced in [DV06].

Weighted MSO logic over trees is an extension of MSO logic over trees. It
allows for the use of usual MSO formulas, but also incorporates quantitative
aspects such as semiring elements and operations, as well as weighted
quantifiers. In the end, every weighted MSO formula defines a weighted tree
language. More precisely, let $\Gamma$ be a ranked alphabet, each weighted MSO
formula $\varphi\in\textup{MSO}(\Gamma,S)$ defines a weighted tree language
$[\mkern-3.0mu[\varphi]\mkern-3.0mu]:T_{\Gamma}\rightarrow S$. Weighted MSO
logic is strictly more expressive than WFTA. Nevertheless, it is possible
restrict the syntax of weighted MSO in such a way that it characterizes
weighted tree languages recognized by WFTA. This fragment is called weighted
syntactically restricted MSO (srMSO). Due to a lack of space, we have to omit
the formal definition of srMSO. We will use syntax and semantics of weighted
srMSO without any changes and refer the interested reader to [FV09] or [DV11].
Our characterization of WAFA will be fully based on the following
characterization theorem for WFTA:

######  Theorem 14 (Theorem 3.49 (A) in [FV09]).

A weighted tree language $s\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is recognized by a WFTA if and only if
there exist $\varphi\in\textup{srMSO}(\Gamma,S)$ such that
$s=[\mkern-3.0mu[\varphi]\mkern-3.0mu]$.

However, we still have to handle the homomorphism used in Theorem 6. This will
be done by choosing an appropriate way of representing words as relational
structures.

By definition $[\mkern-3.0mu[\varphi]\mkern-3.0mu]\in
S\langle\mkern-4.0mu\langle T_{\Gamma}\rangle\mkern-4.0mu\rangle$ for all
$\varphi\in\textup{srMSO}(\Gamma,S)$. However, we want to use weighted srMSO
on trees to define weighted languages on words. To this end, we define
$[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ by
$[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}(w)=[\mkern-3.0mu[\varphi]\mkern-3.0mu]({t_{w}^{\operatorname{Rank}(\Gamma)}})$
for all $\varphi\in\textup{srMSO}(\Gamma,S)$, $w\in\Sigma^{*}$. Since
$\textup{srMSO}(\Gamma,S)\subseteq\textup{srMSO}(\Gamma\cup\Sigma_{\\#}^{\operatorname{Rank}(\Gamma)},S)$,
we can assume without loss of generality
$\varphi\in\textup{srMSO}(\Gamma\cup\Sigma_{\\#}^{\operatorname{Rank}(\Gamma)},S)$.
Hence, $[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}$ is well defined for all
$\Sigma$. It is easy to see that
$[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}=[\mkern-3.0mu[\varphi]\mkern-3.0mu]\circ
h$ where
$h:\Sigma\rightarrow\Sigma_{\\#}^{\operatorname{Rank}(\Gamma)}\cup\Gamma$ is
the generic homomorphism.

######  Theorem 15.

A weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma\rangle\mkern-4.0mu\rangle$ is recognized by
a WAFA if and only if there exist a ranked alphabet $\Gamma$ and
$\varphi\in\textup{srMSO}(\Gamma,S)$ such that
$s=[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}$.

######  Proof 6.1.

$\Rightarrow$: Assume $s\in
S\langle\mkern-4.0mu\langle\Sigma\rangle\mkern-4.0mu\rangle$ is recognized by
a WAFA. By 4, there exists $r\in\mathbb{N}$ and a WFTA $\mathcal{B}$ such that
$s=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ h^{r}$. By Theorem 14,
$\varphi\in\textup{srMSO}(\Sigma_{\\#}^{r},S)$ exists such that
$[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]=[\mkern-3.0mu[\varphi]\mkern-3.0mu]$.
Thus $s=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ
h^{r}=[\mkern-3.0mu[\varphi]\mkern-3.0mu]\circ
h^{r}=[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}$.

$\Leftarrow$: If $s=[\mkern-3.0mu[\varphi]\mkern-3.0mu]_{\Sigma}$ for some
$\varphi\in\textup{srMSO}(\Gamma\cup\Sigma_{\\#}^{\operatorname{Rank}(\Gamma)},S)$,
we get $s=[\mkern-3.0mu[\varphi]\mkern-3.0mu]\circ
h^{\operatorname{Rank}(\Gamma)}$. By Theorem 14, a WFTA $\mathcal{B}$ exists
such that
$[\mkern-3.0mu[\varphi]\mkern-3.0mu]=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]$.
Therefore $s=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu]\circ
h^{\operatorname{Rank}(\Gamma)}$. Since $\mathcal{B}$ is a WFTA and
$h^{\operatorname{Rank}(\Gamma)}$ a homomorphism, a WAFA $\mathcal{A}$ with
$s=[\mkern-3.0mu[A]\mkern-3.0mu]$ exists by Lemma 5.

While mirroring the branching behavior of WAFA in the logic gives a natural
characterization of WAFA, the question arises how WAFA relate to the weighted
MSO logic for words. It is well known, that WFTA are not capable of
characterizing the entirety of weighted MSO logic for words, simply because
MSO logic can define series which grow doubly exponential in the size of the
input. While WAFA have this ability (cf. Example 3), they still are incapable
of capturing the entirety of weighted MSO. It can be shown that the series
$r_{B}$ from the proof of Lemma 10 can be defined in weighted MSO logic for
words, while it is not recognized by WAFA. If it is possible to characterize
WAFA by a fragment of weighted MSO logic for words remains open.

##  7\. Closure of WFTA under inverses of homomorphisms

It is a well known fact that regular tree languages are closed under inverses
of homomorphisms. Sadly, this is not true in the weighted case, at least not
for arbitrary semirings. This raises the question if it is possible to give a
precise description of the class of semirings $\mathcal{S}$ for which WFTA are
closed under inverses of homomorphisms. This question will be answered by
Theorem 16.

Theorem 13 and Theorem 14 used Theorem 6 to apply known results for WFTA to
WAFA. Vice versa, we can use Theorem 6 and Theorem 3 to characterize
$\mathcal{S}$.

######  Theorem 16.

The class of $S$-weighted tree languages recognized by WFTA is closed under
inverses of homomorphisms if and only if $S$ is locally finite.

To prove this result we will use the notion of recognizable step functions: A
weighted tree language $r\in S\langle\mkern-4.0mu\langle
T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is a recognizable step function if there
exist recognizable tree languages $L_{1},\ldots,L_{k}$ and values
$l_{1},\ldots,l_{k}\in S$ such that
$r=\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{L_{i}}$. Due to [DV06], we know the
following about recognizable step functions:

######  Lemma 17 (Lemma 3.1 in [DV06]).

If $r\in S\langle\mkern-4.0mu\langle T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is
a recognizable step function, then a partition $L_{1},\ldots,L_{k}$ of
$T_{\Gamma}$ exits such that $r=\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{L_{i}}$
for some $l_{1},\ldots,l_{k}\in S$.

Note, this lemma is not redundant since the definition of recognizable step
functions does not demand that the recognizable tree languages are pairwise
disjoint. Due to Lemma 17, we know that a weighted tree language is a
recognizable step function if and only if it has a finite image and each
preimage is a recognizable tree language. The next Lemma characterizes
recognizable weighted tree languages over locally finite semirings.

######  Lemma 18 (Lemma 3.3 & Lemma 6.1 in [DV06]).

Let $S$ be locally finite. A weighted tree language $r\in
S\langle\mkern-4.0mu\langle T_{\Gamma}\rangle\mkern-4.0mu\rangle$ is
recognizable if and only if $r$ is a recognizable step function.

Finally, we can proceed with the proof of Theorem 16.

######  Proof 7.1 (Proof of Theorem 16).

$\Rightarrow$: Assume the class of $S$-weighted tree languages recognized by
WFTA is closed under inverses of homomorphisms.

The class of $S$-weighted $\Sigma$ languages recognizable by WAFA and the
class of $S$-weighted $\Sigma$ languages recognizable by WFA are equal.

Clearly every WFA is a WAFA. Thus, for the proof of the claim, it remains to
show that every weighted language which is recognized by a WAFA is recognized
by a WFA. For this purpose, assume $s\in
S\langle\mkern-4.0mu\langle\Sigma^{*}\rangle\mkern-4.0mu\rangle$ is recognized
by a WAFA $\mathcal{A}$. Due to Theorem 6, there exists a WFTA $\mathcal{B}$
and a homomorphism $h:\Sigma^{*}\rightarrow T_{\Gamma}$ such that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=[\mkern-3.0mu[B]\mkern-3.0mu]\circ
h$. However, by our assumption there exists a WFTA $\mathcal{C}$ over
$\Sigma_{\\#}^{1}$ such that
$[\mkern-3.0mu[C]\mkern-3.0mu]=[\mkern-3.0mu[B]\mkern-3.0mu]\circ h$ and hence
a WFA $\mathcal{C}^{\prime}$ over $\Sigma$ such that
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu]=[\mkern-3.0mu[B]\mkern-3.0mu]\circ
h=[\mkern-3.0mu[C]\mkern-3.0mu]=[\mkern-3.0mu[C^{\prime}]\mkern-3.0mu]$.
Thereby, $s$ is recognized by a WFA. This proves our claim.

By Claim 7.1 and Theorem 3 it follows that $S$ is locally finite.

$\Leftarrow$: Assume $S$ is locally finite. Let $r\in
S\langle\mkern-4.0mu\langle T_{\Gamma}\rangle\mkern-4.0mu\rangle$ be
recognizable and $h:T_{\Lambda}\rightarrow T_{\Gamma}$ a homomorphism. Due to
Lemma 17 and Lemma 18, we have $r=\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{L_{i}}$
for some partition $L_{1},\ldots,L_{k}$ of $T_{\Gamma}$ and values
$l_{1},\ldots,l_{k}\in S$. We claim $r\circ
h=\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{h^{-1}(L_{i})}$. To prove this, consider
some arbitrary $t\in T_{\Lambda}$. Since the $L_{i}$ form a partition of
$T_{\Gamma}$ there exists a unique $j\in\\{1,\ldots,k\\}$ such that $h(t)\in
L_{i}$. Therefore we have

$\begin{array}[]{cl}&(r\circ h)(t)\\\
=&\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{L_{i}}(h(t))=l_{j}\\\
=&l_{j}\cdot\mathbb{1}_{h^{-1}(L_{j})}(t)\\\ \overset{l_{j}\text{
unique}}{=}&\sum_{i=1}^{k}l_{i}\cdot\mathbb{1}_{h^{-1}(L_{i})}(t)\enspace.\end{array}$

Since recognizable tree languages are closed under inverses of homomorphisms,
we know that $h^{-1}(L_{1}),\ldots,\\\ h^{-1}(L_{k})\subseteq T_{\Lambda}$ are
recognizable. Thus, $r\circ h$ is a recognizable step function. Again, by
Lemma 18, we get $r\circ h$ is recognizable. This completes our proof.

##  8\. WAFA and polynomial automata

We will use known results for polynomial automata, to prove the decidability
of the Zeroness Problem for WAFA if weights are taken from the rationals
(Lemma 20).

Polynomial automata where introduced in [BTSW17] as a generalization of both
vector addition systems and weighted automata. Polynomial automata are quite
similar to WAFA, the authors of [BTSW17] even prove that the characteristic
function of the reversal of each language recognized by a non-weighted
alternating automaton is recognized by a polynomial automaton of the same
size. We want to strengthen this connection. In [BTSW17] polynomial automata
are defined over the rational numbers. However, it is easy to give a more
general definition for arbitrary commutative semirings.

A polynomial automaton (PA) is a $5$-tuple
$\mathcal{A}=(n,\Sigma,\alpha,p,\gamma)$, where $n\in\mathbb{N}$ is the number
of states, $\Sigma$ is an alphabet, $\alpha\in S^{n}$ is an initial weight
vector, $p:\Sigma\rightarrow{S\langle X_{n}\rangle}^{n}$ the transition
function, and $\gamma\in S\langle X_{n}\rangle$ an output polynomial. We
denote the $i$-th entry of $p(a)$ by $p_{i}(a)$.

Let $\mathcal{A}=(n,\Sigma,\alpha,p,\gamma)$ be a PA. Its state behavior
$[\mathcal{A}]:\\{1,\ldots,n\\}\times\Sigma^{*}\rightarrow S$ is the mapping
defined by

$[\mathcal{A}](i,w)=\begin{cases}\alpha_{i}&\text{ if }w=\varepsilon,\\\
p_{i}\big{\langle}[\mathcal{A}](1,v),\ldots,[\mathcal{A}](n,v)\big{\rangle}&\text{
if }w=va\text{ for }a\in\Sigma.\end{cases}$

Usually we will denote $[\mathcal{A}](i,w)$ by $[\mathcal{A}]_{i}(w)$. Now,
the behavior of $\mathcal{A}$ is the weighted language
$[\mkern-3.0mu[A]\mkern-3.0mu]:\Sigma^{*}\rightarrow S$ defined by

$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=\gamma\big{(}[\mathcal{A}]_{1}(w),\ldots,[\mathcal{A}]_{n}(w)\big{)}.$

It is easy to check that this definition is a reformulation of the definition
found in [BTSW17].

Let the reversal of a weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma\rangle\mkern-4.0mu\rangle$ be defined by
$s^{R}(w)=s(w^{R})$ for all $w=w_{1},\ldots w_{n}\in\Sigma^{*}$, where
$w^{R}=w_{n}\ldots w_{1}$. Comparing the definition of state behavior for WAFA
and PA already yields the following lemma:

######  Lemma 19.

A weighted language $s\in
S\langle\mkern-4.0mu\langle\Sigma\rangle\mkern-4.0mu\rangle$ is recognized by
a WAFA if and only if $s^{R}$ is recognized by a PA.

######  Proof 8.1.

Assume $s$ is recognized by $\mathcal{A}=(Q,\Sigma,\delta,P_{0},\tau)$. Let
$\mathcal{B}=(|Q|,\Sigma,\big{(}\tau(q_{1}),\ldots,\tau(q_{n})\big{)},p,P_{0})$
be a PA with $p_{i}(a)=\delta(q_{i},a)$ for all $1\leq i\leq|Q|,a\in\Sigma$.
Then, a straightforward induction on $|w|$ shows
$[\mkern-3.0mu[A]\mkern-3.0mu](w)=[\mkern-3.0mu[\mathcal{B}]\mkern-3.0mu](w^{R})$
for all $w\in\Sigma$. The second direction is proven analogously to the first
one.

Let $\mathcal{A},\mathcal{A}^{\prime}$ be two WAFA. We observe
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=0$ for all $w\in\Sigma^{*}$ if and
only if $[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w^{R})=0$ for all
$w\in\Sigma^{*}$. Moreover, we have
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w)=[\mkern-3.0mu[\mathcal{A}^{\prime}]\mkern-3.0mu](w)$
for all $w\in\Sigma^{*}$ if and only if
$[\mkern-3.0mu[\mathcal{A}]\mkern-3.0mu](w^{R})=[\mkern-3.0mu[\mathcal{A}^{\prime}]\mkern-3.0mu](w^{R})$
for all $w\in\Sigma^{*}$. This allows us to derive the following corollary
from Lemma 19:

######  Corollary 20.

The Zeroness Problem and the Equivalence Problem for WAFA with weights taken
from the rationals are in the complexity class ACKERMANN and hard for the
complexity class ACKERMANN.

######  Proof 8.2.

Lemma 19 \+ Theorem 1, Theorem 4, Corollary 1 in [BTSW17].

##  9\. Conclusion

We were able to connect WAFA to a variety of formalisms, giving a better
understanding of their expressive power and characterizing the class of
quantitative languages recognized by WAFA. From here, there are various routes
to take. It could be of great practical use to find a logical characterization
of WAFA via a linear formalism such as a weighted linear logic, or weighted
rational expressions tailored to the expressive power of WAFA, or a fitting
fragment of weighted MSO logic for words.

Similar to the work in [BTSW17], one could investigate subclasses of WAFA
allowing for more efficient decision procedures. An interesting candidate is
strictly alternating WAFA who have a bounded number of alternations within any
run. While these use the ability to recognize very fast growing series, they
still add in expressive power due to the ability to multiply over subruns.

A different direction would aim to use the expressive power added by
alternation to achieve an automata model which is as expressive weighted MSO
for words. While WAFA can not fulfill this role a generalization of WAFA might
be. After all, the use of product and sum within runs is very similar, to the
use of product- and sum-quantifiers in weighted MSO for words.

Alternatively, one could approach the concept of alternation in weighted
automata dealing with more complex structures than words, such as weighted
alternating tree automata. And of course, having the universal interpretation
of nondeterminism in mind, one may take several of these routes at once!

## References

  * [AK11] S. Almagor and O. Kupferman.  Max and sum semantics for alternating weighted automata.  In T. Bultan and P. Hsiung, editors, Automated Technology for Verification and Analysis, pages 13–27. Springer, 2011.  doi:10.1007/978-3-642-24372-1_2.
  * [BL80] J.A. Brzozowski and E. Leiss.  On equations for regular languages, finite automata, and sequential networks.  Theoretical Computer Science, 10(1):19–35, 1980.  URL: https://www.sciencedirect.com/science/article/pii/0304397580900699, doi:10.1016/0304-3975(80)90069-9.
  * [BTSW17] M. Benedikt, Duffm T., A. Sharad, and J. Worrell.  Polynomial automata: Zeroness and applications.  In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, June 2017.  URL: https://ora.ox.ac.uk/objects/uuid:f341421b-2130-42d7-bb21-52442bad0b80#citeForm, doi:10.1109/LICS.2017.8005101.
  * [CDH08] K. Chatterjee, L. Doyen, and T. A. Henzinger.  Quantitative languages.  In M. Kaminski and S. Martini, editors, Computer Science Logic, pages 385–400. Springer, 2008.  URL: https://doi.org/10.1007/978-3-540-87531-4_28, doi:10.1007/978-3-540-87531-4_28.
  * [CDH09] K. Chatterjee, L. Doyen, and T. A. Henzinger.  Alternating weighted automata.  In M. Kutyłowski, W. Charatonik, and M. Gębala, editors, Fundamentals of Computation Theory, pages 3–13. Springer, 2009.  doi:10.1007/978-3-642-03409-1_2.
  * [CKS81] A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer.  Alternation.  J. ACM, 28(1):114–133, January 1981.  URL: http://doi.acm.org/10.1145/322234.322243, doi:10.1145/322234.322243.
  * [DD15] M. Droste and S. Dück.  Weighted automata and logics on graphs.  In G. F. Italiano, G. Pighizzini, and D. T. Sannella, editors, Mathematical Foundations of Computer Science 2015, pages 192–204. Springer, 2015\.  doi:10.1007/978-3-662-48057-1_15.
  * [DG07] M. Droste and P. Gastin.  Weighted automata and weighted logics.  Theoretical Computer Science, 380(1):69–86, 2007.  Automata, Languages and Programming.  URL: https://www.sciencedirect.com/science/article/pii/S0304397507001582, doi:10.1016/j.tcs.2007.02.055.
  * [DG09] M. Droste and P. Gastin.  Weighted Automata and Weighted Logics, chapter 5.  In Droste et al. [DKV09], 1st edition, 2009.  doi:10.1007/978-3-642-01492-5_5.
  * [DG17] M. Droste and D. Götze.  A nivat theorem for quantitative automata on unranked trees.  In Models, Algorithms, Logics and Tools - Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday, pages 22–35, 2017\.  URL: https://doi.org/10.1007/978-3-319-63121-9_2, doi:10.1007/978-3-319-63121-9\\_2.
  * [DGV13] G. De Giacomo and M. Y. Vardi.  Linear temporal logic and linear dynamic logic on finite traces.  In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 854–860. AAAI Press, 2013.  URL: http://dl.acm.org/citation.cfm?id=2540128.2540252.
  * [DKar] M. Droste and D. Kuske.  Weighted automata.  European Mathematical Society, to appear.
  * [DKV09] M. Droste, W. Kuich, and H. Vogler, editors.  Handbook of Weighted Automata.  Springer, 1st edition, 2009.  doi:10.1007/978-3-642-01492-5.
  * [DS87] E. Muller D and P. E. Schupp.  Alternating automata on infinite trees.  Theoretical Computer Science, 54(2):267–276, 1987.  URL: https://www.sciencedirect.com/science/article/pii/0304397587901332, doi:10.1016/0304-3975(87)90133-2.
  * [DV06] M. Droste and H. Vogler.  Weighted tree automata and weighted logics.  Theoretical Computer Science, 366(3):228 – 247, 2006.  Automata and Formal Languages.  URL: http://www.sciencedirect.com/science/article/pii/S0304397506005676, doi:10.1016/j.tcs.2006.08.025.
  * [DV11] M. Droste and H. Vogler.  Weighted logics for unranked tree automata.  Theory of Computing Systems, 48(1):23–47, 2011.  doi:10.1007/s00224-009-9224-4.
  * [FV09] Z. Fülöp and H. Vogler.  Weighted Tree Automata and Tree Transducers, chapter 9.  In Droste et al. [DKV09], 1st edition, 2009.  doi:10.1007/978-3-642-01492-5_9.
  * [Gra21] Gustav Grabolle.  A nivat theorem for weighted alternating automata over commutative semirings.  Electronic Proceedings in Theoretical Computer Science, 346:241–257, Sep 2021.  URL: http://dx.doi.org/10.4204/EPTCS.346.16, doi:10.4204/eptcs.346.16.
  * [KM18] P. Kostolányi and F. Mišún.  Alternating weighted automata over commutative semirings.  Theoret. Comput. Sci., 740:1 – 27, 2018.  URL: http://www.sciencedirect.com/science/article/pii/S0304397518303098, doi:10.1016/j.tcs.2018.05.003.
  * [Niv68] M. Nivat.  Transduction des langages de chomsky, 1968.  doi:10.5802/aif.287.
  * [Sch61] M.P. Schützenberger.  On the definition of a family of automata.  Inform. and Control, 4(2):245 – 270, 1961.  URL: http://www.sciencedirect.com/science/article/pii/S001999586180020X, doi:10.1016/S0019-9958(61)80020-X.
  * [Var95] M. Y. Vardi.  Alternating automata and program verification, pages 471–485.  Springer, 1995.  doi:10.1007/BFb0015261.