• Nu S-Au Găsit Rezultate

UNIVERSITY OF LILLE I

N/A
N/A
Protected

Academic year: 2022

Share "UNIVERSITY OF LILLE I"

Copied!
139
0
0

Text complet

(1)

UNIVERSITY OF LILLE I

LABORATORY OF THEORETICAL COMPUTER SCIENCE

Ph.D. Thesis in Computer Science

DF { A FEATURE CONSTRAINT

CONCURRENT SYSTEM

with application to Natural Language

Processing

presented on December 9, 1996 by

Liviu-Virgil CIORTUZ

Jury:

Jean-Paul DELAHAYE Professor, LIFL Lille, PhD Superviser Philippe CODOGNET Dr. Hab., CNRS, Reviewer

Andreas PODELSKI Dr. Hab., MPI Saarbrucken Max DAUCHET Professor, LIFL Lille

Philippe DEVIENNE Dr., INRIA Requencourt Philippe MATHIEU Dr., MC, LIFL Lille

U.F.R. d'I.E.E.A. B^at. M3 { 59655 VILLENEUVE D'ASCQ Cedex FRANCE

(2)

To Filip

In memoriam of Eugen Prudi

(3)

Acknowledgments

I thank rstly my mother, Aneta Ciortuz, simply for having accepted me to be.

Thanks from the deep of my being to the young people who died in December 1989 in Romania, thus oering to the young scientists the opportunity to go abroad and continue their studies; one of those who benet from their sacrice am I!

I am much indebted to Professor Jean-Paul Delahaye from the University of Lille, who accepted me as one of his Ph.D. students. He wisely provided me with the ne guidance and friendship I needed so much during my three stages in the Laboratory of Theoretical Computer Science at Lille. And I will always be thankful to France for having given me this doctoral scholarship.

I am grateful to Professor Hans Uszkoreit from DFKI, University of Saarbrucken, Ger- many, and to Professor Philippe Codognet from INRIA-Recquencourt, France, who have kindly accepted to be the reviewers of my thesis. Thanks to Professor Gert Smolka from the University of Saarbrucken, and again to Professor Hans Uszkoreit, for having invited me two times as a visiting researcher at DFKI. Maybe they will never know of how much invaluable help these visitings provided me.

I was much honored by the fact that Dr. Andreas Podelski from the Max Planck Institute fur Informatik in Saarbrucken has accepted the proposal of Prof. Hans Uszkoreit to take part in the jury of my thesis. This honor obliges me a lot!

Thanks go also to my colleagues: Henri Luchian who forwarded me an early report on F-logic, Cristian Papp who suggested me to search for a good way to do top-down inferences in F-logic, and Dorel Lucanu who made me know about DFKI even before my coming to France. I mention here also the names of my colleagues Anca Ignat, Mirela Petrea, Mihaela Juganaru and Liliana Ibanescu from the University of Iasi { Romania, and of Jean-Cristophe Routier, Anne Parrain, Jean-Marc Talbot and Bruno Beauls from the University of Lille, for they have helped me to nish several research papers that led to this thesis. Thanks to Dorel Lucanu and Luca Dini for the attentive proofreading on an earlier version of Chapter 1, and respectively helpful discussions on Chapter 3.

I will never forget the invaluable moral support oered by my friend Dan M^anastireanu who many times said me (with, and mostly without words) that if I do science then I must do it at my best.

During the time I was working on my Ph.D., I have benet from much administrative help (both in Romania and France) oered by: Professor Constantin Cazacu, Professor Calin Ignat, Dr Philippe Devienne, Professor Cornelius Croitoru, Dr Cristea Dan, Professor Jean-Pierre Steen, Mme Cristiane and Mr Roland Pesenti, Dr Philippe Mathieu, Daniela Ciuca, Vicky and Robert McCuistion, Sitou Gayibour, Paul Zabet, Idelette Brieu, Gabrielle Rudolf, and last but not least Dr Louay Hatem, Mme Boutet from the French Consulate at Brussels and Mme Veronique Majeste-Larouy from the French Embassy at Bucharest.

From all my heart I thank my wife Angela who accepted the dicult task to be single while I was working away of our home, and also our son Filip who will never have back these last years as he would deserve, caused of mine. Angela and Filip will be the single two persons whom I will reimburse the time they have given me in order that this thesis get done. In the case of all others, possibly not named above by mistake, I'll try to discharge my debt to them by helping others, especially students at my university in Romania.

Lille, October 20, 1996

(4)

Contents

1 DF | Feature Constraint System 7

1.1 Introduction . . . 8

1.1.1 An overview of the Feature Constraint Theory . . . 8

1.1.2 Why another feature constraint system? . . . 11

1.2 DF Constraints . . . 14

1.2.1 DF Logic records . . . 14

1.2.2 DF Logic semantics . . . 16

1.3 DF Normalization . . . 20

1.3.1 DF Basic normalization . . . 21

1.3.2 Reference signatures . . . 24

1.3.3 DF Denite normalization . . . 30

1.3.4 DF-Theory relative simplication . . . 34

1.4 DF-resolution and Concurrency . . . 38

2 DF { Concurrent Implementation 45

2.1 Introduction . . . 46

2.1.1 Why do we choose concurrency to implement DF? . . . 46

2.1.2 Oz essentials . . . 47

2.2 Interpreting DF . . . 49

2.2.1 Higher-order functionality, and writing a syntax analyzer in Oz . . . 50

2.2.2 Abstracting variables over data structures in Oz, and writing open record constraints . . . 52

2.2.3 Providing concurrent stateful variables, and parallel unication on data structures in Oz . . . 54

2.2.4 Concurrent synthesis of DF-logic programs, and ... starting the inference engine . . . 57

2.3 Beyond interpreting DF . . . 60

2.3.1 How could DF be compiled into Oz? . . . 61

2.3.2 A rst running example in DF: A Machine Translation demo with binary HPSG rules . . . 62

3 DF | Application to NLP: An HPSG Kernel for Romanian 71

3.1 Introduction . . . 72

3.1.1 Background . . . 72

3.1.2 Meta-language . . . 73

(5)

3.2 On Romanian noun-headed NP:

deniteness, topic and modication . . . 74

3.2.1 On NP deniteness and topic . . . 76

3.2.2 On NP modiers . . . 81

3.3 On transitive VP linearization and clitic pronouns in Romanian . . . 85

3.3.1 Specic background . . . 86

3.3.2 Immediate dominance and linear precedence in the Romanian transitive VP . . . 87

3.3.3 On Romanian clitic pronouns . . . 91

3.3.4 More on the NPA rule and NP modication . . . 94

3.4 Constraint-concurrency issues complementary to the Romanian HPSG kernel . . . 97

3.4.1 Open constrained determiners . . . 98

3.4.2 Free adjunction into the Romanian VP . . . 100

3.4.3 Towards concurrent parsing of the Romanian VP . . . 101

3.4.4 Head-corner parsing in DF . . . 104

A 110

A.1 An overview of F-logic . . . 111

A.1.1 F-Logic syntax . . . 111

A.1.2 F-Logic semantics . . . 111

A.1.3 Semantic F-structures vs. DF-constraint algebras . . . 115

A.2 More on Oz Essentials . . . 116

A.2.1 The Oz underlying functional constraint calculus . . . 116

A.2.2 Concurrent object-orientated programming in Oz . . . 118

A.2.3 Encapsulated search in Oz . . . 119

A.3 Appendix: HPSG Principles . . . 121

A.4 A head-corner parser implemented in Oz . . . 124

B The Oz Code for DF Implementation 133

(6)

\Every question has a power that does not lay in its answer."

A rabbi from Transylvania, cited by Elie Wiesel

(7)

Introduction

General settings

The last decades in the overall progress of humanity have been denitely marked by the explosive development of the information science. Not only that it was intended as an aid for humans' activity, but it was much hoped to lead humanity to its better self-understanding.

Speaking about the human way of being, what could be considered before language?

More or less ready to accept it, maybe after long debates, we have to recognize nally that in the beginning nothing could be butoo, the language.

Similarly, but to another level, in information and computer science it was logic rst, and then logic as a ...language, a programming language. I found much signicant the fact that the rst system intended to \speak" logic as a programming language did human language processing. It was Alain Colmerauer's Q-System, the precursor of the further consecrated Prolog language. Since then a lot of research eort was put into this amazing confulence area of logic and language.

Every new trend in computational logic was more or less converted to a better approach to problems in the eld of Natural Language Processing. This is particularly true for a relatively recent open direction in computational logic, that of constraint logic programming.

Things in this domain arrived to a certain maturity when scientists were asking: What about using constraints in NLP? Important answers were already given, some of them building up the best modern approaches to grammaticality of human language, as it is the case with the theory of HPSG (Head-driven Phrase Structure Grammar).

Nowadays, as constraint logic programming has been generalized to constraint concurrent programming, the above question naturally gets a new form: What about using constraint concurrency in NLP? Answering this question is open. Here is where, among others' recent works, our thesis comes.

Specic settings

The present thesis is the result of a personal eort to combine interesting ideas from some new directions in logic programming

| Object-Oriented Logics,

| Feature Constraint Systems,

| Concurrent Constraint Programming,

with the aim to develop an experimental concurrent constraint system applied to Natural Language Processing, using mainly HPSG grammars.

As main research sources from these directions, serving as departure basis for our work, we followed respectively:

F-logic, by Michael Kifer, Georg Lausen and James Wu [61];

(8)

OSF and CFT systems, by Hassan At-Kaci and Andreas Podelski [5][8], respectively Gert Solka and Ralf Treinen [93];

thecc and OPM models, of Vijay Saraswat [85], and respectively Gert Smolka [97];

and

the HPSG theory of Carl Pollard and Ivan Sag [83].

The above referred directions have been \generative" in the present work in the following respects:

DF is a feature constraint system with F-logic declarative semantics, and

constraint operational semantics based on concurrent rewriting rules;1

DF is implemented as a prototype system using Oz, the DFKI internal release 1.9.13, by dening a static \open" typed alternative to its object-oriented sublanguage;

and

DF is applied to Natural Language Processing: head-corner parsing, head-driven genera- tion and binary HPSG-based Machine Translation.

We have designed, by adding some interesting extensions to the HPSG general theory, a concurrent HPSG grammar kernel for Romanian.

The three parts/chapters of the thesis correspond respectively to the above stated points.

Here it follows a brief presentation of the coming chapters.

Overall Structure

Chapter 1: DF Constraint System

This rst chapter of our thesis presents DF as a feature constraint system. Starting from the the two major approaches in the eld | the OSF system2of H. At-Kaci and A. Podelski [5], and the CFT system3of G. Smolka and R. Treinen [93] | the DF system provides for new signicant characteristics: a rst-class citizen status oered to (both features and) sorts, ner grained constraints using arguments as features' application context, functional single- and multi-valued features, well-type conditioning between feature values and types, and principle-based completion of the sort signature.

The starting point back into the beginning of our research was the work of M. Kifer, G.

Lausen and J. Wu known shortly as F-logic [61], which was designed as \a logical foundation for object-oriented and frame-based languages". Our aim was to make F-logic4 useful as a concurrent logic programming language.5 This approach is based mainly on dening a comprehensive feature constraint system, DF, using the F-logic's declarative semantics, and denitely changing its operational counter-part into a concurrent constraint-based semantics, allowing one to work with conditional, open sort hierarchies that could be completed at the run time.

1The aspect of concurrency/mutable states for objects in M. Kifer's work is given by Transaction Logic, which is orthogonal to F-logic. Bibliographical references: TCS, vol. 133, Oct. 1994, and Technical Report CSRI-323, Nov. 1995.

2OSF stands for Order-Sorted Features.

3CFT stands for Constrained Feature Trees.

4F stands for Frame, DF stands for Data(log) Frames.

5Since my work was in progress, an implementation of F-logic was made available by its authors at the WWW site http://www.cs.sunysb.edu, but this is a bottom-up, non-concurrent interpreter.

(9)

Chapter 2: DF Concurrent Implementation

This second chapter presents a concurrent implementation for DF, our feature constraint system. We accomplish this task using as programming support Oz, a higher-order functional concurrent-constraint object-oriented language.

After a brief synthesis on Oz, an interpreter for DF is presented. Concurrent-constraint programming constructs and techniques implemented during this work | like concurrent goal solving using lazy trees, concurrent synchronizing (agent-like) stateful variables, con- current unication of order-sorted data, and concurrent completion/synthesis of DF-logic programs | are equally described here.

Finally, a preliminary study for compiling DF-logic programs into the object-oriented subset of Oz is started, and a demo DF program doing Machine Translation from English into French and Romanian, based on binary HPSG rules, is presented.

Chapter 3: DF Application to NLP

This third chapter in the present thesis opens the door for the application of DF, our concurrent constraint system, into the eld of Natural Language Processing (NLP).

We design a grammar kernel for Romanian in the framework of the Head-driven Phrase Structure Grammar (HPSG) theory [82], [83]. Firstly the topic and deniteness of Romanian noun-headed NP are studied, and we account mainly on a combined lexical and semantic rule-governed basis for the NP high order-freedom. Further on, linked to the transitive VPs, the status of Romanian clitic pronouns is explained in a combined syntactic-lexical approach.

Along with this (rst) major attempt in the literature to write an HPSG kernel for Roma- nian, some useful generalizations in the general theory of HPSG are proposed: a generalized form of the Immediate Dominance (ID) schemata allowing \free" adjunction, and two ID meta-schemata, to be used one for \stacking" multiple subjects (like Romanian multiple determiners), and the other for concurrent processing of certain Unbounded Dependency Constituents (UDC).

A concurrent parser kernel for Romanian both in Oz and DF is nally implemented in this concurrent approach, using the head-corner technique of G. van Noord [103].

Specic contributions

In a somehow more compact perspective, our present work can be seen as made of two parts: the DF System, with theoretical design { Chapter 1, and concurrent implementation { Chapter 2, and the Romanian concurrent HPSG kernel (here abbreviated as the HPSG RoCK System), also with theoretical design and concurrent implementation { both reported in Chapter 3.

The work reported in the rst part of the present thesis has started with the aim of getting a programming language working in the F-logic settings. We were interested in having a top-down inference algorithm that would manage conveniently the thirteen rules designed by Michael Kifer and his colleagues in F-logic's operational semantics. (This was intended mainly for bottom-up inferences in frame-based and object-oriented databases.) We have initially used an algorithmic approach [25], inspired by [4]. Having \discovered" then the OSF and CFT papers, we have converted our work to a feature constraint approach [26],[29].

Finally we nd out that concurrency can be naturally added to DF when using it to do logical inferences.

We dened-terms (a Datalog parameterization of Kifer's F-terms, and a generalization of At-Kaci's -terms), as particular conjunctions (\positive clauses") of elementary posi-

(10)

tive DF-constraints: is-a derivations, equations, and dierent kinds of feature constraints (\methods"). Then DF-logic formulae have been naturally introduced on top of-terms.

Normalization, that put positive DF-clauses under a solved form, served the DF system to be eectively born, similarly to the OSF and CFT systems. In fact, things get dierent just there, since the solved form of a positive DF-clause was chosen so that it be satisable (which is not the case for OSF and CFT). We continued with extending normalization to denite (Horn-like) DF-theories, allowing us to reason on conditional open hierarchies of rst-class sorts. That denite normalization is a form of program inference rule-based synthesis that we simply called \completion".

Further on, the DF system was provided with an unitary/interleaved operational view on-term unication and deduction in denite DF-theories, that we addressed as \relative simplication".6

Concurrency came in DF when

1. The sort hierarchy was left open, i.e. it was allowed to be completed by a process (based on well-typing conditioning) synchronized with the relative simplication process carried by the logical top-down DF-inference engine.

2. The concurrent environment in which DF was implemented (DFKI Oz) supported concurrent-based parallel inference \engine-copy" processes, thus allowing for conditional sorted unication to be concurrently run with the (main) inference process.

3. We renounced to impose the completeness condition on the DF-logic denite the- ory/program, in favour of a local reactive completion mechanism, using dierent heuristics to apply denite normalization rules.

4. We introduced the concurrent tell meta-predicate on functional uni- and set-valued feature constraints, to extend -terms at the DF-program's run time. While thistellmeta- predicate in DF has a \closed type universe" declarative semantics, a form of \open" tell, and also a sort of localaskare under investigation.

An overview of the DF feature constraint concurrent system is shown in Figure 0.1.

Now, concerning the second part, that of the Romanian HPSG concurrent kernel, we have started our work simply asking how the general framework of HPSG theory serves for a formal description of the Romanian language, and (only then) expecting to see how could it be converted into a concurrent constraint parsing implementation.

Our conclusion was a twofold one:

First, HPSG is powerful and exible (almost) enough to provide the declarative in- strumetary needed to explain in a unitary view the important linguistic issues we have dealt with | the deniteness and topic of Romanian noun phrases and the linearization of transitive verb phrases, intimately related to the clitic pronouns' generation.

Second, in the virtue of its highly declarative conception, the HPSG theory opens the door for setting up new interesting procedural approaches, in particular in concurrent con- straint Natural Language Processing. That is of a quite new (and much expecting) interest in both NLP and CL (Computational Linguistics) communities.7

We will briey present here the concurrency's specic apport we've got in implementing an HPSG kernel for Romanian.8

6We still query ourselves whether we did not too much by putting them two together. Our current answer is: If there were no concurrency to be added, we would renounce!

7See the NEGRA project started at DFKI - University of Saarbrucken.

8In this last part of our work, not only we were concerned with testing the DF capacity to take o as a demonstrative constraint concurrent system on its own power, but also we wanted to apply a full-edged concurrent constraint language { Oz { into an intriguing project: concurrent parsing for natural language.

This is why we have implemented the RoCK HPSG system in both DF and Oz variants.

(11)

Normalization

DF

concurrent synchronization

concurrency-based

OR-parallel inferences AND-parallel

concurrent operations

conditional sorted unification

implicit ask tell

Completion Definite DF-Theory

Relative Simplification local reactive

resumption

type-checking

Figure 0.1: An overview of the DF feature constraint concurrent system.

1. Using logic variables in concurrent constraint programming allows for an elegant and much simplied treatment of otherwise hardly to manage linguistic phenomena, like staking multiple subjects (as it is the case with multiple determiners in Romanian NP).

In an orthodox HPSG approach, that would require to state a new ID Schema (we would call it the \Head-Tail" Schema), that is not at all simple to accept, since it has to block the powerful Subcategorization Principle, asking it not to consume the head's subcatlist, while telling more (sub)components to thecompDslist of the newly generated mother phrase structure.

In our concurrent approach, we have used logical monotonic constrained variables to state an extension of the ID Schema 1 in [83], that we call the ID Meta-Schema 1. To- gether with the new predicative feature stacking in the lexical descriptions associated to stacking subjects, and making use also of the spec feature on stacked signs, it works in a straightforward manner!

2. Concurrent constraint programming allows a smooth integration of bottom-up and top-down parsing strategies:

Free -adjoining/modication in Romanian verb phrases (but in stacking determiners too) has lead us rstly to dene the notion of M-contiguity, and then to generalize accordingly all the ID rule schemata in [83].

From the procedural point of view, we have split VP analysis into two processes, one for modiers' recognition (done in a bottom-up manner), and the other for the verb's sub- ject and complements' analysis (top-down). These two processes run concurrently and get synchronized again directly, using logically constrained variables.

(12)

3. Logical synchronization of processes in concurrent constraint computation provides for a powerful tool to be used at the meta-level upon the HPSG rules.

HPSG is free in the way one could use its rules, up to one simple restriction that one would express as: \Apply only one rule at a time on the given entry!".

The alternative, concurrent constraint correlation of \two or more rules" (applicable at dierent points in time) provides a direct, clean and much simpler approach on specic lin- guistic ground (like clitics' generation in Romanian) then the sequential, commonly assumed, approach.

This correlation of parsing schemata is achieved in our analysis of Romanian transitive VPs by the newly proposed ID Meta-Schema 2/6, a concurrent constraint composition of the Schema 2 (Head-Complement) and Schema 6 (Head-Filler) in [83].

An overview of the HPSG Romanian kernel system RoCK is oered in Figure 0.2.

noun-h. NP transitive VP

long infinitives

lexical rules

HPSG RoCK

NPA CP SO OFP

clitics

subCat* strictCat

linearization

ID Schema 2 ID Schema 6

ID Schema 2/6 M-contiguity

M-adjunction

syntactic rules marking p. feature

definiteness topic

DEF rule

classic HPSG

stacking-determiners

NP Modifiers C.

ID Meta-Schema 1

concurrent HPSG

Figure 0.2: An overview of the HPSG Romanian Concurrent Kernel system.

(13)

DF | Feature Constraint System

Abstract

This chapter presents DF, as a feature constraint system that starting from the the two major approaches in the eld | the OSF system of H. At-Kaci and A. Podelski [5], and the CFT system of G. Smolka and R. Treinen [93] | provides for new signicant characteristics: a rst-class citizen status oered to (both features and) sorts, ner grained constraints using arguments in the feature context, functional and/or multi-valued features, well-type conditioning between feature values and types, and principle-based completion of the sort signature.

We were inspired in our work by M. Kifer, G. Lausen and J. Wu' F-logic [61], which was designed as \a logical foundation for object-oriented and frame-based languages". The starting idea was to dene an (alternative, i.e. non-conventional) operational approach in order to make F-logic useful as a concurrent logic pro- gramming language. This aim was nally reached by dening a comprehensive feature constraint system, namely DF, using a \constraint" variant of the F- logic's declarative semantics, and remaking completely its operational semantics.

(14)

1.1 Introduction

We dene DF, a feature constraint system working on-terms, which are higher-order logic records extending Hassan At-Kaci's -terms [4], that were dened in turn as a generalization of rst-order terms, using order-sorted features.

This present section surveys the DF system's background, namely the theory of feature constraints, and then oers an account on what distinguishes DF with respect to well-known feature constraint systems. Section 1.2 introduces the syntax and the logical semantics of DF.

Then, Section 1.3 provides the operational approach for DF-clause solving and conditional conditional sort signature completion via | simple and then denite | normalization rules.

Further on relative simplication rules are given, to carry both the-term matching and the satisability test of DF-logic programs, as DF-clause entailment. Finally, interesting points on how to put concurrency inside DF are presented in Section 1.4.

This work was partially published as [26], and [29].

1.1.1 An overview of the Feature Constraint Theory

Feature descriptions were rstly introduced in logic just as syntactic constructs, together with an appropriate unication operation. This was for instance the case of -terms [4], when the LOGIN language has extended Prolog with \built-in" inheritance.

Then semantic foundations for feature descriptions were given: after Kasper and Rounds [58] have used a non-standard logic, Johnson [54] and Smolka [92] used fragments of rst- order predicate logic to interpret feature descriptions. Smolka [92] also established a canon- ical model interpreting feature descriptions as feature graphs.1

Unication in these approaches is reduced to satisability of formulae representing fea- ture descriptions, eventually in the canonical feature graph model. Later on, Smolka and Treinen [93] have introduced the arity constraint which specify the nite set of admissible features for a node in a feature description. A new canonical model | based on feature trees, which are mathematically simpler then feature graphs | allowed to generalize constructor trees introduced by Alain Colmerauer in Prolog II.

Backofen [11] has investigated the expressivity of dierent rst-order logic languages over feature trees. It was shown that the Treinen'sF language [99], which allows for \rst-class"

features, i.e. features that can be variables, is very expressive, accounting for set encoding, subsumption and functional uncertainty.

Manandhar [66] investigated set constraints, and Dorre [38] proposed week subsumption constraints.2

Finally, a modal logic approach for feature descriptions was considered for instance in [13]. Its transformation to fragments of second- and rst-order predicate logic, preserving in many cases the theoretical properties, seems to lead to two dierent { to some extent convertible { views on the feature constraint's domain.

1A feature description is satisable i it is satisable in the canonical model of feature graphs.

2Givenxandytwo feature descriptions,xsubsumesy(notationally:xvy) i i. whenever a pathpis dened forx, then it is also dened fory, and

ii. whenever two pathspandqlead to a same node inx, thenpandqmust also lead to the same node iny.

Weak subsumptionrequires only the condition i.

(15)

Decidability results

Synthesizing informations found mainly in [16], we group here the most important decid- ability results in the feature constraint theory:

Order-sorted unication of purely conjunctive feature terms over an inferior lattice is decidable with a quasi-linear complexity [4].

Entailment checking for feature logic descriptions is quasi-linear [7], [93].

It was shown [54] [55] that feature logic can be formulated in a decidable fragment3 of the rst-order logic,

Satisability of the existential fragment of feature logic (including conjunction, dis- junction and negation) is decidable with an NP-complete complexity [53], [92]. This result is maintained if quantication over features as rst-class citizens is allowed [99].

Satisability of feature terms containing functional uncertainty4is decidable [57], [11], [12]. Functional uncertainty with full negation is undecidable [10], though weak func- tional uncertainty (even with full negation) is decidable [38].

Satisability of feature description with subsumption constraints is undecidable [39].

Satisability of typed feature description w.r.t. a type system under least xpoint semantics is undecidable [92]. A partial-decidability result for type systems (missing disjunction) with greatest xpoint semantics appeared in [7].

Also, the decidability of a calculus for set feature constraints has been proven in [66] with an NP-complexity, and there is a complete axiomatization of the theory of feature trees in the feature logic with arity constraints [13], [15].

Feature constraint systems

The interest for feature constraint systems emerged after the seminal work of Gert Smolka [92] was successfully characterizing early unication-grammar formalisms like LFG, FUG, PATR-II [56], [59], [89] into predicate logic. Constraints in these formalisms were expressed as rst-order formulae with equality, and a general method to decide their satisability was designed.

The way was thus opened to better specify the tree constructor terms in Herbrand, the constraint system underlying Prolog II. Then FT, a newly dened constraint system based on feature terms [8], emerged to CFT [93] by incorporating arity constraints, and it was nally chosen to underlie the concurrent constraint language Oz [94]. Completeness results for FT and CFT were proven by Backofen and Treinen [15], respectively by Backofen and Smolka [14].

In parallel with this work, and sometimes even prefacing its phases, feature constraints were used to incorporate in a straightforward way the inheritance principle in the area of logic programming. This was done rstly by generalizing rst-order terms, for instance to -terms [4], [5], [6] and later on by using concurrent constraint stateful objects in Oz. - terms support an extended unication procedure (which makes logic programming even more

3This fragment is calledSchoennkel-Bernay.

4Functional uncertainty is expressed via regular expressions over features:xLy. It holds iyis value on some path starting from .

(16)

x[f]

xF

x f a

x/SOR x/FEA

Ax

CFT

x=y x[f]y

x:a

EF

OSF FT F

DF

Figure 1.1: An overview of Feature Constraint Systems

suitable for Natural Language Processing), while preserving the soundness and completeness of the classical SLD-resolution (correspondingly enhanced).

Our present aim is to follow the previously mentioned works, but starting from a rather dierent attempt to express the object-orientation paradigm in logic, namely Michael Kifer et al.' F-logic [61]. We preserve the F-logic high expressivity up to restriction to Datalog terms instead of Prolog ones to denote complex objects and classes.5 We replace the F- logic's rather complicated6 operational semantics, suitable for bottom up inferences, with another | hopefully simpler | one based on constraint handling rules, allowing for top- down inferences. The resulting constraint system is called DF. The appendix A.1 gives a brief introduction of F-logic, slightly adapted from [61]. 7

To enable visual comparison, a simple synoptic view on the above mentioned feature- constraint systems is given in Figure 1.1. It includes also the E and EF systems [99] which enhance FT, respectively CFT with a rst-class citizen status oered to features. DF extends this status to sorts also.8

Specic contributions aimed by the present work are the following:

| distinguishing between single- and multi-valued features, and also between features' values and their types;

| using arguments to dene the feature application context;

| doing principle-based type control (via well-type conditioning, argument sub-typing, range super-typing, and type inheritance);

5This restriction will be partially removed in the next chapter.

6It contains 13 inference rules!

7For the sake of uniformity, we do not dene atoms on top of terms, as F-logic does, using predicative symbols. We introduce instead a new type of methods, namely predicative methods in the denition of frame terms.

8In Figure 1.1, the notations x : a; x[f]y; xA; x[f] "; andxF denote respectively inheritance (the well-known \is-a" relationship from the theory of knowledge representation), feature constraint, equality, label constraint, non-deniteness (of a feature), and arity constraint. Also,x=SORandx=FEAmark the rst-class status of sorts and respectively features.

(17)

person

girl boy

jim mark

lucy

Figure 1.2: A (ground) reference sort signature.

| allowing for inferential completion of partially specied,9and possibly conditional sort signatures.

1.1.2 Why another feature constraint system?

The answer to this question of \common sense" is mainly twofold:

First, the need for a (concurrent) logic programming language working in the F-logic settings has led us to a \dedicated" feature constraint system, that diers signicantly from the previous ones, and which is appropriate for doing Natural Language Processing (mainly by declarative implementation of HPSGs). Unication and the inference work will be carried inside this constraint system by normalization and relative simplication rules.

Second, the OSF system | to which DF is obviously more linked (than to CFT) | has in our opinion two major limitations/restrictions10:

i. OSF is over-typed in a sense, since it uses sorts as feature values, and this is why it cannot ultimately dissociate between features' values and their types. (By the way, CFT is just the opposite: it is left completely untyped.) The following example makes clear our statement.

Example 1.1.1

Given the simple sort signature

girl:person boy:person lucy:girl mark:boy jim:boy:

shown in Figure 1.2, an OSF-like declaration lucy[likes)boy]

will make the goal

? lucy[likes)X] produce the answers

X=boy;X=mark;X =jim:

2

We consider that the informational \entropy" of the above response is too wide, since the previous type declaration implies thatlucylikes anyboy, and also the allboys' class too.

F-logic instead, and the DF constraint system too, make a clear distinction between features' values and types. This is achieved by

9The so-called \open" hierarchies.

10Which explain in fact its power.

(18)

imposing the relation)to declare only types.

So, in the above example, the declaration lucy[likes ) boy] means: if lucy likes something, then that is aboy).

introducing the functional correspondence!to denote (only) values.

For example, the fact thatlucylikes jimis (explicitly) declared by lucy[likes!jim]:

The correspondence between feature values and types is ensured (rst of all) by the so called well-type conditioning principle. In a simplied form, this principle is expressed as

object[feature!value] object[feature)type ]

)value:type:

ii. OSF assumes a sort/type11hierarchy completely specied at the syntax level (while CFT doesn't use sorts at all). However, it is often the case that the sort hierarchy we are involved with | and this is especially the case in NLP | is not a priori entirely known, or at least that a combined syntax{semantics (\run-time") completion approach is suitable from the user point of view. DF accomplishes this aim just by using the above mentioned well- typing principle. To get an idea of how things work, let's take the following DF denite12 program, that was inspired to us by [33].

Example 1.1.2

(C1) X[happy] : X:person[friend! ]: (C2) person[friend)person]:

(C3) Z[F !W] : W[F:symmetric!Z]: (C4) friend:symmetric:

(C5) albert:person:

(C6) albert[friend!lucy]:

(G0) ?-lucy[happy]: 2

The clause (C1) declares that apersonishappyif he/she has afriend, while (C2) says that anyperson'sfriendis aperson. Then, in the case of asymmetricfunction, the value commute with the respective invoking argument (C3). The facts (C4) { (C6) are declaring that friend is asymmetric function,albertis a person, andlucy is the friendof albert. We informally show how the predicative featurehappyis true forlucy.

The rst approach:

Following in mind a bottom-up strategy,albertinherits the typing of thefriendfeature from the person class (C2), since he is a person (C5). In a simplied form, the type inheritance principle can be expressed as

class[feature)type] object:class

)object[feature)type]: One could visualize the type inheritance eect by explicitly writing

11All along this work we will not distinguish between sorts and types. They both are consideredreferences (to be introduced formally in the next section). Feature values and arguments are references too. Just as a language convention, when referring to nodes (objects and classes) in a hierarchy, we will call themsorts, while referring to the class(es) to which values of one feature belong, we will call themtypes.

12In the well-known sense in logic programming.

(19)

albert lucy person

Z

F symmetric

friend T

W Y X

Figure 1.3: The run-time eect of principle-based completion of a sort signature.

(C7) albert[friend)person].

Now, due to the the well-typing conditions that link feature values and types, it follows from (C6) and (C7) thatlucy is aperson:13

(C8) lucy:person.

The eect of the run-time signature completion for this specic case is shown in Figure 1.3.

Furthermore, applying the clause (C1) to X =lucy, we will get that's enough for our goal to prove thatlucy has a friend:

(C9) lucy[friend!Y].

She has a friend indeed due to (C3), sincefriendis a symmetric function (C4) and there is someone whose friend is she, namelyalbert(C6). So, nally

(C10) lucy[happy].

The reader should note how DF oers a rst-class citizen status to features, for instance in the clause (C3). That clause says that any symmetric function commutes his argument with its caller.

The second approach:

What's really happening in DF is that we have adopted a combined strategy, namely top-down goal solving synchronized with bottom-up sort hierarchy completion. When ask- ing to solve the goal

(G0) ? lucy[happy]

a resolution process (RP) is started, that (following up the sort hierarchy) infers, using the clause (C1), the goal list

(G1) lucy:person;lucy[friend!Y].

The rst goal atom in (G1), which is a derivation constraint, is not solvable in the initial state of the sort hierarchy. Therefore, the resolution process (RP) suspends, raising up instead as a query just that derivation:

(E1) ? lucy:person

which is immediately solved by a \completion" process (EP) that does bottom-up entailment, via well-typing conditioning. Using (C6) and (C2), it infers thatlucy:personis true. This success resumes the resolution process (RP), so it continues with

13Note that OSF, and therefore the programming languages LOGIN and LIFE that emerged from OSF, are not capable of doing such an inference. (If it was not explicitly declared thatl ucyis aperson, then the given goal could not be solved.)

(20)

(G2) ? lucy[friend!Y].

This goal is solvable due to (C3).14 Thus we get (G3) W[friend!lucy].

which is reduced to the empty clause using (C6).

Obviously, in more realistic examples, things get more complicated: a \completion" pro- cess can raise a resolution process which in turn can suspend raising up another completion process, etc. If a completion process is not successful, then it may cancel the resolution pro- cess that generated him. Dierent heuristics for the sort hierarchy completion are possible.

Example 1.1.3

Here is another example, simply showing the use of set-valued features in DF: (S1) int[+int)int].

