Inherently Reversible Grammars, Logic Programming and Computability
Marc Dymetman · 1991
This paper attempts to clarify two distinct notions of "reversibility": (i) Uniforraity of implementation of parsing and generation, and (ii) reversibility as an inherent (or intrinsic) property of gram- mars. On the one hand, we explain why grammars specified as definite programs (or the various 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 finile reversibility, which says that both parsing and generation 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 enumerability of parsing is equivalent to finite enumerability of generation.