A Generalised Twinning Property for Minimisation of Cost Register Automata

Laure Daviaud, Pierre-Alain Reynier, Jean-Marc Talbot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016
PublisherThe Institute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Electronic)9781450343916
Publication statusPublished - Jul 2016
Externally publishedYes
Event31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, United States
Duration: 5 Jul 20168 Jul 2016

Publication series

NameProceedings - Symposium on Logic in Computer Science
ISSN (Print)1043-6871


Conference31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016
Country/TerritoryUnited States
CityNew York


  • cost register automata
  • minimisation
  • twinning property
  • weighted automata

Cite this