Inherently Reversible Grammars, Logic Programming and Computability

Inherently Reversible Grammars, Logic Programming and Computability Marc Dymetman CCRIT, Communications Canada 1575 boulevard Chomedey Laval (QuEbec) HTV 2X2, Canada dymetman@ccrit.doc.ca ABSTRACT This paper attempts to clarify two distinct notions of "reversibility": (i) Uniformity of implementa- tion of parsing and generation, and (it) reversibil- ity as an inherent (or intrinsic) property of gram- mars. On the one hand, we explain why gram- mars specified as definite programs (or the vari- ous related "unification grammars") lead to uni- formity of implementation. On the other hand, we define different intrinsic reversibility properties for such grammars--the most important being finite reversibility, which says that both parsing and gen- eration are finitely enumerable (see text)-- and give examples and counter-examples of grammars which possess or do not possess these intrinsic properties. We also show that, under a certain "moderation" condition on linguistic description, finite enumer- ability of parsing is equivalent to finite enumerabil- ity of generation. 1 Introduction From the linguist's point of view, a grammar is a formal device which defines a recursively enumer- able set of well-formed linguistic structures, each having, among other aspects, a phonological con- tent (or, when dealing with written text, a string content) and a semantic content. Such a device is completely neutral as regards its uses for parsing (recovering semantic content from string content) or generation (recovering string content from se- mantic content). From the computational linguist's point of view, on the other hand, the problem is how to imple- ment such a grammar both as a parsing program and as a generation program, in such a way that these programs exactly reflect the content of the grammar. This we will call the reversibility prob- lem. Let us assume, for specificity, that the grammar has been presented as a definite program (a Prolog program)J Then the reversibility problem has a simple solution: use a complete interpreter for defi- nite programs--for instance a top-down interpreter having a breadth-first search procedure2--and di- rectly use the grammar as the program both for parsing and for generation. In the parsing mode, for any given string x, the program will enumerate all semantics Yl,Y2,... assigned to it by the gram- mar, and similarly, in the generation mode, for any given semantics y, the program will enumerate all semantics xl, x2,.., assigned to it by the grammar. This is a striking property of definite programs: they are reversible in the sense that they naturally lead to uniformity of implementation of the parsing and generation modes (see §4). So the reversibility problem is solved, and we can spend the next few years skimming through Fodor's (not Jerry's) guides in travel bookstores? Not quite. First, the standard depth-first inter- preter for definite programs is an incomplete one, and this problem must be circumvented in some way. Second, and more crucially, even when us- ing a complete interpreter, parsing (and similarly generation) does not in general terminate: the pro- gram may well enumerate Yl,Y2,... ad infinitum. This is even true if, in fact, there are only …

Content truncated to 500 words