Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic

Abstract : The {\em recursive method\/} formalized by Nijenhuis and Wilf \cite{NiWi78} and systematized by Flajolet, Van Cutsem and Zimmermann \cite{FlZiVa94}, is extended here to floating-point arithmetic. The resulting ADZ method enables one to generate decomposable data structures --- both labelled or unlabelled --- uniformly at random, in expected $O(n^{1+\epsilon})$ time and space, after a preprocessing phase of $O(n^{2+\epsilon})$ time, which reduces to $O(n^{1+\epsilon})$ for context-free grammars.
Type de document :
Rapport
[Research Report] RR-3242, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073447
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:49:58
Dernière modification le : samedi 17 septembre 2016 - 01:06:54
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:46:50

Fichiers

Identifiants

  • HAL Id : inria-00073447, version 1

Collections

Citation

Alain Denise, Paul Zimmermann. Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic. [Research Report] RR-3242, INRIA. 1997. 〈inria-00073447〉

Partager

Métriques

Consultations de la notice

333

Téléchargements de fichiers

119