Random Generation for Finitely Ambiguous Context-free Languages

DOI10.1051/ita:2001128zbMath1005.68091OpenAlexW2093299596MaRDI QIDQ3147017

Massimo Santini, Massimiliano Goldwurm, Alberto Bertoni

Publication date: 18 September 2002

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_6_499_0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (4)

On the number of occurrences of a symbol in words of regular languages. ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Preface ⋮ Linear delay enumeration and monadic second-order logic

Cites Work

• Random generation of words in an algebraic language in linear binary space
• Random generation of combinatorial structures from a uniform distribution
• Uniform random generation of decomposable structures using floating-point arithmetic
• Generating words in a context-free language uniformly at random
• The complexity of computing maximal word functions
• A calculus for the random generation of labelled combinatorial structures
• Turing machines with sublogarithmic space
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Optimization of LR(k) parsers
• Uniform Random Generation of Strings in a Context-Free Language
• An efficient context-free parsing algorithm
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Random Generation for Finitely Ambiguous Context-free Languages