A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems

Cedric Loi 1, 2 Paul-Henry Cournède 2, 1 Jean Françon 3
1 DIGIPLANTE - Modélisation de la croissance et de l'architecture des plantes
MAS - Mathématiques Appliquées aux Systèmes - EA 4037, Inria Saclay - Ile de France, Ecole Centrale Paris, Centre de coopération internationale en recherche agronomique pour le développement [CIRAD] : UMR
Abstract : The analysis of pattern occurrences has numerous applications, in particular in biology. In this article, a symbolic method is proposed to compute the distribution associated to the number of occurences of a specific pattern in a random text generated by a stochastic 0L-system. To that purpose, a semiring structure is set for combinatorial classes composed of weighted words. This algebraic structure relies on new union and concatenation operators which, under some assumptions, are admissible constructions. Decomposing the combinatorial classes of interest by using these binary operators enables the direct translation of specifications into a set of functional equations relating generating functions thanks to transformation rules. The article ends with two examples. The first one deals with unary patterns and the connection with multitype branching process is established. The second one is about a pattern composed of two letters and underlines the importance of writing a proper specification.
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.473-488, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00529137
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:32:28
Dernière modification le : vendredi 29 juin 2018 - 12:12:27
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:09:54

Fichier

dmAM0133.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00529137, version 2

Collections

Citation

Cedric Loi, Paul-Henry Cournède, Jean Françon. A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.473-488, 2010, DMTCS Proceedings. 〈inria-00529137v2〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

151