Random Generation for Finitely Ambiguous Context-free Languages

DOI10.1051/ITA:2001128MaRDI QIDQ3147017zbMATH OpenOpenAlexFDO

Authors Massimiliano Goldwurm, Massimo Santini, 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, https://eudml.org/doc/222066, https://semanticscholar.org/paper/a80cccdadaafd46029261231e518375a503ba543

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3921975
• Finite generation of ambiguity in context-free languages
• scientific article; zbMATH DE number 1688372
• Random generation of DFAs
• Random Generation of Combinatorial Structures using Context-Fee Grammars
• Generating words in a context-free language uniformly at random
• Pseudorandom generators against advised context-free languages
• Non-redundant random generation algorithms for weighted context-free grammars
• Random generation of nondeterministic finite-state tree automata
• scientific article; zbMATH DE number 1552330

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3755865 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3560742 (Why is no real title available?)
• scientific article; zbMATH DE number 3614066 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• An efficient context-free parsing algorithm
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Generating words in a context-free language uniformly at random
• Optimization of LR(k) parsers
• Random generation of combinatorial structures from a uniform distribution
• Random generation of words in an algebraic language in linear binary space
• The complexity of computing maximal word functions
• Turing machines with sublogarithmic space
• Uniform Random Generation of Strings in a Context-Free Language
• Uniform random generation of decomposable structures using floating-point arithmetic

Cited in

(13)

• Immunity and pseudorandomness of context-free languages
• Random generation of DFAs
• Bounded length UCFG equivalence
• scientific article; zbMATH DE number 1688372 (Why is no real title available?)
• On the number of occurrences of a symbol in words of regular languages.
• Formulae and asymptotics for coefficients of algebraic functions
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)
• Linear delay enumeration and monadic second-order logic
• A linear algorithm for the random sampling from regular languages
• scientific article; zbMATH DE number 3921975 (Why is no real title available?)
• Random Generation of Combinatorial Structures using Context-Fee Grammars
• Generating words in a context-free language uniformly at random
• Preface

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3147017)