|
|
Resolution of Complex Constraints on Trees and Applications in Logic Grammars
Nelma Moreira
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150-180 Porto, Portugal
Dezembro de 1997
Abstract
In recent years, symbolic constraints have raised a considerable
interest in several areas of computation and particularly in the
Computational Linguistics community. As a matter of fact constraints
over the algebra of rational trees can significantly contribute to the
reduction of the search space of problems in Natural Language
Processing, while increasing the formalisms expressive power. In this
thesis we developed a formal and computational framework for
constraint languages over the algebras of finite, rational and feature
trees. Although, the first-order theories of these algebras are
decidable, they are computationally intractable. Our goal was to
design a formal model and decision procedures to face that problem,
and that have been (successfully) used in the implementation of several
grammar formalisms, called constraint logic grammars (CLG).
The main contributions of this thesis are:
- Complete solvers for complex constraints in the algebras of
finite and rational trees. In order to face the NP-hardness of the
satisfiability problem for complex constraints, our approach
was based in factoring
out, in polynomial time, deterministic information contained in a
complex constraint, simplifying the remaining formula using that
information and delaying as much as possible the explosion of
disjunctions. We also developed rewrite systems for detection of
common factors in disjuncts and rewrite systems that use negative
information for the simplification process. We investigated the
problem of eliminating negative constraints and presented a
decision procedure for finite signatures.
- Establishment of a relation between the algebra of rational
trees and the algebra of feature trees, such that the satisfiability
problem in one can be reduced to the satisfiability problem in
other.
- A method for the computation of the minimal models of certain
classes of satisfiable constraints. These characterizations are
useful to simplify and to detect equivalent constraints.
- A low-level implementation of the main features of the complete
solvers.
- A higher order tree descriptions calculus based on a typed lambda-calculus,
which extended the previous techniques developed for resolving complex
constraints. The higher order tree descriptions were used as semantic
representations in categorial grammars for Natural Language.
|
