Degree of Sequentiality of Weighted Automata

Laure Daviaud, Ismaël Jecker, Pierre-Alain Reynier, Didier Villevalois

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationFoSSaCS 2017: Foundations of Software Science and Computation Structures
EditorsJavier Esparza, Andrzej S. Murawski
PublisherSpringer-Verlag Berlin Heidelberg
Number of pages16
ISBN (Print)9783662544570
Publication statusPublished - 2017
Externally publishedYes
Event20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017 - Uppsala, Sweden
Duration: 22 Apr 201729 Apr 2017

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017
City Uppsala

Cite this