Pierre Viland
email: pierre.viland@insa-rennes.fr

Gheorghe Zaharia

Jean-Franc ¸ois Hélard

QPSK Super-Orthogonal Space-Time Trellis Codes with 3 and 4 Transmit Antennas

In this paper, we propose, for the first time, QPSK super-orthogonal space-time trellis codes (SO-STTCs) with 3 and 4 transmit antennas and with more than 4 states. In order to decrease drastically the search time of the best SO-STTCs with 3 and 4 transmit antennas, a matrix representation of codes and an adaptation of the coset partitioning are proposed. Thus, we obtain good SO-STTCs with more than 2 transmit antennas. We demonstrate by simulations that the new proposed SO-STTCs outperform the best corresponding STTCs.

I. INTRODUCTION

Tarokh et al. introduced in [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF] the concept of space-time trellis codes (STTCs) to improve the error performance or the date rate for wireless communication systems with multiple transmit and receive antennas. The first design criteria called rank and determinant criteria presented in [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF] aim to obtain STTCs achieving full diversity and some coding gain. Chen et al. proposed in [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] the trace criterion to improve the coding gain of STTCs. Based on these criteria, a method called coset partitioning has been proposed in [START_REF] Viland | Optimal generation of spacetime trellis codes via coset partitioning[END_REF] to obtain efficiently the best STTCs.

In [START_REF] Alamouti | A simple transmit diversity technique for wireless communications[END_REF], Alamouti proposed a simple code achieving full diversity and full rate for two transmit antennas. The generalization of this code leads to a new type of codes [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF] called orthogonal space-time block codes (O-STBCs). The main advantages of these codes are to employ a simple decoding scheme and to achieve a full diversity. Nevertheless, O-STBCs do not provide a coding gain. Besides, in the case of complex constellations, there are no O-STBCs with more than two transmit antennas which achieve full diversity and full rate.

Jafarkhani et al. introduced in [START_REF] Jafarkhani | Super-orthogonal space-time trellis codes[END_REF] a new class of codes called super-orthogonal space-time trellis codes (SO-STTCs) for two and four transmit antennas combining O-STBCs and STTCs. In the same time, Ionescu et al. in [START_REF] Ionescu | Improved 8and 16-state space-time codes for 4PSK with two transmit antennas[END_REF] and Siwamogsatham et al. in [START_REF] Siwamogsatham | Improved high-rate space-time codes via concatenation of expanded orthogonal block code and M-TCM[END_REF] proposed similar coding systems to improve the performance of wireless communications. The benefits of SO-STTCs are to provide full diversity compared to STTCs and to improve coding gain compared to O-STBCs. In [START_REF] Bale | Computer design of super-orthogonal space-time trellis codes[END_REF], a simple representation of SO-STTCs with only two transmit antennas based on generator matrices is given to allow a systematic search of all possible codes. For 4 transmit antennas, superquasi-orthogonal space-time trellis codes (SQO-STTCs) have been proposed in [START_REF] Jafarkhani | Super-quasi-orthogonal space-time trellis codes for four transmit antennas[END_REF]. A simplification and a generalization for 2m transmit antennas with m ∈ N * of SQO-STTCs are given in [START_REF] Wang | Space-time trellis code design based on super quasi-orthogonal block codes with minimum decoding complexity[END_REF]. These codes achieve full diversity and full rate. However, SQO-STTCs have the higher coding/decoding complexity compared to SO-STTCs and are proposed for a small number of states.

In this paper, we propose to extend the matrix representation of SO-STTCs [START_REF] Bale | Computer design of super-orthogonal space-time trellis codes[END_REF] for 3 and 4 transmit antennas. This representation allows to design efficiently SO-STTCs, thanks to the coset partitioning [START_REF] Viland | Optimal generation of spacetime trellis codes via coset partitioning[END_REF]. Thus, new SO-STTCs with 3 and 4 transmit antennas are proposed.

The paper is organized as follows. Section II describes the representations of SO-STTCs and the existing design criteria. In section III, the new method is presented. Section IV gives new QPSK SO-STTCs with 3 and 4 transmit antennas. Their performance is compared to that of the best known STTCs.

II. SYSTEM MODEL

A. QPSK SO-STTCs

We consider a QPSK 2 νB S -state SO-STTC with 2 B P parallel branches and n T transmit antennas, where ν, B S , B P , n T ∈ N * and B I = B S + B P is an even number.

The shift register of the encoder is constituted by one input block of B I bits followed by ν memory blocks of B S bits. Every T symbol-times, B I bits x t 1 • • • x t B I are fed into the encoder. The goal of the encoder is to generate n S = B I 2 signals every T symbol-times. We define a generator matrix

G = G 1 1 • • • G 1 B I |G 2 1 • • • G 2 B S | • • • |G ν+1 1 • • • G ν+1 B S (3)
where

G l i = g l 1,i • • • g l n S ,i T ∈ Z n S 4 , where i = 1, 2, • • • , B I if l = 1 and i = 1, 2, • • • , B S if l = 2, • • • , ν +1. In this paper, [•] T is the transpose of the matrix [•]
. Besides, we consider the extended state

X t = [x t 1 • • • x t B I |x t-1 1 • • • x t-1 B S |x t-ν 1 • • • x t-ν B S ] T (4)
which is a column vector containing the binary values of the shift register. Every T symbol-times, the encoder computes

Y = GX t = [y 1 • • • y n S ] T ∈ Z n S 4 mod 4. (5)
Each encoder output y m with m = 1 • • • n S is mapped onto a QPSK signal given by

s m = e j π 2 ym . (6)
C 3 (s 1 , s 2 , s 3 , θ 1 , θ 2 , θ 3 ) = s 1 e jθ 1 s * 2 e jθ 2 s * 3 e jθ 3 0 -s 2 e jθ 1 s * 1 e jθ 2 0 s * 3 -s 3 e jθ 1 0 s * 1 e jθ 3 s * 2 (1)
C 4 (s 1 , s 2 , s 3 , θ 1 , θ 2 , θ 3 ) =     s 1 e jθ 1 -s * 2 e jθ 2 s * 3 √ 2 e jθ 3 s * 3 √ 2 s 2 e jθ 1 s * 1 e jθ 2 s * 3 √ 2 e jθ 3 - s * 3 √ 2 s 3 √ 2 e jθ 1 s 3 √ 2 e jθ 2 -s 1 -s * 1 +s 2 -s * 2 √ 2 e jθ 3 s 2 +s * 2 +s 1 -s * 1 √ 2 s 3 √ 2 e jθ 1 - s 3 √ 2 e jθ 2 -s 2 -s * 2 +s 1 -s * 1 √ 2 e jθ 3 - s 1 +s * 1 +s 2 -s * 2 √ 2     (2)
During T symbol-times, a codeword of T MIMO symbols is sent over the propagation channel. We consider the codewords given by the expressions (1) proposed in [START_REF] Hochwald | A transmitter diversity scheme for wideband cdma systems based on space-time spreading[END_REF] and (2) proposed in [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF] in the case of n T = 3 and n T = 4 transmit antennas, respectively. For these codes, n S = 3 and T = 4.

The goal of multiple rotation angles θ 1 , θ 2 and θ 3 is to increase the number of possible orthogonal codewords. In order to not expand the QPSK constellation, θ τ must belong to 0, π 2 , π, 3π 2 with τ ∈ {1, 2, 3}. The k th line of the expressions ( 1) and ( 2) with k ∈ {1, 2, • • • , n T } corresponds to the signals sent by the k th transmit antenna. The t th column of the codewords ( 1) and ( 2) with t ∈ {1, 2, 3, 4} corresponds to the MIMO signal transmitted at time t by the n T transmit antennas.

The two codewords of expressions ( 1) and ( 2) achieve full rank, but the rates are limited to 3/4. In fact, there are no O-STBCs with full rank and full rate with more than 2 transmit antennas [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF]. The rotation angles θ 1 , θ 2 and θ 3 depend on the current state during the transmission of the codeword. For example, the trellis of Fig. 1 describes a QPSK 8-state SO-STTC with 8 parallel paths and 3 transmit antennas. The lines between the points are the transitions between the different states. For each transition, 8 possible codewords can be sent over the propagation channel. The signals s 1 , s 2 and s 3 depend on the inputs bits, the current state and the generator matrix with 3 lines and 9 columns.

STATES: [x t-1 1 x t-1 2 x t-1 3 ] [x t 1 x t 2 x t 3 ] time t time t +1 C 3 (s 1 ,s 2 ,s 3 , 0, 0, 0) C 3 (s 1 ,s 2 ,s 3 , 0, 0, 1) C 3 (s 1 ,s 2 ,s 3 , 0, 1, 0) C 3 (s 1 ,s 2 ,s 3 , 0, 1, 1) C 3 (s 1 ,s 2 ,s 3 , 1, 1, 1) C 3 (s 1 ,s 2 ,s 3 , 1, 1, 0) C 3 (s 1 ,s 2 ,s 3 , 1, 0, 0) C 3 (s 1 ,s 2 ,s 3 , 1, 0, 1)

B. Design criteria

The main design criteria have been established in [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] in order to decrease the bit and frame error rate. In this paper, only the case of slow Rayleigh fading channels is considered, i.e. the fading coefficients within each frame are constant.

Let us consider a frame of L MIMO signals starting at t = 0 by a n T × L matrix S = [s 0 s 1 ...s L-1 ] where s q is the q th MIMO signal. An error occurs if the decoder decides that another frame E = [e 0 e 1 ...e L-1 ] is transmitted. The main goal of the code design is to reduce the pairwise error probability (PEP) which is the probability that the decoder selects erroneously the frame E as transmitted frame while the frame S is actually transmitted. Let define the n

T × L difference matrix B = E -S B =    e 0 1 -s 0 1 . . . e L-1 1 -s L-1 1 . . . . . . . . . e 0 n T -s 0 n T . . . e L-1 n T -s L-1 n T    . (7)
The n T × n T product matrix A = BB * is introduced, where B * denotes the hermitian of B. We define r = min(rank(A)), where A is computed for all pairs of frames (E, S) with E = S. The design criteria depend on the value of the product rn R , where n R is the number of receive antennas.

