Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Object grammars and ...
Article

Object grammars and random generation

I. Dutour (1), Jean-Marc Fedou (2) (3)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
(3) École Supérieure en Sciences Informatiques
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 1998
Last modified on
March 31, 2025
Volume 2
vol. 2
DOI
10.46298/dmtcs.250
License
https://about.hal.science/hal-authorisation-v1
Indicators
637
Views
656
Downloads

Object grammars and random generation

I. Dutour (1), Jean-Marc Fedou (2) (3)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
(3) École Supérieure en Sciences Informatiques
Abstract
This paper presents a new systematic approach for the uniform random generation of combinatorial objects. The method is based on the notion of object grammars which give recursive descriptions of objects and generalize context-freegrammars. The application of particular valuations to these grammars leads to enumeration and random generation of objects according to non algebraic parameters.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Uniform random generation
  • object grammars
  • q-equations
Cited by

Source: OpenCitations

  • Object grammars and bijections

    Theoretical Computer Science

    Authors : I. Dutour, J.M. Fédou

    Journal reference : Volume 290, 2003, pp. 1915-1929

    DOI : 10.1016/s0304-3975(02)00368-7
  • Attribute grammars and automatic complexity analysis

    Advances in Applied Mathematics

    Authors : Marni Mishna ORCID

    Journal reference : Volume 30, 2003, pp. 189-207

    DOI : 10.1016/s0196-8858(02)00542-0
  • A clustering algorithm for huge trees

    Advances in Applied Mathematics

    Authors : D. Auber ORCID, M. Delest

    Journal reference : Volume 31, 2003, pp. 46-60

    DOI : 10.1016/s0196-8858(02)00505-5
  • On computing the coefficients of bivariate holonomic formal series

    Theoretical Computer Science

    Authors : P. Massazza, R. Radicioni

    Journal reference : Volume 346, 2005, pp. 418-438

    DOI : 10.1016/j.tcs.2005.08.011
  • Q-grammars and wall polyominoes

    Annals of Combinatorics

    Authors : Philippe Duchon

    Journal reference : Volume 3, 1999, pp. 311-321

    DOI : 10.1007/bf01608790
  • Controlled non-uniform random generation of decomposable structures

    Theoretical Computer Science

    Authors : A. Denise ORCID, Y. Ponty ORCID, M. Termier

    Journal reference : Volume 411, 2010, pp. 3527-3552

    DOI : 10.1016/j.tcs.2010.05.010
  • Random generation of words of context-free languages according to the frequencies of letters

    Mathematics and Computer Science

    Authors : Alain Denise ORCID, Olivier Roques ORCID, Michel Termier

    Journal reference : Volume , 2000, pp. 113-125

    DOI : 10.1007/978-3-0348-8405-1_10
  • From object grammars to ECO systems

    Theoretical Computer Science

    Authors : Enrica Duchi, Jean-Marc Fedou, Simone Rinaldi

    Journal reference : Volume 314, 2003, pp. 57-95

    DOI : 10.1016/j.tcs.2003.10.037
Preview
Loading PDF preview...