Degree of Sequentiality of Weighted Automata

Daviaud, Laure, Jecker, Ismaël, Reynier, Pierre-Alain and Villevalois, Didier (2017) Degree of Sequentiality of Weighted Automata. In: FoSSaCS 2017: Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science . Springer-Verlag Berlin Heidelberg, SWE, pp. 215-230. ISBN 9783662544570

Full text not available from this repository.

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.

Item Type:	Book Section
Additional Information:	Funding Information: This work has been funded by FNRS, the DeLTA project (ANR-16-CE40-0007), the ARC project Transform (Federation Wallonie Brussels), the FNRS CDR project Flare, and the PHC project VAST (35961QJ) funded by Campus France and WBI. L. Daviaud was partially supported by ANR Project ELICA ANR-14-CE25-0005, ANR Project RECRE ANR-11-BS02-0010 and by project lipa that has received funding from the European Research Council ( erc ) under the European Union’s Horizon 2020 research and innovation programme (grant agreement Nb 683080). Publisher Copyright: © Springer-Verlag GmbH Germany 2017.
Uncontrolled Keywords:	theoretical computer science,computer science(all) ,/dk/atira/pure/subjectarea/asjc/2600/2614
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 14:30
Last Modified:	08 Jun 2023 14:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92347
DOI:	10.1007/978-3-662-54458-7_13

Actions (login required)

View Item