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.
Random generation and approximate counting of ambiguously described combinatorial structures / M. Santini, M. Goldwurm, A. Bertoni - In: STACS 2000 : 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19, 2000 : Proceedings / [a cura di] H. Reichel, S. Tison. - Berlin : Springer, 2000. - ISBN 3540671412. - pp. 567-580 (( Intervento presentato al 17. convegno Annual Symposium on Theoretical Aspects of Computer Science (STACS) tenutosi a Lille nel 2000.
|Titolo:||Random generation and approximate counting of ambiguously described combinatorial structures|
SANTINI, MASSIMO (Primo)
GOLDWURM, MASSIMILIANO (Secondo)
BERTONI, ALBERTO (Ultimo)
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2000|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|