A simple proof of Valiant's lemma

DOI10.1051/ITA/1986200201831MaRDI QIDQ3745310zbMATH OpenOpenAlexWikidataFDO

Authors Hermann K.-G. Walter

Publication date 1986

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

Full work available at URL https://eudml.org/doc/92255

zbMATH Keywords

dividing matrices into submatricesmatrix closuresrecognition problem of context-free languagestransitive closure

Mathematics Subject Classification ID

Matrices over special rings (quaternions, finite fields, etc.) (15B33) Formal languages and automata (68Q45)

Recommendations

• Context-free recognition via shortest paths computation: a version of Valiant's algorithm
• Certified context-free parsing: a formalisation of Valiant's algorithm in Agda
• Parallel recognition and ranking of context-free languages
• On the parallel recognition of unambiguous context-free languages
• On the complexity of parallel parsing of general context-free languages

Cites work

• General context-free recognition in less than cubic time
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)

Cited in

(1)

• Context-free recognition via shortest paths computation: a version of Valiant's algorithm

This page was built for publication: A simple proof of Valiant's lemma

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