Object grammars and random generation

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

• q-equations
• uniform random generation
• object grammars
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]