Random generation and approximate counting of ambiguously described combinatorial structures

This paper concerns the uniform random generation and the approximate counting of combinatorial structures admitting an ambiguous description. we propose a general framework to study the complexity of these problems and present some applications to specific classes of languages. in particular, we give a uniform random generation algorithm for finitely ambiguous context-free languages of the same time complexity of the best known algorithm for the unambiguous case. other applications include a polynomial time uniform random generator and approximation scheme for the census function of (i) languages recognized in polynomial time by one-way nondeterministic auxiliary pushdown automata of polynomial ambiguity and (ii) polynomially ambiguous rational trace languages.