(S2) posint:int[stream!!0;

1 +posint:stream].

Assuming that + has the semantics of the well-known arithmetic operator, the goal

? posint:stream!!X

will generate the natural numbers' stream. The DF syntax in this example is a sugared one, with respect to that introduced in the next section. This example was inspired to us by [6].

2

To summarize, but also to introduce the next sections, essential in DF is that:

| unication is achieved by the so-called relative simplication rules (w.r.t. to the condi- tional sort hierarchy associated to the program);

| completion of that hierarchy is done by bottom-up denite normalization rules; and

| DF-resolution is SLD-like, improved with a suspension and resumption mechanism (which is quite dierent from that used in OSF; see explanations in Section 1.4).

The last section of this chapter will introduce the concurrenttellin DF; theaskoperation is implicit as DF-constraint goal solving.

1.2 DF Constraints

This section presents the DF system's syntax and its underlying (constraint) semantics.

1.2.1 DF Logic records

The logic data structures described by the DF system are based upon three types of elemen- tary relations: derivations, equations and methods. These relations lead naturally to dene the DF elementary terms:

derivation s:t 1:

equation s=t 2:

functional method s[u@w1;:::;wn!v] 3:1 set-valued method s[u@w1;:::;wn!!v] 3:2 function-typing method s[u@w1;:::;wn)t] 3:10 set-typing method s[u@w1;:::;wn))t] 3:20 boolean method s[u@w1;:::;wn] 3:3

