A Generalised Twinning Property for Minimisation of Cost Register Automata

Daviaud, Laure, Reynier, Pierre-Alain and Talbot, Jean-Marc (2016) A Generalised Twinning Property for Minimisation of Cost Register Automata. In: Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Proceedings - Symposium on Logic in Computer Science . The Institute of Electrical and Electronics Engineers (IEEE), USA, pp. 857-866. ISBN 9781450343916

Full text not available from this repository.

Abstract

Weighted automata (WA) extend finite-state automata by associating with transitions weights from a semiring S, defining functions from words to S. Recently, cost register automata (CRA) have been introduced as an alternative model to describe any function realised by a WA by means of a deterministic machine. Unambiguous WA over a monoid (M, ⊗) can equivalently be described by cost register automata whose registers take their values in M, and are updated by operations of the form x: = y ⊗ c, with c M. This class is denoted by CRA⊗c(M). We introduce a twinning property and a bounded variation property parametrised by an integer k, such that the corresponding notions introduced originally by Choffrut for finite-state transducers are obtained for k = 1. Given an unambiguous weighted automaton W over an infinitary group (G, ⊗) realizing some function f, we prove that the three following properties are equivalent: i) W satisfies the twinning property of order k, ii) f satisfies the k-bounded variation property, and iii) f can be described by a CRA⊗c(G) with at most k registers. In the spirit of tranducers, we actually prove this result in a more general setting by considering machines over the semiring of finite sets of elements from (G, ⊗): the three properties are still equivalent for such finite-valued weighted automata, that is the ones associating with words subsets of G of cardinality at most ℓ, for some natural ℓ. Moreover, we show that if the operation ⊗ of G is commutative and computable, then one can decide whether a WA satisfies the twinning property of order k. As a corollary, this allows to decide the register minimisation problem for the class CRA⊗c(G). Last, we prove that a similar result holds for finite-valued finite-state transducers, and that the register minimisation problem for the class CRA.c (B∗) is Pspace-complete.

Item Type:	Book Section
Additional Information:	Publisher Copyright: © 2016 ACM.
Uncontrolled Keywords:	cost register automata,minimisation,twinning property,weighted automata,software,mathematics(all) ,/dk/atira/pure/subjectarea/asjc/1700/1712
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 13:30
Last Modified:	08 Jun 2023 13:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92326
DOI:	10.1145/2933575.2934549

Actions (login required)

View Item