If rn R ≤ 3, for a slow Rayleigh fading channel, the rank and determinant criteria have been proposed [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], [START_REF] Liao | Improved code design criteria for space-time codes over quasi-static flat fading channels[END_REF] to reduce the PEP:

• A has to be a full rank matrix for any pair (E, S).

• The coding gain is related to the inverse of η = d N (d)d -n R , where N (d) is defined as the average number of error events with determinant d = det(A). The best codes must have the minimum value of η.

If rn R ≥ 4, it is shown in [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] that for a large value of rn R which corresponds to a large number of independent SISO channels, the PEP is minimized if the sum of all the eigenvalues of the matrix A is maximized. Since A is a square matrix, the sum of all the eigenvalues is equal to the trace of the matrix A

tr(A) = n T k=1 λ k = n T k=1 L-1 q=0 e k t+q -s k t+q 2 . ( 8
)
For each pair of codewords, tr(A) is computed. The minimum trace is the minimum of all these values tr(A). The minimization of the PEP amounts to using a code which has the maximum value of the minimum trace. In [START_REF] Liao | Improved code design criteria for space-time codes over quasi-static flat fading channels[END_REF], it is also stated that to minimize the frame error rate (FER), the number of error events with minimum trace has to be minimized. This criterion is called the trace (or Euclidean distance) criterion.

24

III. CODE SEARCH In the previous publications, in order to maximize the coding gain, the generator matrix was designed via the set partitioning [START_REF] Ungerboeck | Channel coding with multilevel/phase signals[END_REF] used with the determinant criterion rather than the Euclidean distance criterion. It has been shown in [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] that the Euclidean distance governs the performance of spacetime codes when the number of independent sub-channels is great i.e. rn R ≥ 4. Thus, we propose to design new SO-STTCs based on the Euclidean distance criterion, rather than the determinant criterion.

As shown for SO-STTCs with 2 transmit antennas in [START_REF] Hartling | Design rules for extended super-orthogonal space-time trellis codes[END_REF] and for STTCs in [START_REF] Viland | Optimal generation of spacetime trellis codes via coset partitioning[END_REF], the generator matrix can be divided into blocks of columns. For example, let us consider the QPSK 8-state SO-STTCs with 8 parallel branches and 3 transmit antennas where B P = 3 and B S = 3. The generator matrix can be represented as

G = N e x t s ta te G 1 G 2 G 3 | P a r a ll e l b r a n c h e s G 4 G 5 G 6 Input bits | C u r r e n t s ta te G 7 G 8 G 9 (9)
where

G l ∈ Z 3 4 for l = 1, 2, • • • , 9.
The first block is used to compute the codewords originating from a same state. The second block is employed to compute the codewords of parallel branches of the trellis. Finally, the third block is used to obtain the codewords merging to a same state.

Based on this observation, we adapt the coset partitioning method to design the best SO-STTCs. Thus, the designed codes must fulfill the following rules :

• the used codewords are equally probable.

• the codewords of parallel transitions must be separated by the largest Euclidean distances.

• the MIMO symbols originating from or merging to a same state generate all the possible codewords. At first, the block which separates the codewords of parallel branches separated by the largest Euclidean distances must be found. The second step is the search of the blocks generating the codewords originating from and merging into the same states as a function of the previous selected block. As does the coset partitioning, the symbols Y originating from the same state must form the group Z n S 4 . This additive group is the set of all the possible symbols Y given by the expression [START_REF] Tarokh | Space-time block codes from orthogonal designs[END_REF]. In fact, since the rotation angles θ i are fixed for a given state, the number of codewords originating from the same state is equal to 4 n S . Thus, in order to separate by a non-null distance the codewords originating from the same state, the first two blocks must generate all possible codewords. Similarly, the number of codewords merging to the same state is equal to 4 n S . Thus, the last block and the block relative to the parallel branches must generate the group Z n S 4 . The method to select the columns of generator matrix to obtain a subgroup is presented in [START_REF] Viland | Optimal generation of spacetime trellis codes via coset partitioning[END_REF]. The best codes are combinations of the created blocks. ) are given in Table I. Remark : Noexhaustive search has been performed to design the SO-STTCs proposed in Table I.

IV. NEW CODES AND SIMULATION

The performance of each new code is evaluated by simulation in a slow Rayleigh fading channel and compared to the performance of the corresponding STTC in Table II proposed in [START_REF] Viland | Optimal generation of spacetime trellis codes via coset partitioning[END_REF]. For the simulation, the channel fading coefficients are independent samples of a complex Gaussian process with zero mean and variance 0.5 per dimension. These channel coefficients are assumed to be known by the decoder. Each frame consists of 264 bits. For the simulations, we consider 1 and 2 receive antennas. The decoding has two steps. For each transition between two states, the decoder picks the parallel branch with the smallest Euclidean distance. The resulting trellis has only one branch per transition. Then, the Viterbi decoder is applied to find the sent binary data.

nT 2 2ν G d 2 E min 3 8   0 2 2 3 0 0 2 3 2 3 0 2 2 3 2 1 0 2   20 16   0 2 1 2 2 0 2 1 2 0 3 2 2 1 3 2 1 2   24 4 16     1 2 2 0 3 2 3 2 3 2 1 2 2 0 3 2 1 2 1 2 2 0 2 0     32
Figs. 2 and 3 present the performance of SO-STTCs and STTCs with 3 transmit antennas presented in Tables I and II with 8 states and 16 states, respectively. Fig. 4 shows the performance of SO-STTCs and STTCs with 4 transmit antennas presented in Tables I and II. In the case of one receive antenna and for FER=10 -1 , according to the simulation results, we can notice that the new proposed SO-STTCs offer a gain of at least 2 dB over the corresponding best STTCs. In the case of 2 receive antennas and for FER=10 -1 , the SO-STTCs have more than 0.25 dB of gain compared to the corresponding best STTCs. For 4 transmit antennas, no SQO-STTC with 8 states or more has been proposed in [START_REF] Jafarkhani | Super-quasi-orthogonal space-time trellis codes for four transmit antennas[END_REF], [START_REF] Wang | Space-time trellis code design based on super quasi-orthogonal block codes with minimum decoding complexity[END_REF]

V. CONCLUSION

In the paper, the matrix representation of SO-STTCs is extended to the SO-STTCs with 3 and 4 transmit antennas and with more than 4 states. Via this representation and an adaptation of the coset partitioning, good SO-STTCs with 3 and 4 transmit antennas are designed efficiently. Due to the number of transmit antennas and the complex constellation, the new proposed codes do not achieve a full rate. However, they outperform significantly the corresponding STTCs.

Fig. 1 .

 1 Fig. 1. Trellis representation of QPSK 8-state SO-STTCs with 8 parallel paths and 3 transmit antennas

