The Formal and Processing Models of CLG

The Formal and Processing Models of CLG Luis DAMAS Nelma MOREIRA University of Porto, Campo Alegre 823 P-4000 Porto luis@nccup.ctt.pt Giovanni B. VARILE CEC Jean Monnet Bldg. B4fl)01 L-2920 Luxembourg nino@eurokom.ie Abstract: We present the formal • processing model of CLG, a logic grammar formalism based on complex constraint resolution. In particular, we show how to monotonically extend terms and their unification to constrained terms and their resolution. The simple CLG constraint rewrite scheme is presented and its consequence for CLG's multiple delay model explained. Keywords: Grammatical formalisms, Complex constraint resolution. Introduction CLG is a family of grammar formalisms based on complex constraint resolution designed, implemented and tested over the last three years. CLG grammars consist of the description of global and local constraints of linguistic objects as described in [1] and [2]. For the more recent members of the CLG family, global constraints consist of sort declarations ~md the definition of relation between sorts, while local constraints consist of partial lexical and phrasal descriptions. The sorts definable in CLG are closed, in a way akin to the ones used by UCG 13]. Relations over sorts represent the statement of linguistic principles in the spirit of HPSG [4]. The constraint language is a classical first order language with the usual unary and binary logical connectives, i.e. negation (-), conjunction (&), disjunction (I), material implication (---)), equivalence (,-)) and a restricted form of quantification ('7' and Zl) over finitely instantiatable domains. The interpretation of these ¢onneclives in CLG is strictly classical as in Smolka's FL 16] and Johnson's AVL [5], unlike the intuitionistic interpretation of negation of Moshier and Rounds [7]. A more detailed description of CLG including its denotational semantics can be found in 121. In this paper we present the tormal processing model of CLG, which has been influenced by the Constraint Logic Programming paradigm 18] 191. We show in what way it extends pure unilication based formalisms and how it achieves a sound implementation of classically interpreted first order logic while maintaining practical computational behaviour by resorting to a simple set of constraint rewrite rules and a lazy evaluation model for constraints satisfaction thus avoiding the problem mentioned in I10] concerning the non-monotonic properties of negation and implication intcrpretcd in the Herbrand universe. The paper is organized as follows: in the first part we show how we extend term unification to accommodate complex constraint resolution. We then explain what rewrites are involved in CLG constraint resolution, proceeding to show what the benefits of the delayed evaluation model of CLG are. We conclude by discussing some of the issues involved in our approach and compare it to other approaches based on standard first order logics. From Unification to Constraint Solving We will first show how to extend a unilication based parsing algorithm for a grammar formalism based on an equational theory, to an algorithm for a formalism with complex constraints attached to rules. Assume a countable set V of variables x, y, z, ... and a countable set F …

Content truncated to 500 words