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

Original language | English |
---|---|

Title of host publication | Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016 |

Publisher | The Institute of Electrical and Electronics Engineers (IEEE) |

Pages | 857-866 |

Number of pages | 10 |

ISBN (Electronic) | 9781450343916 |

DOIs | |

Publication status | Published - Jul 2016 |

Externally published | Yes |

Event | 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, United States Duration: 5 Jul 2016 → 8 Jul 2016 |

### Publication series

Name | Proceedings - Symposium on Logic in Computer Science |
---|---|

Volume | 05-08-July-2016 |

ISSN (Print) | 1043-6871 |

### Conference

Conference | 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 |
---|---|

Country/Territory | United States |

City | New York |

Period | 5/07/16 → 8/07/16 |

## Keywords

- cost register automata
- minimisation
- twinning property
- weighted automata