Fig. 4 .

 4 Fig. 4. Performance of the QPSK 16-state STTCs of table II and the SO-STTC with 4 transmit antennas

  Table I presents new QPSK 8-state and 16-state SO-STTCs with 3 and 4 transmit antennas. The number of parallel branches and the minimal Euclidean distance between two codewords (notified d 2

	E
	min

TABLE II STTCS

 II WITH 3 AND 4 TRANSMIT ANTENNAS

  . Fig. 2. Performance of the QPSK 8-state STTCs of table II and the QPSK 8-state SO-STTC with 3 transmit antennas Fig. 3. Performance of the QPSK 16-state STTCs of table II and the QPSK 16-state SO-STTC with 3 transmit antennas

		10 0
	FER	10 !1		0,45 dB				2,2 dB
					STTC with n R =1
					SO!STTC with n R =1
					STTC with n R =2
		10 !2	0	2 SO!STTC with n R =2 4 6	8	10	12	14	16	18
						SNR (dB)
		10 0
	FER	10 !1			0,25 dB				2 dB
					STTC with n R =1
					SO!STTC with n R =1
					STTC with n R =2
		10 !2	0	2 SO!STTC with n R =2 4 6	8	10		12	14	16
						SNR (dB)


Dana Angluin
email: dana.angluin@yale.edu

Leonor Becerra-Bonache

Effects of Meaning-Preserving Corrections on Language Learning

We present a computational model of language learning via a sequence of interactions between a teacher and a learner. Experiments learning limited sublanguages of 10 natural languages show that the learner achieves a high level of performance after a reasonable number of interactions, the teacher can produce meaning-preserving corrections of the learner's utterances, and the learner can detect them. The learner does not treat corrections specially; nonetheless in several cases, significantly fewer interactions are needed by a learner interacting with a correcting teacher than with a non-correcting teacher.

Introduction

A child learning his or her native language typically does so while interacting with other people who are using the language to communicate in shared situations. The correspondence between situations and utterances seems likely to be a very important source of information for the language learner. Once a child begins to produce his or her own utterances, other people's responses to them (or lack thereof) are another source of information about the language. When the child's utterances fall short of adult-level competence, sometimes the other person in the conversation will repeat the child's utterance in a more correct form. A number of studies have focused on the phenomenon of such corrections and questions of their frequency in child-directed speech and whether children can and do make use of them; some of these studies are discussed in the next section.

In this paper we construct a computational model with a learner and a teacher who interact in a sequence of shared situations. In each situation the teacher and learner interact as follows. First the learner uses what it has learned about the language to (attempt to) generate an utterance appropriate to the situation. The teacher then analyzes the correctness of the learner's utterance and either generates an utterance intended as a correction of the learner's utterance, or generates another utterance of its own appropriate to the situation. Finally, the learner uses information given by its own utterance, the teacher's utterance and the situation to update its knowledge of the language. At the conclusion of this interaction, a new interaction is begun with the next situation in the sequence.

Both the learner and the teacher engage in comprehension and production of utterances which are intended to be appropriate to their shared situation. This setting allows us to study several questions: whether the teacher can offer meaningful corrections to the learner, whether the learner can detect intended corrections by the teacher, and whether the presence of corrections by the teacher has an effect on language acquisition by the learner. For our model, the answer to each of these questions is yes, and while the model is in many respects artificial and simplified, we believe it sheds new light on these issues. Additional details are available [START_REF] Angluin | A Model of Semantics and Corrections in Language Learning[END_REF].

Meaning-preserving corrections

Formal models of language acquisition have mainly focused on learning from positive data, that is, utterances that are grammatically correct. But a question that remains open is: Do children receive negative data and can they make use of it?

Chomsky's poverty of stimulus argument has been used to support the idea of human innate linguistic capacity. It is claimed that there are principles of grammar that cannot be learned from positive data only, and negative evidence is not available to children. Hence, since children do not have enough evidence to induce the grammar of their native language, the additional knowledge language learners need is provided by some form of innate linguistic capacity.

E. M. Gold's negative results in the framework of formal language learning have also been used to support the innateness of language. Gold proved that superfinite classes of languages are not learnable from positive data only, which implies than none of the language classes defined by Chomsky to model natural language is learnable from positive data only [START_REF] Gold | Language identification in the limit[END_REF]. [START_REF] Brown | Derivational complexity and the order of acquisition in child speech[END_REF]) studied negative evidence understood as explicit approvals or disapprovals of a child's utterance (e.g.,"That's right" or "That's wrong.") They showed that there is no dependence between these kinds of answers and the grammaticality of children's utterances. These results were taken as showing that children do not receive negative data. But do these results really show this? It seems evident that parents rarely address their children in that way. During the first stages of language acquisition children make a lot of errors, and parents are not constantly telling them that their sentences are wrong; rather the important thing is that they can communicate with each other. However, it is worth studying whether other sources of negative evidence are provided to children. Is this the only form of negative data? Do adults correct children in a different way? Some researchers have studied other kinds of negative data based on reply-types (e.g., [START_REF] Hirsh-Pasek | Brown and Hanlon revisited: mothers' sensitivity to ungrammatical forms[END_REF], [START_REF] Demetras | Brown and Hanlon revisited: mothers' sensitivity to ungrammatical forms[END_REF] and [START_REF] Morgan | Limits on negative information in language input[END_REF].) These studies argue that parents provide negative evidence to their children by using different types of reply to grammatical versus ungrammatical sentences. Marcus analyzed such studies and concluded that there is no evidence that this kind of feedback (he called it noisy feedback) is required for language learning, or even that it exists [START_REF] Marcus | Negative evidence in language acquisition[END_REF]. He argued for the weakness, inconsistency and inherently artificial nature of this kind of feedback. Moreover, he suggested that even if such feedback exists, a child would learn which forms are erroneous only after complex statistical comparisons. Therefore, he concluded that internal mechanisms are necessary to explain how children recover from errors in language acquisition.

Since the publication of the work of Marcus, the consensus seemed to be that children do not have access to negative data. However, a study carried out by Chouinard and Clark shows that this conclusion may be wrong [START_REF] Chouinard | Adult Reformulations of Child Errors as Negative Evidence[END_REF]. First, they point out that the reply-type approach does not consider whether the reply itself also contains corrective information, and consequently, replies that are corrective are erroneously grouped with those that are not. Moreover, if we consider only replytypes, they may not help to identify the error made. Hence, Chouinard and Clark propose another view of negative evidence that builds on Clark's principle of contrast [START_REF] Clark | The principle of contrast: a constraint on language acquisition[END_REF][START_REF] Clark | The Lexicon in Acquisition[END_REF]. Parents often check up on a child's erroneous utterances, to make sure they have understood them. They do this by reformulating what they think the child intended to express. Hence, the child's utterance and the adult's reformulation have the same meaning, but different forms. Because children attend to contrasts in form, any change in form that does not mark a different meaning will signal to children that they may have produced an utterance that is not acceptable in the target language. In this way, reformulations identify the locus of any error, and hence the existence of an error. Chouinard and Clark analyze longitudinal data from five children between two and four years old, and show that adults reformulate erroneous child utterances often enough to help learning. Moreover, these results show that children not only detect differences between their own utterance and the adult reformulation, but that they make use of that information.

In this paper we explore this new view of negative data proposed by Chouinard and Clark. Corrections (in form of reformulations) have a semantic component that has not been taken into account in previous studies. Hence, we propose a new computational model of language learning that gives an account of meaning-preserving corrections, and in which we can address questions such as: What are the effects of corrections on learning syntax? Can corrections facilitate the language learning process?

The Model

We describe the components of our model, and give examples drawn from the primary domain we have used to guide the development of the model.

Situation, meanings and utterances.

A situation is composed of some objects and some of their properties and relations, which pick out some aspects of the world of joint interest to the teacher and learner. A situation is represented as a set of ground atoms over some constants (denoting objects) and predicates (giving properties of the objects and relations between them.) For example, a situation s 1 consisting of a big purple circle to the left of a big red star is represented by the following set of ground atoms: s 1 = {bi1 (t 1 ), pu1 (t 1 ), ci1 (t 1 ), le2 (t 1 , t 2 ), bi1 (t 2 ), re1 (t 2 ), st1 (t 2 )}.

Formally, we have a finite set P of predicate symbols, each of a specific arity. We also have a set of constant symbols t 1 , t 2 , . . ., which are used to represent distinct objects. A ground atom is an expression formed by applying a predicate symbol to the correct number of constant symbols as arguments.

We also have a set of of variables x 1 , x 2 , . . .. A variable atom is an expression formed by applying a predicate symbol to the correct number of variables as arguments. A meaning is a finite sequence of variable atoms. Note that the atoms do not contain constants, and the order in which they appear is significant. A meaning is supported in a situation if there exists a support witness, that is, a mapping of its variables to distinct objects in the situation such that the image under the mapping of each atom in the meaning appears in the situation. If a meaning is supported in a situation by a unique support witness then it is denoting in the situation. We assume that both the teacher and learner can determine whether a meaning is denoting in a situation.

We also have a finite alphabet W of words. An utterance is a finite sequence of words. The target language is the set of utterances the teacher may produce in some situation; in our examples, this includes utterances like the star or the star to the right of the purple circle but not star of circle small the green. We assume each utterance in the target language is assigned a unique meaning. An utterance is denoting in a situation if the meaning assigned to utterance is denoting in the situation. Intuitively, an utterance is denoting if it uniquely picks out the objects it refers to in a situation.

In our model the goal of the learner is to be able to produce every denoting utterance in any given situation. Our model is probabilistic, and what we require is that the probability of learner errors be reduced to very low levels.

3.2

The target language and meaning transducers.

We represent the linguistic competence of the teacher by a finite state transducer that both recognizes the utterances in the target language and translates each correct utterance to its meaning. Let A denote the set of all variable atoms over P . We define a meaning transducer M with input symbols W and output symbols A as follows. M has a finite set Q of states, an initial state q 0 ∈ Q, a finite set F ⊆ Q of final states, a deterministic transition function δ mapping Q×W to Q, and an output function γ mapping Q × W to A ∪ {ε}, where ε denotes the empty sequence.

The transition function δ is extended in the usual way to δ(q, u). The language of M , denoted L(M ) is the set of all utterances u ∈ W * such that δ(q 0 , u) ∈ F . For each utterance u, we define M (u) to be the meaning of u, that is, the finite sequence of non-empty outputs produced by M in processing u. Fig. 1 shows a meaning transducer M 1 for a limited sublanguage of Spanish. M 1 assigns the utterance el triangulo rojo the meaning (tr1 (x 1 ), re1 (x 1 )).

The learning task.

Initially the teacher and learner know the predicates P and are able to determine whether a meaning is denoting in a situation. The learner and teacher both also know a shared set of categories that classify a subset of the predicates into similarity groups. The categories facilitate generalization by the learner and analysis of incorrect learner utterances by the teacher. In our geometric shape domain the categories are shape, size, and color; there is no category for the positional relations. Initially the teacher also has the meaning transducer for the target language, but the learner has no language-specific knowledge.

The Interaction of Learner and Teacher

In one interaction of the learner and teacher, a new situation is generated and presented to both of them. The learner attempts to produce a denoting utterance for the situation, and the teacher analyzes the learner's utterance and decides whether to produce a correction of the learner's utterance or a new denoting utterance of its own. Finally, the learner uses the situation and the teacher's utterance to update its current grammar for the language.

In this section we describe the algorithms used by the learner and teacher to carry out the steps of this process.

Comprehension and the co-occurrence

graph.

To process the teacher's utterance, the learner records the words in the utterance and the predicates in the situation in an undirected co-occurrence graph. Each node is a word or predicate symbol and there is an edge for each pair of nodes. Each node u has an occurrence count, c(u), recording the number of utterances or situations it has occurred in. Each edge (u, v) also has an occurrence count, c(u, v), recording the number of utterance/situation pairs in which the endpoints of the edge have occurred together. From the co-occurrence graph the learner derives a directed graph with the same nodes, the implication graph, parameterized by a noise threshold θ (set at 0.95 in the experiments.) For each ordered pair of nodes u and v, the directed edge

(u, v) is in- cluded in the implication graph if c(u, v)/c(u) ≥ θ.
The learner then deletes edges from predicates to words and computes the transitively reduced implication graph.

The learner uses the transitively reduced implication graph to try to find the meaning of the teacher's utterance by translating the words of the utterance into a set of sequences of predicates, and determining if there is a unique denoting meaning corresponding to one of the predicate sequences. If so, the unique meaning is generalized into a general form by replacing each predicate by its category generalization. For example, if the learner detects the unique meaning (tr1 (x 1 ), re1 (x 1 )), it is generalized to the general form (shape1 (x 1 ), color1 (x 1 )). The learner's set of general forms is the basis for its production.

Production by the learner.

Each general form denotes the set of possible meanings obtained by substituting appropriate symbols from P for the category symbols. To produce a denoting utterance for a situation, the learner finds all the meanings generated by its general forms using predicates from the situation and tests each meaning to see if it is denoting, producing a set of possible denoting meanings. If the set is empty, the learner produces no utterance. Otherwise, it attempts to translate each denoting meaning into an utterance.

The learner selects one of these utterances with a probability depending on a number stored with the corresponding general form recording the last time a teacher utterance matched it. This ensures that repeatedly matched general forms are selected with asymptotically uniform probability, while general forms that are only matched a few times are selected with probability tending to zero.

From meaning to utterance.

The process the learner uses to produce an utterance from a denoting meaning is as follows. For a meaning that is a sequence of k atoms, there are two related sequences of positions: the atom positions 1, 2, . . . , k and the gap positions 0, 1, . . . , k. The atom positions refer to the corresponding atoms, and gap position i refers to the position to the right of atom i, (where gap position 0 is to the left of atom a 1 .) The learner generates a sequence of zero or more words for each position in left to right order: gap position 0, atom position 1, gap position 1, atom position 2, and so on, until gap position k. The resulting sequences of words are concatenated to form the final utterance.

The choice of what sequence of words to produce for each position is represented by a decision tree. For each variable atom the learner has encountered, there is a decision tree that determines what sequence of words to produce for that atom in the context of the whole meaning. For example, in a sublanguage of Spanish in which there are both masculine and feminine nouns for shapes, the atom re1 (x 1 ) has a decision tree that branches on the value of the shape predicate applied to x 1 to select either rojo or roja as appropriate. For the gap positions, there are decision trees indexed by the generalizations of all the variable atoms that have occurred; the variable atom at position i is generalized, and the corresponding decision tree is used to generate a sequence of words for gap position i. Gap position 0 does not follow any atom position and has a separate decision tree.

If there is no decision tree associated with a given atom or gap position in a meaning, the learner falls back on a "telegraphic speech" strategy. For a gap position with no decision tree, no words are produced. For an atom position whose atom has no associated decision tree, the learner searches the transitively reduced implication graph for words that approximately imply the predicate of the atom and chooses one of maximum observed frequency.

The teacher's response.

If the learner produces an utterance, the teacher analyzes it and then chooses its own utterance for the situation. The teacher may find the learner's utter-ance correct, incorrect but correctable, or incorrect and uncorrectable. If the learner's utterance is incorrect but correctable, the teacher chooses a possible correction for it. The teacher randomly decides whether or not to use the correction as its utterance according to the correction probability. If the teacher does not use the correction, then its own utterance is chosen uniformly at random from the denoting utterances for the situation.

If the learner's utterance is one of the correct denoting utterances for the situation, the teacher classifies it as correct. If the learner's utterance is not correct, the teacher "translates" the learner's utterance into a sequence of predicates by using the meaning transducer for the language. If the resulting sequence of predicates corresponds to a denoting meaning, the learner's utterance is classified as having an error in form. The correction is chosen by considering the denoting utterances with the same sequence of predicates as the learner's utterance, and choosing one that is "most similar" to the learner's utterance. For example, if the learner's utterance was el elipse pequeno and (el1 , sm1 ) corresponds to a denoting utterance for the situation, the teacher chooses la elipse pequena as the correction. If the learner's utterance is neither correct nor an error in form, the teacher uses a measure of similarity between the learner's sequence of predicates and those of denoting utterances to determine whether there is a "close enough" match. If so, the teacher classifies the learner's utterance as having an error in meaning and chooses as the possible correction a denoting utterance whose predicate sequence is "most similar" to the learner's predicate sequence. If the learner produces an utterance and none of these cases apply, then the teacher classifies the learner's utterance as uninterpretable and does not offer a correction.

When the teacher has produced an utterance, the learner analyzes it and updates its grammar of the language as reflected in the co-occurrence graph, the general forms, and the decision trees for word choice. The decision trees are updated by computing an alignment between the teacher's utterance and the learner's understanding of the teacher's meaning, which assigns a subsequence of words from the utterance to each atom or gap position in the meaning. Each subsequence of words is then added to the data for the decision tree corresponding to the position of that subsequence.

If the learner has produced an utterance and finds that the teacher's utterance has the same meaning, but is expressed differently, then the learner classifies the teacher's utterance as a correction. In the current model, the learner reports this classification, but does not use it in any way.

Empirical Results

We have implemented and tested our learning and teaching procedures in order to explore questions about the roles of corrections in language learning. We have used a simplified version of the Miniature Language Acquisition task proposed by [START_REF] Feldman | Miniature Language Acquisition: A Touchstone for Cognitive Science[END_REF]. Although this task is not as complex as those faced by children, it involves enough complexity to be compared to many realword tasks.

The questions that we address in this section are the following. (1) Can the learner accomplish the learning task to a high level of correctness and coverage from a "reasonable" number of interactions (that is, well short of the number needed to memorize every legal situation/sentence pair)? (2) What are the effects of correction or non-correction by the teacher on the learner's accomplishment of the learning tasks?

5.1 The specific learning tasks.

Each situation has two objects, each with three attributes (shape, color and size), and one binary relation between the two objects (above or to the left of.) The attribute of shape has six possible values (circle, square, triangle, star, ellipse, and hexagon), that of color has six possible values (red, orange, yellow, green, blue, and purple), and that of size three possible values (big, medium, and small.) There are 108 distinct objects and 23,328 distinct situations. Situations are generated uniformly at random.

For several natural languages we construct a limited sublanguage of utterances related to these situations. A typical utterance in English is the medium purple star below the small hexagon. There are 168 meanings referring to a single object and 112,896 meanings referring to two objects, for a total of 113,064 possible meanings. The 113,064 possible meanings are instances of 68 general forms: 4 referring to a single object and 64 referring to two objects. These languages are the 68-form languages.

We consulted at least one speaker of each language to help us construct a meaning transducer to translate appropriate phrases in the language to all 113,064 possible meanings. Each transducer was constructed to have exactly one accepted phrase for each possible meaning. We also constructed transducers for reduced sublanguages, consisting of the subset of utterances that refer to a single object (168 utterances) and those that refer to two objects, but include all three attributes of both (46,656 utterances.) Each meaning in the reduced sublanguage is an instance of one of 8 general forms, while most of the lexical and syntactic complexity of the 68-form language is preserved. We refer to these reduced sublanguages as the 8-form languages.

How many interactions are needed to learn?

The level of performance of a learner is measured using two quantities: the correctness and completeness of the learner's utterances in a given situation.

The learning procedure has a test mode in which the learner receives a situation and responds with the set of U utterances it could produce in that situation, with their corresponding production probabilities. The correctness of the learner is the sum of the production probabilities of the elements of U that are in the correct denoting set. The completeness of the learner is the fraction of all correct denoting utterances that are in U . The averages of correctness and completeness of the learner for 200 randomly generated situations are used to estimate the overall correctness and completeness of the learner.

A learner reaches a level p of performance if both correctness and completeness are at least p.

In the first set of trials the target level of performance is 0.99 and the learner and teacher engage in a sequence of interactions until the learner first reaches this level of performance. The performance of the learner is tested at intervals of 100 interactions. Fig. 2 shows the number of interactions needed to reach the 0.99 level of performance for each 68-form language with correction probabilities of 0.0 (i.e., the teacher never corrects the learner) and 1.0 (i.e., the teacher offers a correction to the learner every time it classifies the learner's utterance as an error in form or an error in meaning.) For correction probability 1.0, it also shows the number of incorrect utterances by the learner, the number of corrections offered by the teacher, and the percentage of teacher utterances that were corrections. Each entry is the median value of 10 trials except those in the last column. It is worth noting that the learner does not treat corrections specially. In the column for correction probability 0.0 there are two clear groups: Greek and Russian, each with at least 3400 interactions and the rest of the languages, each with at most 1000 interactions. The first observation is that the learner achieves correctness and completeness of 0.99 for each of these languages after being exposed to a small fraction of all possible situations and utterances. Even 3700 interactions involve at most 16.5% of all possible situations and at most 3.5% of all possible utterances by the teacher, while 1000 interactions involve fewer than 4.3% of all situations and fewer than 1% of all possible utterances.

How do corrections affect learning?

In the column for correction probability 1.0 we see the same two groups of languages. For Greek, the number of interactions falls from 3400 to 2600, a decrease of about 24%. For Russian, the number of interactions falls from 3700 to 2900, a decrease of about 21%. Corrections have a clear positive effect in these trials for Greek and Russian, but not for the rest of the languages.

Comparing the numbers of incorrect learner utterances and the number of corrections offered by the teacher, we see that the teacher finds corrections for a substantial fraction of incorrect learner utterances. The last column of Fig. 2 shows the percentage of the total number of teacher utterances that were corrections, from a low of 1.5% to a high of 12.3%.

There are several processes at work in the improvement of the learner's performance. Comprehension improves as more information accumulates about words and predicates. New correct general forms are acquired, and unmatched incorrect general forms decrease in probability. More data improves the decision tree rules for choosing phrases. Attainment of the 0.99 level of performance may be limited by the need to acquire all the correct general forms or by the need to improve the correctness of the phrase choices.

In the case of Greek and Russian, most of the trials had acquired their last general form by the time the 0.90 level of performance was reached, but for the other languages correct general forms were still being acquired between the 0.95 and the 0.99 levels of performance. Thus the acquisition of general forms was not a bottleneck for Greek and Russian, but was for the other languages. Because the teacher's corrections generally do not help with the acquisition of new general forms (the general form in a correction is often the same one the learner just used), but do tend to improve the correctness of phrase choice, we do not expect correction to reduce the number of interactions to attain the 0.99 level of performance when the bottleneck is the acquisition of general forms. This observation led us to construct reduced sublanguages with just 8 general forms to see if correction would have more of an effect when the bottleneck of acquiring general forms was removed.

The reduced sublanguages have just 8 general forms, which are acquired relatively early. Fig. 3 gives the numbers of interactions to reach the 0.99 level of performance (except for Turkish, where the level is 0.95) for the 8-form sublanguages with correction probability 0.0 and 1.0. These numbers are the means of 100 trials (except for Greek and Russian, which each had 20 trials); the performance of the learner was tested every 50 interactions.

Comparing the results for 8-form sublanguages with corresponding 68-form languages, we see that some require notably fewer interactions for 8-form sublanguages (English, Mandarin, and Swedish) while others require notably more (Greek, Hungarian and Russian.) In the case of Turkish, the learner cannot attain the 0.99 level of performance for the 8-form sublanguage at all, though it does so for the 68-form language; this is caused by limitations in learner comprehension as well as the differing frequencies of forms. Thus, the 8-form languages are neither uniformly easier nor uniformly harder than their 68-form counterparts. Arguably, the restrictions that produce the 8-form languages make them "more artificial" than the 68-form languages; however, the artificiality helps us understand more about the possible roles of correction in language learning.

Even though in the case of the 8-form languages there are only 8 correct general forms to acquire, the distribution on utterances with one object versus utterances with two objects is quite different from the case of the 68-form languages. For a situation with two objects of different shapes, there are 40 denoting utterances in the case of 68-form languages, of which 8 refer to one object and 32 refer to two objects. In the case of the 8-form languagues, there are 10 denoting utterances, of which 8 refer to one object and 2 refer to two objects. Thus, in situations of this kind (which are 5/6 of the total), utterances referring to two objects are 4 times more likely in the case of 68-form languages than in the case of 8form languages. This means that if the learner needs to see utterances involving two objects in order to master certain aspects of syntax (for example, cases of articles, adjectives and nouns), the waiting time is noticeably longer in the case of 8-form languages.

This longer waiting time emphasizes the effects of correction, because the initial phase of learning is a smaller fraction of the whole. In the third column of Fig. 3 we show the percentage reduction in the number of interactions to reach the 0.99 level of performance (except: 0.95 for Turkish) from correction probability 0.0 to correction probability 1.0 for the 8-form languages. For each language, corrections produce a reduction, ranging from a low of 11.7% for Swedish to a high of 38.1% for Greek. This confirms our hypothesis that corrections can substantially help the learner when the problem of acquiring all the general forms is not the bottleneck.

Discussion and Future Work

We show that a simple model of a teacher can offer meaning-preserving corrections to the learner and such corrections can significantly reduce the number of interactions for the learner to reach a high level of performance. This improvement does not depend on the learner's ability to detect corrections: the effect depends on the change in the distribution of teacher utterances in the correcting versus noncorrecting conditions. This suggests re-visiting discussions in linguistics that assume that the learner must identify teacher corrections in order for them to have an influence on the learning process.

Our model of language is very simplified, and would have to be modified to deal with issues such as multi-word phrases bearing meaning, morphological relations between words, phonological rules for word choice, words with more than one meaning and meanings that can be expressed in more than one way, languages with freer word-orders and meaning components expressed by non-contiguous sequences of words. Other desirable directions to explore include more sophisticated use of cooccurrence information, more powerful methods of learning the grammars of meanings, feedback to allow the learning of production to improve comprehension, better methods of alignment between utterances and meanings, methods to allow the learner's semantic categories to evolve in response to language learning, and methods allowing the learner to make use of its ability to detect corrections.

Figure 1 :

 1 Figure 1: Meaning transducer M 1 .

Figure 2 :

 2 Figure 2: Interactions, incorrect learner utterances and corrections by the teacher to reach the 0.99 level of performance for 68-form languages.

Figure 3 :

 3 Figure 3: Interactions to reach the 0.99 level of performance for 8-form languages. (For Turkish: the 0.95 level.)

*

Research supported by the National Science Foundation, Grant CCF-0916389.


Dana Angluin
email: dana.angluin@yale.edu

Leonor Becerra-Bonache

An Overview of How Semantics and Corrections Can Help Language Learning

Keywords: semantics, corrections, interactive learning

We present an overview of the results obtained with a computational model that takes into account semantics and corrections for language learning. This model is constructed with a learner and a teacher who interact in a sequence of shared situations. The model was tested with limited sublanguages of 10 natural languages in a common domain of situations.

I. INTRODUCTION

Can children learn language from the radio? As psychological and linguistic studies have shown [START_REF] Ervin-Tripp | Some strategies for the first two years[END_REF], interaction with human speakers is crucial for language development. The context in which the utterances are generated also plays an important role in the early stages of children's language acquisition; thanks to the shared context, adult and child can communicate with each other although their grammars are different. Moreover, as some linguistic studies suggest [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF], parents often reformulate children's erroneous utterances, to make sure they have understood them. These corrections (in the form of reformulations) are based on the meaning that the child intend to express.

In this paper we present the main features of a computational model that takes into account all these ideas, and we discuss the experimental results obtained with such model. In this model, a teacher and a learner interact in a sequence of shared situations. Both of them engage in comprehension and production of utterances which are intended to be appropriate to their shared situation. Moreover, the teacher is able to correct the learner's utterance, and the learner can detect the intended corrections by the teacher. This setting has allowed us to study the effects of semantics and corrections in language learning.

II. RELATED WORK

Most work on computational models of language learning has focused only on language comprehension, and on just a single phenomenon (e.g., single word learning or syntactic category acquisition.) Some of the more empirical works that are focused on comprehension and take into account semantics are those of Siskind [START_REF] Siskind | A computational study of cross-situational techniques for learning word-to-meaning mappings[END_REF], Marcken [START_REF] De Marcken | Unsupervised language acquisition[END_REF], Regier [START_REF] Regier | The Human Semantic Potential: Spatial Language and Constrained Connectionism[END_REF] and Bailey [START_REF] Bailey | A computational model of the role of motor control in the acquisition of action verbs[END_REF]. The systems developed by Siskind [START_REF] Siskind | Lexical acquisition in the presence of noise and homonymy[END_REF] and Marcken [START_REF] De Marcken | Unsupervised language acquisition[END_REF] learn word semantics in simulation; it is assumed that the learner already has concepts for each of the words to be learned, and word learning becomes a problem of matching words to concepts. The representation used by these systems is based on compositional semantics. Moreover, Siskind investigated the use of crosssituational analysis to model lexical acquisition. The systems introduced by Regier [START_REF] Regier | The Human Semantic Potential: Spatial Language and Constrained Connectionism[END_REF] and Bailey [START_REF] Bailey | A computational model of the role of motor control in the acquisition of action verbs[END_REF] use more realistic simulated data; they focus on learning particular words in isolation, rather than in a linguistic context.

One of the most closely related research efforts is that of Kevin Gold and his collaborators [START_REF] Gold | Using sentence context and implicit contrast to learn sensor-grounded meanings for relational and deictic words: The TWIG system[END_REF], [START_REF] Gold | Robotic vocabulary building using extension inference and implicit contrast[END_REF]. They introduced a word learning system called TWIG (Transportable Word Intension Generator) that allows a robot to learn compositional meanings for new words. We use a different representation of word meaning, that is not based on Frege's principle of compositionality; this allows us to assign a correct meaning to a sentence even if the sentence is not grammatically correct. Unlike in TWIG, our learner has no initial knowledge of words or grammar, there is no restriction on the number of new words in a sentence given to the learner, and our learner is allowed to interact with the teacher and possibly receive corrections.

Our model is also inspired by Chouinard and Clark's results [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF]. They analyze longitudinal data from five children between two and four years old, and show that adults reformulate erroneous child utterances often enough to help learning. Such corrections (in form of reformulations) preserve the intended meaning of the child. Moreover, they show that children not only can detect the corrections, but also make use of them. Our model gives an account of meaning-preserving corrections.

III. OUR MODEL

The domain we have used to guide the development of our model is a simplification of the Miniature Language Acquisition task, formalized by Feldman et al. [START_REF] Feldman | Miniature language acquisition: A touchstone for cognitive science[END_REF]. The task consists of learning a subset of a natural language from sentence-picture pairs that involve geometric shapes with different properties (color, size and position.)

In our model, the input given to the learner consists of a situation and an utterance that denotes something in that situation: i) A situation is a collection of objects, properties and relations. These are not intended to be an exhaustive description of the state of the world, but to pick out some aspects of it that are of joint interest to the teacher and the learner. We assume that these objects, properties and relations are recognizable to both the learner and teacher from the outset. A situation is represented as a set of ground atoms over some constants (denoting objects) and predicates (giving properties of the objects and relations between them.) For example, a situation s 1 consisting of a big red triangle to the left of a big yellow circle is represented by the following set of ground atoms:

s 1 = {bi1 (t 1 ), re1 (t 1 ), tr1 (t 1 ), le2 (t 1 , t 2 ), bi1 (t 2 ), ye1 (t 2 ), ci1 (t 2 )}.
ii) An utterance is a finite sequence of words over a finite alphabet. For example, the star or the star to the right of the purple circle or star of circle small the green. The target language is the set of utterances the teacher may produce in some situation; in our example, this includes utterances like the star or the star to the right of the purple circle but not star of circle small the green. We assume each utterance in the target language is assigned a unique meaning. The goal of the learner is to learn a grammar for the language that will enable it to produce every appropriate utterance in any given situation. The learner gathers information about the language by engaging in a sequence of interactions with the teacher, where each interaction is related to a new situation. Our model is probabilistic, and what we require is that the probability of learner errors be reduced to very low levels.

