Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Théodore Lopez 1 Benjamin Monmege 1 Jean-Marc Talbot 1
1 MOVE - Modélisation et Vérification
LIS - Laboratoire d'Informatique et Systèmes
Abstract : Cost register automata (CRA) are machines reading an input word while computing values using write-only registers: values from registers are combined using the two operations, as well as the constants, of a semiring. Particularly interesting is the subclass of copyless CRAs where the content of a register cannot be used twice for updating the registers. Originally deterministic, non-deterministic variant of CRA may also be defined: the semantics is then obtained by combining the values of all accepting runs with the additive operation of the semiring (as for weighted automata). We show that finitely-ambiguous copyless non-deterministic CRAs (i.e. the ones that admit a bounded number of accepting runs on every input word) can be effectively transformed into an equivalent copyless (deterministic) CRA, without requiring any specific property on the semiring. As a corollary, this also shows that regular look-ahead can effectively be removed from copyless CRAs.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download
Contributor : Benjamin Monmege <>
Submitted on : Tuesday, August 20, 2019 - 1:06:52 PM
Last modification on : Friday, August 23, 2019 - 11:54:01 AM
Long-term archiving on: Thursday, January 9, 2020 - 4:24:43 PM


Publisher files allowed on an open archive




Théodore Lopez, Benjamin Monmege, Jean-Marc Talbot. Determinisation of Finitely-Ambiguous Copyless Cost Register Automata. 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany. ⟨10.4230/LIPIcs.MFCS.2019.75⟩. ⟨hal-02268107⟩



Record views


Files downloads