Determinisation of Finitely-Ambiguous Copyless Cost Register Automata - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Résumé

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.
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2019-75.pdf (503.39 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02268107 , version 1 (20-08-2019)

Identifiants

Citer

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⟩
104 Consultations
106 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More