The linguistic competence of the teacher is represented by a finite state transducer. This transducer is used by the teacher both to produce utterances appropriate to the given situation, and to analyze the utterances of the learner.

The learner and teacher share the same description of the situation. They also know a shared set of categories that classify a subset of the predicates into similarity groups. For example, in our domain we have three different categories: one for shape predicates, one for color predicates, and one for size predicates. No category contains the positional relations. The categories facilitate generalization by the learner, and are used by the teacher in analyzing incorrect utterances of the learner.

Figure 1 summarizes one interaction between learner and teacher. More details about our model and a description of the algorithms used by the learner and teacher to carry out the steps of this process can be found in [START_REF] Angluin | A model of semantics and corrections in language learning[END_REF].

IV. TESTING ON NATURAL LANGUAGE SAMPLES

We have implemented and tested our model in the example domain of geometric shapes with limited sublanguages of ten different natural languages: English, German, Greek, Hebrew, Hungarian, Mandarin, Russian, Spanish, Swedish, 1) A new situation is generated and presented to the learner and teacher.

2) The learner uses its current grammar to attempt to produce an utterance.

3) The teacher analyzes the learner's utterance (if any) in the context of the situation. 4) If the learner's utterance has an error in form or an error in meaning, the teacher decides randomly (using the correction probability) whether to correct the learner. 5) The teacher produces an utterance appropriate to the situation. 6) The learner analyzes the teacher's utterance and updates its current grammar. and Turkish. These experiments have allowed us to explore questions about the role of semantics and corrections in language learning. In our experiments, each situation has two objects, each with three attributes (shape, color and size), and one binary relation between the two objects (above or to the left of.) The attribute of shape has six possible values (circle, square, triangle, star, ellipse, and hexagon), that of color has six possible values (red, orange, yellow, green, blue, and purple), and that of size three possible values (big, medium, and small.) There are 108 distinct objects and 23,328 distinct situations. Situations are generated uniformly at random.

