City Research Online

A Generalised Twinning Property for Minimisation of Cost Register Automata

Daviaud, L., Reynier, P-A. and Talbot, J-M. (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. 857-866). New York, NY: ACM. ISBN 978-1-4503-4391-6

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.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © {Daviaud, L., Reynier, P-A. and Talbot, J-M. | 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
URI: http://openaccess.city.ac.uk/id/eprint/21298
[img]
Preview
Text - Accepted Version
Download (448kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login