14With sorted unication on , using (C4).

(21)

The intended meaning for these relations is:

1: sis an object of the typet (or: sis a sort derived fromt);

2: sis equal tot;

3.1: The value of the functional featureufor the object/classsisvfor (the context made of) thew1;:::;wn arguments;

3.2: One of the values taken by the set-valued featureuforsisv when taking the argumentsw1;:::;wn;

3.10 and 3:20 : The value(s) of the function-typing, respectively set-typing feature u forsin the contextw1;:::;wn should belong to the sortt;

(The typing arrow)corresponds to the functional arrow!, and similarly)) corresponds to!!.)

3.3: The featureuis true forsin the contextw1;::;wn.

The elements s;t;u;v;wi in the above relations are called references. They belong to a set R = C[V, where C = fa;b;c;:::gis a set of constants,15 and V = fX;Y;:::g is a countably innite set of variables.

We individualize among constants a special one noted >and read \top", that will be further dened as the greatest element in the sort hierarchy.

The reference s in a method term is called its root. Methods having a same root s are commonly built together into a single frame structure, namely a -term. (They will be equally referred in the sequel as DF-terms.)

By syntax convenience, the special character @ is omitted when the feature takes no arguments.

Example 1.2.1

The well-known meaning for the Prolog denotation for lists [ ];[H jT] is made explicitly typed by the following DF-terms that dene also the type for the append operation on lists:

(T1) nil:list

(T2) list[tail)list;

append@list)list].

