2026-07-20T11:57:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11019 2024-03-06T10:47:04Z ddc:004 open_access

Determinisation of Finitely-Ambiguous Copyless Cost Register Automata Lopez, Théodore Monmege, Benjamin Talbot, Jean-Marc Cost-register automata Look-ahead removal Unambiguity Determinisation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Théodore Lopez and Benjamin Monmege and Jean-Marc Talbot 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.75 urn:nbn:de:0030-drops-110190 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.75 eng https://creativecommons.org/licenses/by/3.0/legalcode