City Research Online

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.

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: https://doi.org/10.1007/978-3-662-54458-7_13.
Subjects:	Q Science > QA Mathematics
Departments:	School of Science & Technology > Computer Science

Export

Downloads