(T1) is a derivation term and declares that nil is a list. (T2) is a -term saying that thetailof anylistis also of thelisttype, and that appending alistto anotherlistreturns always alist.

By convenience, derivation terms will be allowed to enhance the -terms' writing. For instance:

(T3) nil[append@L:list!L]:

The-term denition can be extended also recursively to allow | by means of logical conjunction | that vandt (values and types) in the methods' denition be-terms, as in

(T4) L0 :list[head!H;

tail!T[append@L:list!Z];

append@L!Y[head!H; tail!Z]]:

15 is assumed to be innite in order to ensure the existential prenex s-equivalent form for each DF-formula.

(22)

s :=t equationconstraint s:t derivation constraint

s[uqtv]t non-boolean methodconstraint (qtis either !;);!!;or))) s[ubv] boolean methodconstraint

Figure 1.4: Atomic DF-constraints

2

One should easily recognize that -terms | logic records in the OSF theory | are-terms containing only functional methods without arguments, with constant features names and whose feature values are always sorted variablesX :s.16 As -terms generalize rst-order terms, it follows that rst-order terms can be seen as a particular case of-terms.

DF-logic formulae are built on top of-terms using quantiers and logical connectives.

1.2.2 DF Logic semantics

We introduce now the DF constraint logic semantics. This is an intensional one, meaning that relations that dene predicates are assigned to symbol denotations in the domain of interpretation, not to the symbol names themselves, as used in rst-order predicate logic.