The utterances in a situation are phrases intended to denote one of the objects, for example, the circle, the orange star, or the small purple hexagon below the medium green square. There are 168 meanings referring to a single object and 112,896 meanings referring to two objects, for a total of 113,064 possible meanings.

In each of these languages, the 113,064 possible meanings are instances of 68 general forms: 4 referring to a single object and 64 referring to two objects. For English, examples of general forms are (shape1 (x 1 )), (color1 (x 1 ), shape1 (x 1 )) and (size1 (x 1 ), shape1 (x 1 ), le2 (x 2 , x 1 ), shape1 (x 2 )). We refer to these languages as the 68-form languages.

For each language we consider, we consulted at least one speaker of the language to help us construct a meaning transducer to translate appropriate phrases in the language to all 113,064 possible meanings. Each transducer was constructed to have exactly one accepted phrase for each possible meaning.

To help understand the effect of different aspects of the learning problem, we also considered reduced sublanguages, consisting of the utterances that refer to a single object (168 utterances) and those that refer to two objects, but include all three attributes of both (46,656 utterances.) Thus, for English the utterances in the reduced sublanguage include the star, the blue triangle and the medium purple ellipse to the left of the medium red square but not the circle below the yellow hexagon. Each meaning in the reduced sublanguage is an instance of one of 8 general forms, but most of the lexical and syntactic complexity of the language is preserved. We refer to these reduced sublanguages as the 8-form languages.

