Daviaud, L., Reynier, PA. and Talbot, JM. (2016). A Generalised Twinning Property for Minimisation of Cost Register Automata. In: LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS, 2016. (pp. 857866). New York, NY: ACM. ISBN 9781450343916
Abstract
Weighted automata (WA) extend finitestate 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 finitestate 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 kbounded 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 finitevalued 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 finitevalued finitestate transducers, and that the register minimisation problem for the class CRA.c (B*) is Pspacecomplete.
Publication Type:  Conference or Workshop Item (Paper) 

Additional Information:  © {Daviaud, L., Reynier, PA. and Talbot, JM.  ACM} {2016}. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in LICS '18 Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science , http://dx.doi.org/10.1145/10.1145/3209108.3209163. 
Publisher Keywords:  weighted automata; cost register automata; minimisation; twinning property 
Subjects:  Q Science > QA Mathematics 
Departments:  School of Mathematics, Computer Science & Engineering > Computer Science 
Date available in CRO:  22 Jan 2019 15:45 
Date deposited:  22 January 2019 
Date of acceptance:  4 April 2016 
Date of first online publication:  5 July 2016 
URI:  https://openaccess.city.ac.uk/id/eprint/21298 

Text
 Accepted Version
Download (448kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 