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

https://hal.archives-ouvertes.fr/hal-02268107
Contributor : Benjamin Monmege <>
Submitted on : Tuesday, August 20, 2019 - 1:06:52 PM
Last modification on : Friday, August 23, 2019 - 11:54:01 AM

File

LIPIcs-MFCS-2019-75.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

43

Files downloads

19