The level of performance of a learner attempting to learn a given language L is measured using two quantities: the correctness and completeness of the learner's utterances in a given situation. i) Correctness: sum of the probabilities of the learner's utterances that are in the correct denoting set. ii) Completeness: fraction of the correct denoting utterances that appear in the set of learner utterances. The averages of correctness and completeness of the learner in 200 randomly generated situations is used to estimate the overall correctness and completeness of the learner. We say that a learner reaches a level p of performance if both correctness and completeness are at least p.

We conducted two different sets of experiments. In all of them, we set a target level of performance of p = 0.99. The first set of experiments tries to answer the following question: What are the effects of a correcting and a noncorrecting teacher for the learner to accomplish the learning task? The second set of experiments tries to see whether the presence of semantics facilitate the learning process. We review the results obtained in the next sections. More details can be found in [START_REF] Angluin | A model of semantics and corrections in language learning[END_REF] and [START_REF]Effects of meaning-preserving corrections on language learning[END_REF].

A. What are the effects of corrections?

In order to see the effects of corrections in language learning, we have compared the number of interactions needed by the learner to accomplish the learning task to a high level of performance in two different situations: i) The teacher does not correct the errors produced by the learner; ii) The teacher corrects the incorrect learner utterances.

First of all, we tested the number of interactions needed by the learner to reach the 0.99 level of performance, for each 68-form language, with correction probabilities of 0.0 and 1.0.

We obtained the following results. When the teacher does not correct the learner (i.e., correction probability is 0.0), we could distinguish two different groups: Greek and Russian, each with at least 3400 interactions and the rest of the languages, each with at most 1000 interactions. The first observation is that the learner achieves correctness and completeness of 0.99 for each of these languages after being exposed to a small fraction of all possible situations and utterances. Even the maximum number of interactions needed for Russian (concretely, 3700 interactions) involve at most 16.5% of all possible situations and at most 3.5% of all possible utterances by the teacher.

When the teacher corrects the learner (i.e., correction probability is 1.0), we see the same two groups of languages: Greek and Russian versus the rest of the languages tested. For Greek and Russian, there is a clear decrease in the number of interactions required to achieve level of performance 0.99; for Greek, a decrease of about 24%, and for Russian a decrease of about 21%. However, the languages in the other group show no clear effect of corrections in these trials. The question is: Why?

It is important to note that in these trials the learner processes a teacher utterance in exactly the same way regardless of whether the learner classifies it as a correction. That is, the learner does not do anything special for perceived corrections. Thus, the improvements in performance for Greek and Russian depend entirely on the difference in behavior of the teacher. In particular, the non-correcting teacher and the correcting teacher produce different distributions of utterances, and this change in the learners environment changes the performance of the learner. This suggests that studies of correction in natural languages should consider the possibility that corrections may affect the learning process even when the learner cannot detect corrections (or does not attempt to.)

If we further examine the results, we can see that for the group consisting of Greek and Russian, the learner had acquired its last general form in attaining performance level 0.90, and then, the attainment of the 0.99 level of performance is limited by the need to improve the correctness of the phrase choices. However, for the group consisting of the other languages, the bottleneck is the acquisition of all 68 correct general forms. The teacher's corrections tend not to help with the acquisition of new general forms.

In order to see if correction would have an effect when the bottleneck of acquiring general forms was removed, we conducted the same experiments with the 8-form languages. The results obtained with these reduced sublanguages are the following. We can see an improvement of over 30% in the number of interactions to reach performance level 0.99 in going from correction probability 0.0 to correction probability 1.0. The intermediate correction probabilities give intermediate values. The corrected learners seem to be slightly slower to reach the 0.60 level of performance. The data on numbers of general forms for these runs show that learners had overwhelmingly acquired their last general form by the time they reached the 0.90 level of performance, where the superior performance of the corrected learners becomes very evident.

These experiments confirm our hypothesis that corrections can substantially help the learner when the problem of acquiring all the general forms is not the bottleneck.

B. What are the effects of semantics?

Our second set of experiments was focused on investigating whether the presence of semantics facilitates the learning process. Unlike the previous experiments, we only consider a non-correcting teacher. Therefore, the teacher simply produces a randomly drawn denoting utterance for the situation, independent of the learner's production. Note that because we consider only the case of a non-correcting teacher, only positive data is provided to our learner.

In order to answer this question, we compared the performance of our system to the ALERGIA algorithm. ALERGIA is one of the most successful approaches to the problem of learning PDFA (probabilistic deterministic finite automata) from a positive sample, and it has become the basis of comparisons for algorithms that have been subsequently proposed. A full description of this algorithm can be found in [START_REF] Carrasco | Learning stochastic regular grammars by means of a state merging method[END_REF].

We used the ALERGIA algorithm to learn limited sublanguages of Spanish and English, specifically, the 68form sublanguages of Spanish and English. We compared the number of examples needed to reach a high level of performance by the ALERGIA algorithm with the number of interactions needed by our system. The utterances given to ALERGIA were generated in the same way as the utterances of a non-correcting teacher, i.e., we generated a sequence of n pairs of a random situation and a randomly chosen denoting utterance, and extracted the sequence of utterances to form the input to ALERGIA.

We ran the ALERGIA algorithm to estimate the minimum number of utterances required to acquire these two languages, and the results obtained were the following. In the case of Spanish, instead of 1000 situation/utterance pairs, ALERGIA needs 6000 utterances. For English, the difference is still larger; instead of 700 situation/utterance pairs, ALERGIA needs 15000 utterances. These results show that the number of examples is drastically reduced when semantics is taken into account, suggesting that the presence of semantics signicantly facilitates the learning process, even when the teacher is non-correcting. Our results in the previous section suggest that if in addition to semantics, corrections are taken into account (e.g., the teacher's correction probability is set to 1.0), the improvement for some learning tasks can be even greater.

V. CONCLUSION AND FUTURE WORK

Our model and results show that: i) Semantics can significantly reduce the number of examples needed to acquire limited sublanguages of natural language; ii) A teacher can offer corrections to the learner, the learner can detect them, and that such corrections can significantly reduce the number of interactions needed by the learner to accomplish the learning task (to a high level of performance), even if the learner does not treat corrections specially.

A future direction of research is to improve our current model of language; it is very simplified, and there are many issues it does not deal with properly (e.g., morphological relations between words, phonological rules for word choice, polysemous words, etc.) It would also be interesting to see if a learner can use the ability to detect corrections to accelerate the learning process.

Figure 1 .

 1 Figure 1. Summary of one interaction in the learning cycle.

ACKNOWLEDGMENT

The work of the first author was supported by the National Science Foundation under Grant CCF-0916389. The second author thanks the support given by the Network of Excellence PASCAL 2.


Bruno Paiva Lima Da Silva

Jean Francois Baget #

Madalina Croitoru
email: croitoru@lirmm.fr

Ontological Conjunctive Query Answering over Semi-Structured KBs

In the context of ontological conjunctive query answering different paradigms for representation and their subsequent manipulation by dedicated reasoning systems have been successfully studied in the past. However, new challenges, problems and issues have appeared in the context of knowledge representation in AI that involve the logical manipulation of increasingly large information sets (see for example the Semantic Web). In this paper we explain these challenges by the means of an example and try to further identify the difficulties ahead of our goal.

I. INTRODUCTION

The purpose of this paper is to present our current research question: "How to store large knowledge bases in order to be able to scale up ontological conjunctive query answering?"

