City Research Online

Degree of Sequentiality of Weighted Automata

Daviaud, L., Jecker, I., Reynier, P-A. & Villevalois, D. (2017). Degree of Sequentiality of Weighted Automata. In: Foundations of Software Science and Computation Structures. FoSSaCS 2017. Foundations of Software Science and Computation Structures. FoSSaCS 2017, 24-27 April, Uppsala, Sweden. doi: 10.1007/978-3-662-54458-7_13


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

Publication Type: Conference or Workshop Item (Paper)
Additional Information: This is a post-peer-review, pre-copyedit version of a conference paper published in Foundations of Software Science and Computation Structures. FoSSaCS 2017. Lecture Notes in Computer Science, vol 10203. The final authenticated version is available online at:
Subjects: Q Science > QA Mathematics
Departments: School of Science & Technology > Computer Science
[thumbnail of main.pdf]
Text - Accepted Version
Download (560kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login