✦ LIBER ✦

A homomorphism theorem for weighted context-free grammars

✍ Scribed by Donald F. Stanat

Publisher: Elsevier Science
Year: 1972
Tongue: English
Weight: 731 KB
Volume: 6
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(72)80003-5

No coin nor oath required. For personal study only.

✦ Synopsis

Productions of a context-free grammar can be given coefficients from semirings, inducing weights for both derivations in the grammar and strings over the terminal alphabet. For a weighted context-free grammar in Greibach normal form, the weight of any string, as well as the set of derivations of the string, may be determined from the image under a homomorphism which maps each terminal symbol to a polynomial. The definition of the homomorphism is a straightforward function of the productions. Some examples of interesting semiring structures are included.

📜 SIMILAR VOLUMES

Polymorphic malware detection and identi

Polymorphic malware detection and identification via context-free grammar homomorphism

✍ Gerald R. Thompson; Lori A. Flynn 📂 Article 📅 2007 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 158 KB

A useful lemma for context-free programm

A useful lemma for context-free programmed grammars

✍ Jan Leeuwen 📂 Article 📅 1979 🏛 Springer-Verlag 🌐 English ⚖ 663 KB

On a covering relation for context-free

On a covering relation for context-free grammars

✍ Eljas Soisalon-Soininen; Derick Wood 📂 Article 📅 1982 🏛 Springer-Verlag 🌐 English ⚖ 784 KB

A new algorithm for regularizing one-let

A new algorithm for regularizing one-letter context-free grammars

✍ Ştefan Andrei; Salvador Valerio Cavadini; Wei-Ngan Chin 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Language modeling using stochastic conte

Language modeling using stochastic context-free grammars

✍ A. Corazza; R. De Mori; R. Gretter; G. Satta 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 593 KB

A method for the inference of non-recurs

A method for the inference of non-recursive context-free grammars

✍ C. Chirathamjaree; Martin H. Ackroyd 📂 Article 📅 1980 🏛 Elsevier Science ⚖ 438 KB

A practical method is presented for the automatic generation of a non-recursive context-free grammar (cfg) from a set of strings that the cfg is required to be capable of producing. The method is efficient in computing time by comparison with enumerative methods.