Title: Degree of sequentiality of weighted automata,
Abstract: Weighted automata (WA) are an important formalism to describe quantitative
properties. Obtaining equivalent deterministic machines is a longstanding
research problem. In this paper we consider WA with a set semantics, meaning
that the semantics is given by the set of weights of accepting runs. We focus
on multi-sequential WA that are defined as finite unions of sequential WA. The
problem we address is to minimize the size of this union. We call this minimum
the degree of sequentiality of (the relation realized by) the WA. For a given
positive integer k, we provide multiple characterizations of relations realized
by a union of k sequential WA over an infinitary finitely generated group: a
Lipschitz-like machine independent property, a pattern on the automaton (a new
twinning property) and a subclass of cost register automata. When possible, we
effectively translate a WA into an equivalent union of k sequential WA. We also
provide a decision procedure for our twinning property for commutative
computable groups thus allowing to compute the degree of sequentiality. Last,
we show that these results also hold for word transducers and that the
associated decision problem is Pspace-complete.