Efficient Computation of Throughput Values of Context-Free Languages

DOI10.1007/978-3-540-76336-9_20MaRDI QIDQ3503907zbMATH OpenOpenAlexFDO

Authors Jurek Czyzowicz, Wojciech Fraczak, Didier Caucal, Wojciech Rytter

Publication date 10 June 2008

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00620156/file/throughput.pdf

zbMATH Keywords

context-free grammarminimal mean weightpush-down automatonthroughput

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Parallel recognition and ranking of context-free languages
• Stochastic context-free grammars, regular languages, and newton's method
• Finding the growth rate of a regular or context-free language in polynomial time
• Context-free recognition via shortest paths computation: a version of Valiant's algorithm

Cites work

• A characterization of the minimum cycle mean in a digraph
• Computing the throughput of concatenation state machines
• On Context-Free Languages
• On Fixed Point Equations over Commutative Semirings

Cited in

(3)

• Derivation Tree Analysis for Accelerated Fixed-Point Computation
• Derivation tree analysis for accelerated fixed-point computation
• Computing the throughput of concatenation state machines

This page was built for publication: Efficient Computation of Throughput Values of Context-Free Languages

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