×

Representation of metamorphosis grammar in logic grammar: Proof trees and their lengths. (English) Zbl 0830.03012

Summary: We consider the representations of metamorphosis grammar in logic grammar, more precisely in Horn predicate logic, developed by A. Colmerauer [“Metamorphosis grammar”, Lect. Notes Comput. Sci. 63, 133- 189 (1978; Zbl 0378.68045)]using the idea of difference lists. For the proofs in metamorphosis grammar in normal form the so-called normal length of the proof is defined and it is shown that this length equals the length of the corresponding proof in logic grammar.

MSC:

03B65 Logic of natural languages
03F20 Complexity of proofs
68T50 Natural language processing

Citations:

Zbl 0378.68045
PDFBibTeX XMLCite
Full Text: EuDML EMIS