Adding Pebbles to Weighted Automata

Paul Gastin 1, 2 Benjamin Monmege 1, 2
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We extend weighted automata and weighted rational expressions with 2-way moves and (reusable) pebbles. We show with examples from natural language modeling and quantitative model-checking that weighted expressions and automata with pebbles are more expressive and allow much more natural and intuitive specifications than classical ones. We extend Kleene-Schützenberger theorem showing that weighted expressions and automata with pebbles have the same expressive power. We focus on an efficient translation from expressions to automata. We also prove that the evaluation problem for weighted automata can be done very efficiently if the number of (reusable) pebbles is low.
Type de document :
Communication dans un congrès
Moreira, Nelma and Reis, Rogério. Proceedings of the 17th International Conference on Implementation and Application of Automata (CIAA'12), 2012, Porto, Portugal. Springer-Verlag, 7381, pp.28-51, 2012, 〈10.1007/978-3-642-31606-7_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00776603
Contributeur : Benedikt Bollig <>
Soumis le : mardi 15 janvier 2013 - 17:43:10
Dernière modification le : jeudi 11 janvier 2018 - 06:23:37

Lien texte intégral

Identifiants

Collections

Citation

Paul Gastin, Benjamin Monmege. Adding Pebbles to Weighted Automata. Moreira, Nelma and Reis, Rogério. Proceedings of the 17th International Conference on Implementation and Application of Automata (CIAA'12), 2012, Porto, Portugal. Springer-Verlag, 7381, pp.28-51, 2012, 〈10.1007/978-3-642-31606-7_4〉. 〈hal-00776603〉

Partager

Métriques

Consultations de la notice

184