A Generalized Twinning Property for Minimisation of Cost Register Automata
| Autor: | Jean-Marc Talbot, Pierre-Alain Reynier, Laure Daviaud |
|---|---|
| Přispěvatelé: | Preuves et Langages (PLUME), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modélisation et Vérification (MOVE), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Reynier, Pierre-Alain |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Monoid
0102 computer and information sciences 02 engineering and technology 01 natural sciences Semiring Combinatorics Cardinality Integer [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] cost register automata QA Commutative property ComputingMilieux_MISCELLANEOUS [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Mathematics Discrete mathematics minimisation twinning property Order (ring theory) Function (mathematics) 010201 computation theory & mathematics Bounded variation 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory Weighted automata |
| Zdroj: | Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16) Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), 2016, Unknown, Unknown Region. pp.857--866, ⟨10.1145/2933575.2934549⟩ LICS |
| Popis: | Weighted automata (WA) extend finite-state automata by associating with transitions weights from a semiring $\mathbb {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,\otimes )$ 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\otimes c$, with $c\in M$. This class is denoted by $\mathrm {CRA}_{\otimes 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,\otimes )$ 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 $\mathrm {CRA}_{\otimes 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,\otimes )$ : 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 $\ell$, for some natural $\ell$. Moreover, we show that if the operation $\otimes \, \mathrm {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 $\mathrm {CRA}_{\otimes 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|