Let us further describe the context of this research question. Knowledge Representation and Reasoning (KRR) studies computational models for building explicit representations of knowledge processed by reasoning engines. Systems based upon such computational models are called knowledge-based systems (KBS). Their fundamental components are a knowledge base (KB) containing different kinds of knowledge and a reasoning engine which performs the inferences. First Order Logic (FOL) is the reference logic in KRR and most formalisms in this area can be translated into fragments (i.e., particular subsets) of FOL. A large part of research in this domain can be seen as studying trade-off between the expressivity of languages and the complexity of (sound and complete) reasoning in these languages. The fundamental problem in KRR formal languages is deduction (or consequence, entailment) checking: "can a given piece of knowledge be deduced from other pieces of knowledge (for instance the KB)?" Another important problem is consistency checking: "is a set of knowledge pieces (for instance the KB itself) consistent, i.e., is it sure that nothing absurd can be deduced from it?" Here we are interested in the ontological conjunctive query answering problem. In its decision form, it asks if the KB contains an answer to the query, and is equivalent to deduction in the special case of boolean queries (i.e., queries with a yes/no answer). Queries must be at least as expressive as conjunctive queries in databases (eg. a conjunction of positive atoms in logical form); and the knowledge base is split into a factual component (that can be seen as a database or as a conjunction of positive atoms) and an ontological component, that is often expressed by formulas of a specific subset of FOL.

Nevertheless, in this context, different paradigms for representation and their subsequent manipulation by dedicated reasoning systems have been successfully studied in the past. However, new challenges, problems and issues have appeared in the context of knowledge representation in AI that involve the logical manipulation of increasingly large knowledge sets (see for example the Semantic Web). Improvements in storage capacity and performance also affect the nature of KRR systems. Their focus has now shifted towards representational power and execution performance. Therefore, research into KRR must move towards investigating structures for representation optimally manipulated to perform large scale reasoning, given very new and different constraints to those existing only few years ago. While a plethora of systems dedicated to non relational structures (such as NoSQL1 , which means "Not Only SQL") for information storing and querying have lately received much attention, we are interested in the representation and reasoning with knowledge. Our querying mechanisms are more expressive than typical queries done in the above mentioned systems. On the other hand, a discussion solely on expressivity / reasoning and how it relates to other NoSQL systems might turn abstract very fast, with the storage issues hidden away. This is why we chose to present this paper solely by the means of a running example where we identify informally the problems we are facing.

Our research interests2 follow the computational and logicoriented approach of KRR: the different kinds of knowledge have a logical semantics and the reasoning corresponds to inferences in this logic, at least for the kernels of studied languages. The fundamental decision problem we want to address is (boolean) ontological conjunctive query answering, which can be expressed as a deduction problem: "is a (boolean) conjunctive query deducible from a KB?" The afore mentioned KB queries are supposed to be at least as expressive as the basic queries in databases, i.e., conjunctive queries, which can be seen as existentially closed conjunctions of atoms.

A knowledge base is composed of a set of facts, and a set of rules (ontological knowledge). In this paper rules will be expressed using ∀∃-rules, which have the same logical form as TGDs in databases, and which forms the core of Datalog ± family of languages. ∀∃-rules form an abstraction particularly well-suited to the representation of ontological knowledge since they generalize several specific knowledge representation languages adapted to query answering: RDFS [START_REF] Hayes | RDF Semantics, ser. W3C Recommendation[END_REF] (the basic semantic web language), constraints in F-logic-Lite [START_REF] Calì | Containment of conjunctive object meta-queries[END_REF], [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF] (a powerful subset of F-logic, a formalism for object-oriented deductive databases), as well as the core of new families of description logics tailored for conjunctive query answering [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF], [START_REF] Lutz | Conjunctive query answering in the description logic el using a relational database system[END_REF], [START_REF] Baget | DL-SR: a lite DL with expressive rules: Preliminary results[END_REF], [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF].

II. EXAMPLE

In this paper, we deliberately chose to present our work informally, by the means of an example. Through this example, we highlight some issues and the limits of current methods used in KRR. For the theoretical foundation of the formalisms detailed below please see: [START_REF] Abiteboul | Foundations of Databases[END_REF] for relational databases and Datalog evaluation techniques, [START_REF] Chein | Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs[END_REF] for our graph based representation and [START_REF] Calì | Datalog+/-: A family of logical knowledge representation and query languages for new applications[END_REF] for Datalog ± , that corresponds to the graph based rules as discussed in [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF].

Let us consider a knowledge base representing the companies people work in and their practised sport. The knowledge base is composed of the following facts:

• (1) "There is a person, named Bob, working for some Organisation (u). This person plays for some football team (p) which has "RueAda, M ontpellier" as address.

There is another person, named Tom, working for another Organisation (v), which is part of u, and who plays for some rugby team (q), which also has "RueAda, M ontpellier" as address."

The knowledge base is also composed of the following rules:

• (2) "If x works for y, and y is part of z, then x also works for z" • (3) "If x and z work for y, then x and z are co-workers" • (4) "If x and z share the same address y, then there is a club t, which contains x and z and has y as address." • (5) "If x plays in y, which is contained in z, then x is a member of z." • (6) "If x and z are members of y, then they are in the same club."

Being given the above mentioned facts and rules we want to be able to answer the two following queries:

• (7) "Is there a person which works in an organisation and plays in a football team?" • (8) "Are there two persons who are co-workers and share the same sports club?"

Please note that query ( 7) can be answered directly on the facts in (1) i.e. without the application of any of the rules ( 2) -( 6). However, query (8) can only be answered by applying the rules ( 2) -( 6). Also, please note that rules (2), ( 3), ( 5) and ( 6) intuitively only add relations between existing entities, while rule (4) generates a new entity (club) that is added to the knowledge base 3 .

The next section (Section II-A) shows the logical translation of the knowledge base. Then in Section II-B we show the equivalent representation using relational databases. Sections II-C and II-D explain how query answering takes place (without and with rule application). In Section III we then illustrate how the knowledge base can be expressed using a graph based formalism and how query answering (without rules) is equivalent to a labelled graph homomorphism.

A. First Order Logic translation

In order to lay the logical foundations for the different models used later in this paper please find below the First Order Logic translation of the facts in the knowledge base mentioned in Section II.

