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

## 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: | |

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 |