The elementary relations introduced in the precedent subsection translate naturally into DF atomic constraints which are shown in Figure 1.4. There the v symbol denotes a nite (possibly empty) sequence v1;:::;vk. These constraints are built upon :, =, and: uqtv as binary predicates (for qtone of !;);!!;))), andubvas unary predicate.

Note that we can think uqtv and ubv as second-order HiLog predicates [21], namely qt(u;v)(:) andb(u;v)(:). Translation into rst-order predicate logic with equality is imme- diate. The reader could alternatively consider:[: :::]:as a multi-arity predicate dened in the contextual rst-order predicate calculus.

Denition 1.2.1

LetC be a set of constants. A DF-algebra over C is a tuple

A=< DA;A;ICA;(IpA!q)p;q;(IpA)q)p;q;(IpA!!q)p;q;(IpA))q)p;q;(IpAbq)p;q>

where

DA is the domain of the DF-algebra A,

A is a binary relation on DA,

ICA:C!DA is the interpretation of constants,

IpA!q,IpA)q,IpA!!q,IpA))q, indexed on p2DA andq2(DA)=Sn0(DA)n are binary relations onDA, and

IpAbqare unary relations on DA.

Let A be a DF-algebra, A the reexive and transitive closure of A on DA, and : V ! DA a variable assignment in A extended as usually to constants from C. The satisability of DF-atomic constraints is dened as follows:

16These restrictions lead to the fact that -terms are dened upon asortsignature (C,:,^) which organize

Cas lower semi-lattice,^denoting here the sort intersection. As [4] shows, such a signature can always be constructed provided that`:'is a computable partial order relation on .

(23)

A;j=s :=t i (s) =(t)

A;j=s:t i (s)A(t)

A;j=s[uqtv]t i ((s);(t))2IA(u)qt(v)forqt6=b

A;j=s[ubv] i (s)2IA(u)b(v)

Satisability of complex DF formulae (obtained via logical connectives and quantier application) is dened as usually.

Boolean methods are seen as a special kind of functional methods. By convention, when writings[ubv]twe will assume thattis the special symbol>, denoting (in this context) the truth value true. So, from now on, for the sake of uniformity, whenever not otherwise said, the indexqt(read: \quasi-type") will denote!;);!!;))and b (read: \blank").

Every-term is interpreted as the logical conjunction of the elementary constraints it is built on.

Denition 1.2.2

A DF-clauseis a nite conjunction of atomic DF-constraints.

Example 1.2.2

For the-term (T2) in the precedent example we get the DF-clause list[tail)]list^list[append)list]list

while the-term (T4) goes into

L0:list^L0[head!]H^L0[tail!]T ^T[append!L]Z^L:list^ L0[append!L]Y ^Y[head!]H^Y[tail!]Z.

2

Conjunction will be seen as an idempotent and commutative operation having > as neuter element. Thus DF-clauses can be seen equivalently as sets of atomic DF-constraints.

The empty DF-clause, denoted >, is always true.

It's useful to note clearly that any DF-clausehas three main components: theequation part:=, thederivationpart:, and theframepart[]. These partitions ofare dened as one would expect:

:=fs:tjs:t2g :==fs :=tjs :=t2g [] = (:[:=):

Now we introduce a particular form for DF-clauses to characterize their satisability.

The next section will give an operational way to get such a form for every DF-clause.

Denition 1.2.3

A DF-clause is in solved form(or, simply: is solved) if 1. there are no derivation cycles s:t1;t1:t2;:::;tn:s in;

2. ifs :=t2, thensoccurs only once in ; 3. if

8

<

:

s1[u1!v1]t12 s2[u2!v2]t22, and s =: s ;u =: u ;v = : v

9

=

;

thent1=: t22,

(24)

(G) ~8(X :>^:>:X) (AS) ~8(X:Y ^Y:X !X :=Y)

(F) ~8(X[u!v]Y ^X[u!v]Z !Y :=Z) (WT) ~8(X[u!v]Y ^X[F)v]Z !Y:Z)

~

8(X[u!!v]Y ^X[u))v]Z!Y:Z)

(T) ~8(X[u)v]Y ^X0:X^v0:v^Y:Y0!X0[u)v0]Y0)

~

8(X[u))v]Y ^X0:X^v0:v^Y:Y0!X0[u))v0]Y0) (C) ~8(!9C()) for everysolved clause.

is the setf:(u :=u0&v := v0)js[u!v]t;s[u0!v0]t2g, and C() is the set of all constrained variables in.

Figure 1.5: Axiom schemes for DF-algebras

4. if

8

>

>

<

>

>

:

s1[u1!v1]t12 s2[u2)v2]t22 u1=: u22;

s1:s2 andv1: v22

9

>

>

=

>

>

;

thent1:t22, and similarly for!!in correspondence with )).

The axiom schemes all DF-algebras must satisfy are given in Figure 1.5. There the ~8 formula denotes as usually the universal closure of .

The (G) axiom expresses the fact that > is assumed to be the greatest element in the domain of interpretation. The (AS) axiom corresponds to the antisymmetry of the derivation relation. The (F) axiom states the functionality of single-valued methods. The (WT) axiom gives the well-typing correspondence between values and types for single-valued, and respectively set-valued methods. The typing axiom (T) expresses in a compact form the type inheritance, argument subtyping, and range supertyping principles from the object- orientation paradigm. (One could see the distinct cases by alternatively choosing two of the equalitiesX =X0;v=v0;andY =Y0 and pushing them into (T). For instance, ifX =X0, andY =Y0 then the (T) formula states the argument subtyping principle.)

Finally, the (C) axiom is added (as [99] pointed out) in order to avoid empty relation interpretations for DF method constraints.17

Denition 1.2.4

Let be a DF-formula, and A a DF-algebra. A valuation in A is a solutionof ifA;j=.

The denitions for DF-equivalence, DF-entailment and DF-disentailment relations be- tween DF-formulae are given as expected:

17 is constrained in if there is a constraint : , [ ], or =: in .

Referințe

DOCUMENTE SIMILARE

Lycium Chinense (Goji) is an important Chinese medicine used for energy restoring tonic, to cure a wide range of ailments from skin rashes and to treat and prevent diseases such as

should be presented each of the first three years useful when writing the thesis, if related. some

Haskell is a general purpose, purely functional programming language exhibiting many of the recent innovations in functional (as well as other) programming language re-

The second reason for focusing on Herbrand interpretations is more theoretical. For the restricted language of definite programs, it turns out that in order to determine whether

The thread releases ownership of this monitor and waits until another thread notifies threads waiting on this object's monitor to wake up either through a call to the notify method

Amir Pnueli - proposed that temporal logic should be used for checking continually operating

Keywords: algebraic specification, integration, concurrent systems, object- oriented specification, hidden algebra, CCS, temporal logics, model checking..

 In our previous example, this is the logging code that we want to apply whenever the thread enters or exits a method...  This is the term given to the point of execution