• (1) ∃x, y, u, v, p, q ( is-a(x, "P erson") ∧ name(x, "Bob") ∧ works-f or(x, u) ∧ is-a(u, "Organisation") ∧ is-a(y, "P erson ′′ ) ∧ name(y, "T om") ∧ works-f or(y, v) ∧ is-a(v, "Organisation") ∧ part-of (v, u) ∧ is-a(p, "F ootballT eam") ∧ plays-in(x, p)
∧ is-a(q, "RugbyT eam") ∧ plays-in(y, q) ∧ address(p, "RueAda, M ontpellier") ∧ address(q, "RueAda, M ontpellier") )

The rule set containing ∀∃-rules:

• (2) ∀x, y, z works-f or(x, y) ∧ part-of (y, z) → works- f or(x, z) • (3) ∀x, y, z works-f or(x, y) ∧ works-f or(z, y) → co- worker(x, z) • (4) ∀x, y, z ∧ address(x, y) ∧ address(z, y) → ∃t is-a(t, "Club") ∧ contains(t, x) ∧ contains(t, z) ∧ address(t, y) • (5) ∀x, y, z plays-in(x, y) ∧ contains(z, y) → member(x, z) • (6) ∀x, y, z ∧ member(x, y) ∧ member(z, y) → same-club(x, z)
And queries:

• (7) ∃x, y, z works-f or(x, y) ∧ is- a(y, "Organisation") ∧ plays-in(x, z) ∧ is- a(z, "F ootballT eam")
• (8) ∃x, y co-worker(x, y) ∧ same-club(y, x)

B. Equivalence with a Relational Database

This section shows an encoding of the example formulas using a relational database containing the facts in the knowledge base introduced in Section II. For every n-ary predicate P in our facts, we create a new table P with n columns. Variables in the knowledge base are then frozen and replaced by fresh constants, since there are no variables in a relational database. After that, for every atom in the facts, a row is added to the table corresponding to the name of the predicate.

Figures 1 to 4 represent the relational database for facts [START_REF] Hayes | RDF Semantics, ser. W3C Recommendation[END_REF]. 3. part-of and plays-in relations address 1 2 < p > "RueAda, M ontpellier" < q > "RueAda, M ontpellier"

name 1 2 < x > "Bob" < y > "T om" works-for 1 2 < x > < u > < y > < v > Fig. 1. name and works-f or relations is-a 1 2 < x > "P erson" < u > "Organisation" < y > "P erson" < v > "Organisation" < p > "F ootballT eam" < q > "RugbyT eam" Fig. 2. is-a relation part-of 1 2 < v > < u > plays-in 1 2 < x > < p > < y > < q > Fig.

C. Rule Application

Rule application allows to enrich the KB with new facts deduced from existing ones. In Datalog ± , a rule is an expression of form ∀x 1 , ..., x k C → C ′ where x 1 to x k are the variables present in the conjunction of atoms C and C ′ . C is called the head of the rule, while C ′ is the tail.

In Datalog ± , the chase algorithm consists in enriching the the database (directly, or just a local copy) with inferred information. It queries the head of the rule in the database using a SELECT -F ROM -W HERE call, and if there is a positive answer to the query, a specification of the tail of the rule is then inserted to the base with an IN SERT call. In the case of our example, rule (2) will fire since (1) <v> is part-of <u> and (2) <y> works-for <v>. Therefore, the new row <y>,<u> will be added to the table works-for. Similarly, the rules (3), ( 5) and ( 6) will add new rows in corresponding tables. Please note though that the expressivity of the rules we are interested in is that of ∀∃-rules as explained in the introduction. This means that we want to be able to add not only new rows but also new relations between pieces of information, which in this case would correspond to adding new tables or changing the relational schema of the database. This cannot be dealt with by Datalog itself. We point out that TGDs can add rows that use newly generated constants, which why the chase may not halt (the deduction problem is indeed undecidable). However, decidable subclasses of the problem have been studied (eg. [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF], [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF], [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]).

D. Querying a Knowledge Base

The SQL translation of the queries in the example is as follows: No rules need to be applied to answer the first query, however, 4 tables (the same table twice), need to be joined. More importantly, the second query can only be answered after the addition of new pieces of knowledge to the base. Consistency becomes a problem in this case since it is initially maintained by the fact that the data stored is supposed to be organized into normalized tables, in which independent sets of data are related by a key and in which redundancy is avoided. While this model seems appopriate when dealing with sets of structured data, the semi-structured nature of our data makes the relational model difficult to fit into. We can distinguish two different methods for rule application over a KB: forwardchaining and backwards-chaining.

• (7) SELECT * F ROM works-f or,plays-in,is-a isa1,is-a isa2 W
The forward-chaining method fires all rules looking for new pieces of information to be added to the base until an answer to the query is found. The large amount of joins when performing a request in the KB becomes quickly very costly, and things get even more difficult when new information has to be introduced to the base, since indexes and the database schema have to be updated several times. On the other hand, the backwardschaining method does not add any new information to the KB, but has a major drawback as it can possibly create a huge number of queries.

Scaling is also one of the real problems of those approaches since joins usually create new temporary tables in main memory. One should not forget our initial intentions to answer conjunctive queries when the knowledge base itself cannot be held any more in main memory.

So far we have presented the relational approach and its drawbacks when scaling up. These drawbacks led us to look into graph appropriate storage for solving our problem. Let us further detail the graph model and highlight our specific needs for the conjunctive query answering problem.

III. GRAPH-BASED REPRESENTATION

In this section we represent the knowledge base using the graph based formalism detailed in [START_REF] Chein | Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs[END_REF]. In this representation, constants and variables are vertices in our (hyper)graph, while (hyper)edges between those vertices represent the atoms in our KB 4 .

x "Bob" name name(x, "Bob") Fig. 5. A fact in the knowledge base and its graph representation on the right.

Figure 5 shows the transformation of the facts of the KB in a graph, and Figure 6 represents the graph containing the facts in the KB for the given example.

"P erson"

x y u v "Organisation" "Bob" "T om" p q "F ootball T eam" "Rugby T eam"

"RueAda -M ontpellier" is-a is-a name name is-a is-a works-f or works-f or is-a is-a plays-in plays-in part-of

address address

Fig. 6. Graph containing the facts (1) from Section II.

A. Querying

In a graph-based KB, queries are represented as graphs. Figures 7 and8 show the graphs of both queries from Section II.

B. Homomorphism

Queries in a graph-based KB are answered by computing a labelled graph homomorphism from the graph representing the query Q to F , the graph of facts. The fundamental theorem says that a logical formula Q can be deduced from another formula F iff there is a labelled graph homomorphism from the graph representing Q to the graph representing F .

Basically, a labelled graph homomorphism is a mapping, say π, from the vertices of the graph Q (the query), to those of the graph F (the facts) that preserves both the constants labelling the nodes and the hyperedges and their type. More formally:

• if x is a vertex of Q labelled by a constant c, then the label of π(x) is also c; • if there is a hyperedge labelled p between vertices (x 1 , ..., x q ) in Q, then there must also be a hyperedge labelled p between vertices (π(x 1 ), ..., π(x q )) in F . Since the labelled graph homomorphism problem is NP-Complete, a backtracking algorithm is used to enumerate all the possible matchings that answer the query.

Let us now detail the execution of a backtracking algorithm for homomorphism finding. We consider a recursive algorithm that, at every loop, extends the current matching algorithm. We name the algorithm Extend(). The algorithm takes as parameters the set of already matched nodes couples, and the graphs representing query and facts.

Extend(MatchedNodes,Query,Facts) returns true if the number of couples in the matched nodes set is equal to the number of nodes in the query graph. If not, it selects a node n that has not yet been matched, and returns a list of relevant possible node matchings i of the node n according to MatchedNodes, Query and Facts. Then, for each of the possible matchings, the algorithm is recursively called with the couple (n,i) added to the matched nodes set.

Let us consider the first query that can be answered without rule application (detailed in the next section). To find a homomorphism from this query to the facts graph, the algorithm starts matching all the constant vertices from the query graph to the facts one. As we have seen on Figure 7, the constants in the query, "Organisation" and "FootballTeam", are also present in the facts, and are added to the matched nodes set. After that, the algorithm will try to match the remaining variable nodes of the query graph. Node x has two outgoing relations to another variable: works-f or and plays-in. Possible matchings for x then are nodes x and y from the graph of facts. When node x in query is matched with y in facts, y will then be then paired to v since it is an Organisation, and then z will not have any matching possibility since it there is no node in the facts connected to y via plays-in relation and to "F ootballT eam" via is-a relation. This branch will then be left and other branches will be explored in order to find a positive answer. On the other side, when x is paired with x, y will then be paired to u, and z to p, which is a Football Team. True is then returned by the algorithm, meaning that there is in fact an homomorphism from Q to F , and the matched nodes set {(x,x),(y,u),(z,p)} is the answer of our query.

There are thus two elementary operations needed in order to calculate a homomorphism from the query graph to the facts:

• Matching a vertex from the query graph with another in the facts graph 5 • Accessing the neighborhood of both matched vertices to check whether their edges and adjacent vertices are compatible or not. While matching vertices from two different graphs into a pair can be easily done in constant time, efficient access to the neighbourhood of a vertex is primordial in order to have some real advantage over traditional relational database systems.

For instance, for a n-ary predicate p of arity 4, the complexity of searching for the presence of an atom p(x, < c1 >, y, < c2 >) in a KB using a relational database is O(m p ), m p being the size of the table p. Using a graph-based KB instead, this complexity can be improved to O(d <c1> ), with d being the size of the neighbourhood of a given vertex, in this case < c1 >, if there are optimized data structures and algorithms to quickly access the neighbourhood of a vertex. This improvement is due to the fact that the encoding of semi-structured data into a graph does generate a graph with a very small density, in which good efficiency 5 We do not make the assumption that the facts graph is connected.

is obtained when accessing the neighbourhood of a vertex. However, there is still no efficient method for doing it when the graph-based KB is stored in secondary memory.

It is however impossible to have an answer for the second query without enriching the KB with new facts (or rewriting the query). Let us detail in the next section how rule application takes place.

C. Rule application in a graph-based KB

The forward-chaining method for rule application in a graph-based KB that will be described more precisely in this part of the paper mimics exactly the chase method mentioned in Section II-C. In a graph-based KB, rules are represented using two pieces of graph: head (hypothesis) and tail (conclusion). Figure 9 and 10 show the graph representation of the Rules ( 2) and (4) from the example in Section II. Rule application works in two steps: first, the head of the rule needs to be deducted from the facts (using homomorphism). Then, if there is a homomorphism, the conclusion gets added to the graph respecting links between vertices in head and tail parts of the rule. The method we use to enrich the graph-based KB is called forward-chaining, which consists in applying all rules of the rule set until there is no more new information to be added to the KB. Note that while rule (2) only adds edges to the facts graph rule (4) can also introduce new variables to the KB. This is the reason why, apart from the efficient operations mentioned above, we need a flexible data structure that also allows quickly adding edges and nodes to the graph. Figure 11 shows the facts graph after applying rule (4). Once the graph saturated with all the rules, the second query can be answered in the same way as described before.

"P erson" x y u v "Organisation" "Bob" "T om" p q "F ootball "Rugby T eam" T eam" "RueAda -M ontpellier" t "Club" is-a is-a name name is-a is-a works-f or works-f or is-a is-a plays-

IV. CONCLUSION

Knowledge Representation and Reasoning (KRR) studies computational models for building explicit representations of knowledge processed by reasoning engines. Given the need for increasingly large knowledge, research into KRR must move now towards investigating structures for representation, optimally manipulated to perform large scale reasoning.

In this work, we have compared two different approaches for the ontological conjunctive query answering. We have first introduced the method for performing reasoning over a KB using a relational database with a set rules. This method has already proved that it works very well when dealing with large sets of structured data, stored whether in main or in secondary memory. Then we have presented another approach for solving our problem using a graph-based KB with graph rules. As we have showed before, this approach ensures an unicity between the KB and the query languages and has theoretically better results than the first method when reasoning over semistructured data.

Nevertheless, our graph based approach for representation6 and reasoning 7 only works well when the facts hold in main memory. This is why we are now interested in finding adequate storage solutions suitable for our graphs reasoning manipulations. More precisely, as shown in the previous sections, the reasoning mechanism we use on graphs is labelled graph homomorphism. When detailing our backtracking algorithm we identified two important qualities of the desired graph based storage: a good indexing on nodes (that facilitates the identification of potential candidates for matching) and an efficient structure of access to the neighbors of a given node, and, for these neighbors, its subsequent neighbors. Moreover, rule application will mean that our structure also needs to be flexible for the insertion of new nodes and edges.

After having set the operations we need in order to perform reasoning over graphs, our future work will consist in evaluating current solutions to the ontological conjunctive query problem (such as AllegroGraph8 , Neo4J9 or HyperGraphDB 10 ) and testing their large scale efficiency. In parallel, we will also investigate different graph paradigms for storage that allow efficient manipulation for the operations previously described.

Fig. 4 .

 4 Fig. 4. address relation

• ( 8 )

 8 HERE works-f or.2 = isa1.1 AN D isa1.2 = "Organisation" AN D plays-in.2 = isa2.1 AN D isa2.2 = "F ootballT eam" SELECT * F ROM co-worker,same-club W HERE co-worker.1 = same-club.2 AN D coworker.2 = same-club.1

Fig. 7 .Fig. 8 .

 78 Fig. 7. Graph representing the query (7) from Section II.

Fig. 9 .

 9 Fig. 9. Graph representing the Rule (2) from Section II.

Fig. 10 .

 10 Fig. 10. Graph representing the Rule (4) from Section II.

http://nosql-database.org/

http://www.lirmm.fr/graphik/index.html

One has to be careful with rules adding new constants or variables to the knowledge base since some of them could be fired forever (for example "Every person has another person as its parent".) For more information please see[START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF].

If the predicate in the knowledge base is n-ary, we represent it as a hyperedge. In our example, we have only binary predicates, thus simple edges.

http://www.lirmm.fr/cogui/

http://cogitant.sourceforge.net/

http://www.franz.com/agraph/allegrograph/

http://neo4j.org/

http://www.kobrix.com/hgdb.jsp