Laurent Guichard
email: laurent.guichard@irisa.fr

Joseph Chazalon
email: joseph.chazalon@irisa.fr

Bertrand Coüasnon
email: bertrand.couasnon@irisa.fr

Exploiting Collection Level for Improving Assisted Handwritten Word Transcription of Historical Documents

Keywords: document analysis, document sets, handwritten word recognition, historical documents

Transcription of handwritten words in historical documents is still a difficult task. When processing huge amount of pages, document centered approaches are limited by the trade-off between automatic recognition errors and the tedious aspect of human user annotation work. In this article, we investigate the use of inter page dependencies to overcome those limitations. For this, we propose a new architecture that allows the exploitation of handwritten word redundancies over pages by considering documents from a higher point of view, namely the collection level. The experiments we conducted on handwritten word transcription show promising results in terms of recognition error and human user work reductions.

I. INTRODUCTION

In the context of historical document recognition, transcription of handwritten words is still challenging. Due to the degradation or the specificity of the document handwritings, state-of-the-art automatic recognition is not yet able to fully transcribe this kind of documents. Therefore, human help is necessary to assist the document analysis system; by correcting the detected recognition ambiguities and difficulties.

However, when processing a huge number of document pages, the user annotation work may become tedious.

Even when the system includes a re-training phase to improve over time the recognition, the ground truth for learning requires the human user intervention.

Facing the same limitations of imperfect automatic recognition and of not overloading the human user with annotation, we looked for new and complementary information sources to overcome those restrictions.

As [START_REF] Saund | Scientific challenges underlying production document processing[END_REF] pointed out, the semantic dependencies between document pages could be exploited to improve document recognition. To benefit from this inter pages link, a higher point of view is adopted, namely collection level, From the collection level, redundancies over pages can be used. For example, some identical words written by the same person contained in two different pages can be grouped together to enforce their individual recognition hypothesis or to be annotated at the same time by a human user. Also, at this level, page contents continuity carries information. For example, the knowledge that handwritten numbers spread over pages form an increasing sequence can be used to optimally recognized them.

For the problem of historical handwritten words transcription, there exists a strong redundancy and homogeneity between document pages. We believe that grouping words at collection level will improve overall document recognition.

To evaluate this idea, we developed a document recognition architecture. In the literature, different kind of architecture are proposed. The DocMining [START_REF] Clavier | DocMining: A cooperative platform for heterogeneous document interpretation according to user-defined scenarios[END_REF] system is similar to a workflow of processing tasks. For each kind of document, a processing scenario is defined, made of tasks such as binarization, connected components extraction, user interaction GUI, etc. The document attached information is updated after each task. While this system is highly configurable, it is document centered and does not provide a common place to manipulate collections of documents. Another system, smartFIX [START_REF] Klein | smartFIX: An adaptive system for document analysis and understanding[END_REF], proposes an industrial framework to analysis printed medical bills. It integrates an improving module that can check consistency and optimize interpretations in multi-page documents. This system was aimed at analyzing business documents, hence as they are mainly independent documents, its architecture cannot be configured enough to integrate collection level knowledge.

Keeping the concept of tasks cooperating through a workflow, our architecture has the following specificities to exploit the collection knowledge: It enables tasks to cooperate at collection level through its strategy component; and it manipulates the document information at collection level, thanks to a central storage database component.

By grouping document data at a higher level, our architecture must not break the strong bond between the information at document level and at collection level. Our architecture employs an iterative mechanism to satisfy this constraint.

To summarize, this article has two main contributions :

• present an iterative multi-level architecture to transcript handwritten words; • demonstrate that processing document at collection level leads to better result in term of user intervention and recognition performances. This work is organized in the following way. Section II and III address in detail our architecture. Experimental results and conclusion are presented in sections III and IV.

II. EXPLOITING COLLECTION LEVEL

The next two sections detail the strategy and database components needed to work at collection level. Section II-C explains our iterative mechanism to tie together the different levels. Figure 2 synthesizes the different components of our architecture through an example strategy.

A. Cooperation at Collection Level

Considering the documents from the collection point of view offers new ways of handling their processing. In our case, we are interested in processing the 18th century French revolutionary sales documents, shown in figure 1a, and more precisely in extracting and recognizing the handwritten words in the highlighted columns. Those documents inventory the goods that were sold during the revolutionary sales around year 1791. They are arranged in tables, each row corresponding to a sale. First highlighted column is the former owner and second is the new owner. Some extracted sample words are presented in figure 1b.

Those documents cannot be recognized automatically because of singular handwriting, time degradation, noise and word overlapping. Thus, human users usually must label by hand some of the words. A simple two stages approach can be used. The first document of the collection is given to a document analyzer which extracts and tries to recognize the handwritten words. Those rejected are annotated by a human user. Then, the second document is processed and so on.

More evolved strategies to handle document recognition could be envisaged. For example, in order to increase the amount of words recognized automatically, we could regroup in clusters all the words amongst the document that graphically "look the same" and then use word individual recognition hypotheses to label the cluster with more confidence. Exploiting word redundancy at collection level by combining word spotting, word clustering and handwritten word recognition could lead to better automatic recognition.

Nevertheless, whatever the ways those processes are assembled, the human user intervention is going to be required. Some of the words would be rejected and they would need to be labeled by hand. But, again, decreasing the amount of work asked to the user could benefit from the collection point of view. Instead of presenting the user one word at a time, he could label the clusters and therefore the annotation of the words in the cluster done in one user action.

Those examples suggest two remarks and their corresponding consequences for our document processing architecture. First, obviously, many king of strategies are possible. Consequently, the presented architecture allows the specification of user own strategies independently from the processing tasks.

Second, the strategy schedules the processing tasks. It is responsible for creating, manipulating and executing the tasks. By considering the documents at collection level, the cooperation of tasks like document analysis, handwritten word clustering and user interaction, is enhanced.

The intra pages regularities can easily be used as information over all documents can be gathered at collection level.

B. Manipulating Document Information

To efficiently group the redundant handwritten words, the clustering task must be fed with word images extracted from several pages. For this, the strategy is able to collect, manipulate and choose the data transiting between tasks so that they work at different levels. The collected data are stored in a central storage database.

Since we are interested in handwritten word recognition, we introduce the main data type field transiting between tasks and stored in the database:

• A contents type • A 2D bounding box • A list of top n recognition hypotheses h i defined by a
word w i and a confidence score s i • A final word In the above definition, a word is a transcription of a handwritten word found in a document and that belongs to a known lexicon. The ultimate value of a field is stored in its final word attribute.

Our architecture permits to overcome the difficulty of grouping data extracted from documents. When the strategy, for example, queries the database for all the fields to feed the clustering task, the document physical segmentation is abstracted to consider things at collection level. It implicitly switches from one level to another.

At this point, we have considered only the bottom-up part of our multi level architecture going from document level to collection level. The fields exchanged between tasks are a simple type, they do not embed any higher knowledge about, for example, their semantic connection to another field. It means that some constraints on a field, known only inside the document analyzer task, may not be respected by others tasks that could modify the field. To fulfill the intra document constraints, an iterative scheme is used.

C. Iterative Mechanism

As an example of intra-page bond between fields, we can consider the documents illustrated in figure 1a, where the word "IDEM", in the former owner column, means that the name in the current row is the same as the one in the previous row. This knowledge is kept, like any intra-page constraint, in a single page model embedded in the page analyzer to: i) simplify their development; and ii) ease the validation of model constraints in a single component.

When some fields are extracted by the page analyzer but not recognized because of ambiguities, they are stored in the database and another task will take those fields and affects values to their final word attributes that may not take into account their link. Then, the strategy calls again the document analyzer, with, as input, the page and the fields with their actual final word values. The attribute values are kept if no constraint is broken, otherwise they are swept and the whole process is repeated until the document is completely recognized, as symbolized in figure 2.

The top-down part of the multi level architecture consists in re-injecting those fields into the page analyzer such that the constraints between them is verified, thanks to a method we proposed in [START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF]. It is not detailed in this paper as we focus on the global architecture enabling the use of collection context. The bottom-up and top-down parts form an iterative mechanism in the multi level architecture, which somehow conciliates the apparent contradiction between centralizing the document knowledge in one task and manipulating the extracted document fields at the collection level.

III. IMPLEMENTATION OF OUR MULTI LEVEL ARCHITECTURE

A. Storing Information

The information to be stored is heterogeneous. Some data are related to the collection level: the list of field clusters. Others are of document level: the fields. To mix them up easily in our database, we chose HBase part of the Hadoop framework 1 . The main advantage of this database is to ease the selection of fields according to the page they belong to, or to their content type: number, family name, city name. . .

B. Defining the Strategy

As the Hadoop framework would require some extensions to enable an efficient interaction, we currently use a prototype designed in Python which enables a quick chaining of the various task tools we use. The strategy it implements will automatically run the task processes with appropriate data, and gather their results when their are done, using the database previously presented to store them.

C. Tasks

The tasks can be implemented as a C/C++ shared library, a python script, a binary executable, a remote GUI client, etc. They all respect the same Python interface. We now details the tasks used in the strategies we evaluated in section IV.

1) Page Analyzer: The document recognition is performed using DMOS-P [START_REF] Lemaitre | Multiresolution cooperation makes easier document structure recognition[END_REF], a concept-driven grammatical method for structural analysis of pages, which uses page descriptions to analyze and extract contents. In order to be able to reintegrate manually annotated elements in the document structure and validate them, we use a recent extension of DMOS-P [START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF] which enables an iterative analysis of document pages. Therefore, according to a page model we defined, a page analyzer processes each page as follows.

• The analyzer is provisioned with all the fields related to the current page stored in the database. • It locates the textual fields to be transcribed.

• For each field, if a transcription is already available in external data, it is used to fill the final word attribute.

Otherwise, the field is submitted to the handwritten word recognition system detailed in [START_REF] Guichard | A novel verification system for handwritten words recognition[END_REF]. The confidence score associated to the returned word hypothesis is compared to a rejection threshold. If above, the transcription is validated, otherwise it is rejected and marked for external correction.

• All the fields are sent back to the strategy module. The incomplete fields may be filled elsewhere in the strategy.

2) Field Clustering: This task aims at regrouping the fields containing the same word. It works on samples which are, in the present case, 2D graphic images corresponding to the field 2D bounding box extracted from the original document image.

First, the samples, transformed to a set of features, are pairwise compared using dynamic time warping to get matching scores that are stored in a cost matrix M. As the samples are images containing handwritten text, the extracted features are the one detailed in [START_REF] Rath | Features for word spotting in historical manuscripts[END_REF].

Then, a hierarchical agglomerative clustering algorithm is initialized by treating each sample as a cluster. Afterward, the clusters are pairwise merged up till the distance between them exceed a given threshold T c . The distance d i,j between clusters C i and C j is computed as:

d i,j = max e k ∈Ci,e l ∈Cj
M (e k , e l )

3) Cluster Recognition: Considering that, at this stage, the clusters newly created are homogeneous, this task goal is to assign to each cluster a word label based on individual field recognition hypotheses.

Let C be a cluster composed of N samples e i and to each sample e i is associated a list of the top n i recognition hypothesis h i,j , j ∈ [1, n i ] (coming from the field recognition). We define the auxiliary functions: L : h → w and S : h → s where w and s are respectively the word and score associated to h. Furthermore, we introduce H k as:

H k = {h|L(h) = w, w ∈ W, w / ∈ H i , ∀i < k} where W = {w|w = L(h i,j ), i ∈ [1, N ], j ∈ [1, n i ]}.
Therefore, a cluster recognition hypothesis h k is defined as a combination of the word w k = L(h) with h ∈ H k and the following score s k :

s k = 1 Z ∀h∈H k S(h) where Z = N i=1 n i
Then, the cluster recognition hypotheses are re-ordered according to their score s k , defining a new list: ĥ1 , ĥ2 , ... . A thresholding action is performed by assigning w 1 = L( ĥ1 ) to cluster C, according to: if S( ĥ1 ) -S( ĥ2 ) ≥ T r then accept w 1 else reject w 1 where T r is a rejection threshold. The word label assigned to the cluster is spread to the fields constituting the cluster.

It is worth mentioning that the thresholding action relies on the ability of the handwritten word recognizer to efficiently reject ambiguous samples. The recognizer we used was specially developed for this purpose [START_REF] Guichard | A novel verification system for handwritten words recognition[END_REF].

4) User Interaction:

The human user cooperates to the fields recognition by annotating the clusters. The user is presented successively the homogeneous clusters, not automatically recognized by the cluster recognition task. He has a view of one sample of the cluster and he must type the handwritten word he sees. The word label thereby assigned to the cluster is spread to the fields constituting the cluster.

IV. EXPERIMENTS ON ASSISTED HANDWRITTEN WORD

TRANSCRIPTION The experiments we conducted aim at showing that document processing at collection level can improves both automatic recognition and user annotation work. We present 2 different strategies, one exploiting the collection level. The iterative mechanism is not evaluated here.

A. Test Documents

For our experiments, 70 document pages looking alike the one in figure 1a where used. It forms a set S of 1206 extracted handwritten fields that need recognition. The localization and extraction were not evaluated in the experiments. Amongst those 1206 fields, they are 502 different words.

B. Tested Strategies

We compared 2 different strategies made of the tasks detailed in III-C.

Baseline: document pages are processed with the document analyzer, the rejected fields are annotated by a human user depending on threshold T r . There is no collection level clustering and no iterative mechanism.

Clustering: document pages are processed with the document analyzer. Clustering task, controlled by T c , regroups the fields. Then, the clusters are either automatically recognized or annotated by a human user depending on T r .

The number of recognition hypotheses was set to 10. Both thresholds T c and T r were tuned using a grid search on a validation set.

C. Experimental setup

In those experiments, we are focusing on the amount of work for human user. We are evaluating user interaction as described in III-C4.

For the Baseline (resp. Clustering) strategy, a user interaction is to label a field (resp. cluster) by hand.

We aim at minimizing the number of user interactions, in our case, this is equivalent to minimizing the number N M of manual annotations.

This absolute count of manual annotations has to be compared to the worst case where all the fields are labeled by hand, equal to |S|.

Thus, we adopt the following definitions for Manual annotation Rate (MR), Error Rate (ER) and Automatic annotation Rate (AR): where N e is the number of incorrectly annotated field. For the Baseline strategy, an incorrectly annotated field is due to an error of the handwritten word recognizer. For the Clustering strategy, an incorrectly annotated field is either caused by a recognizer error or by a clustering mistake. As an example, suppose the clustering has incorrectly regrouped 5 fields in a cluster. 4 have the same label l and 1 has another. If the cluster is assigned automatically label l, cluster MR is 0, ER is 0.2 and AR is 0.8. If the cluster is assigned manually label l, cluster MR is 0.2, ER is 0.2 and AR is 0.6.

M R = N M |S| ER = N e |S| AR = 1 - N M + N e |S|

D. Results

Table I presents the results of the experiments for two strategies.

When reject is disabled, there is no manual annotation. A field is either well (goes into AR) or incorrectly recognized (goes into ER). It has to be noted that the recognition of handwritten words in our historical documents is hard as the Baseline strategy only gets 64% of automatic annotation. In addition, it is worth mentioning that the top 10 AR is of 71% (+ 7%).

The AR increases from 64% to 66% between the Baseline and Clustering strategies. This moderate improvement (2%) should be to compared to the top 10 AR of 71%. Indeed, it means that Clustering strategy is able to "recall" 2% of those potential 7%, i.e. more than 25% of them.

Reject is used for controlling the error rate. When working in document retrieval domain, the need is to transcribe as many fields as possible with a reasonable amount of manual annotation and error. In this case, the Clustering strategy decreases relatively the amount of manual annotation by 19%, from 21% to 17%, with an error rate of 20%. The obtained annotation rate (AR + MR) is then 80%.

An error rate of 1% is appropriate to get automatically some reliable ground truth for recognizer retraining purpose. For such error rate, the Clustering strategy increases relatively the automatic annotation rate by 58% compared to the Baseline strategy (from 24% to 38%). More generally, the Clustering strategy most clearly outperforms the Baseline strategy for low error rate.

V. CONCLUSION

This paper introduces a document analysis architecture that allows to process documents at collection level. From this higher point of view, redundancies and homogeneities between pages can be efficiently exploited so as to improve results quality and lower human workload. The architecture is based on three elements: a strategy module; a central database; and an iterative mechanism. The experiments conducted on historical documents show that clustering handwritten words according to their shape leads to an improvement in performances, for two different tasks. For document retrieval which requires the indexing as many elements as possible, a reasonable error rate is conceivable, and the use of collection context permits a relative diminution of 19% of human workload for an overall annotation rate of 80%. For the adaptation of the system through retraining, a very low error rate is necessary, and our approach enables a relative diminution of 25% of human workload for an overall annotation rate of 99%.

Our current perspectives are to: i) investigate the impact of the aggregation function which fusion label hypothesis in a cluster, as it could also help recognizing suspicious elements instead of suppressing them; and ii) to quantify the adaptation capability of the system over several passes, after bootstrapping using human-produced ground-truth.

Figure 1 .

 1 Figure 1. (a) Sample of the 18th century French revolutionary sales documents to process. Highlighted columns are to be extracted and recognized. (b) Extracted words: "CURE D'HERBLAY', "PIGIS", and "IDEM".

Figure 2 .

 2 Figure 2. Example strategy to process historical documents based on our iterative architecture

Table I RESULTS

 I FOR TWO STRATEGIES. AR = AUTOMATIC ANNOTATION RATE (%), MR = MANUAL ANNOTATION RATE (%), ER = ERROR RATE (%)

	Strategy	AR	W/o reject MR	ER	AR MR	With reject ER AR	MR	ER
	Baseline Clustering	64 66	0 0	36 34	59 63	21 17	20	24 38	75 61	1

Documentation at http://hadoop.apache.org

ACKNOWLEDGMENT

This work has been done in cooperation with the Archives départementales des Yvelines in France, with the support of the Conseil Général des Yvelines.


Keywords: MCPyV, Environment, Surface

F o r P e e r R e v i e w

The Merkel cell polyomavirus (MCPyV) is a human virus identifed recently which is 2 associated with the Merkel cell carcinoma. This virus is also detected frequently in the skin of 3 healthy individuals. The presence of MCPyV has been investigated on environmental surfaces 4 in contact with human skin. Various surfaces in 4 laboratories, public places, and individual 5 homes were swabbed. Human DNA and MCPyV DNA were detected in swabs by real-time 6 PCR. MCPyV DNA levels were measured before an after DNase treatment in a set of 12 7 MCPyV DNA-positive samples. A total of 60 environmental surface samples were collected. depending on the environment, with a particular focus on objects with frequent contact with 2 human skin. They were various handles (doors, refrigerators, freezers, incubators), keyboards 3 (lifts, computers, drink dispensers, cash dispensers, ticket machines) and stair banisters. In 4 each environment, surfaces not exposed to contact with human skin, such as walls sampled 5 around 2 m off the ground, or hood working surfaces in the laboratories, were swabbed as 6 controls (Table 1).

Results

6

A total of 60 surface samples were collected. Fifty-one (85%) were positive for human DNA 7 detection and 45 (75%) were positive for MCPyV DNA detection (Table 1). MCPyV DNA 8 positivity was 81%, 100% and 67% for samples collected in laboratories, city and individual 9 homes, respectively (P = 0.2). Human DNA levels in positive samples ranged from 5.0 to 10 2,700 pg/µL (median, 25 pg/µL). All MCPyV-positive samples were positive for human 11 DNA detection. Among the 11 samples collected on walls, 9 (81.8%) were negative for 12 human DNA and 10 (90.1%) were negative for MCPyV DNA. [START_REF] Feng | Clonal integration of a polyomavirus in 14 human Merkel cell carcinoma[END_REF] The median MCPyV DNA level was 2.8 log copies/ng of human DNA (range 0.8-5.2 log 14 copies/ng of human DNA). No correlation was observed between MCPyV DNA and human 15 DNA levels (R 2 = 0.007). 16 A set of 12 samples positive for MCPyV DNA were processed in parallel with and without 17 DNase treatment. Median human DNA level in these samples was 97 pg/µL (range 10-762 18 pg/µL). Median viral DNA load in these samples was 2.45 log copies/µL (range, 1.6-4.2 log 19 copies/µL). After DNase treatment, MCPyV DNA was still detectable in 10 samples with a 20 median level that decreased to 1.14 log copies/µL (range 0.7-3.8 log copies/µL), representing 21 a decrease of 1.3 log in MCPyV DNA level and indicating that about 5% of viral DNA was 22 protected from DNase degradation (Fig. 1). In contrast, in the same conditions human DNA 23 became undetectable after DNase treatment of the samples. 24 High viral DNA levels despite low human DNA levels might be explained by the fact that the 6 cutaneous viruses are abundantly present in the most superficial layers of the epidermidis, the 7 stratum corneum, composed mainly of dead and apoptotic cells with genomic DNA 8 fragmented by host cells DNases that might not affect viral DNA. This might also explain 9 why levels of MCPyV DNA, as normalized to human DNA, in environment samples were 10 higher than those reported previously in human skins specimens [Foulongne et al., 2010b]. 11

The relative high level of MCPyV DNA normalized to human DNA on environmental 12 surfaces might be explained also by an accumulation of viral DNA more resistant to 13 degradation than human DNA. This cumulative effect may also explain the highest, although 14 not significant, MCPyV DNA detection rate observed in the public environment, since the 15 objects sampled were more prone to be handled by many people as compared with those 16 sampled in individual homes. 17

8 Fifty 1 The

 81 -one (85.0%) were positive for human DNA detection and 45 (75.0%) were positive for 9 MCPyV DNA detection. All samples positive for MCPyV DNA were positive for human 10 DNA detection. After DNase treatment, a 1.3 log decrease in MCPyV DNA level was 11 observed indicating that about 5% of viral DNA is protected from DNase degradation and 12 might be associated with infectious virus. These results indicate that MCPyV DNA may be 13 detected on environmental surfaces in contact with human skin. Detection of viral DNA might 14 reflect the presence of infectious viral particles and transmission from environmental source 15 to humans cannot be ruled out. 16 Merkel cell polyomavirus (MCPyV) is a novel human polyomavirus discovered in a rare 2 and aggressive neuroendocrine skin cancer, the Merkel cell carcinoma [Feng et al., 2008]. 3 Subsequent studies have confirmed that, unlike the other human polyomaviruses, MCPyV 4 has an oncogenic potential [Shuda et al., 2008; Sastre-Garau et al., 2009; Shuda et al., 2009]. 5 However, seroepidemiological studies indicate that MCPyV circulates widely in the human 6 population [Kean et al., 2009], and a widespread distribution of MCPyV in the human 7 population was suggested recently by studies reporting a frequent detection of MCPyV in 8 cutaneous swabs from healthy adults [Foulongne et al., 2010b; Scholwalter et al., 2010; 9 Wieland et al., 2010]. These studies indicate that MCPyV causes a persistent asymptomatic 10 infection of the most superficial layers of the epidermis. The route of transmission of MCPyV 11 remains uncertain. Possible respiratory or fecal-oral routes of transmission have been 12 suggested, supported by the detection of the virus in respiratory secretions, in saliva or in 13 urban sewages [Bialasiewicz et al., 2009; Loyo et al., 2010; Bofill-Mass et al., 2010]. The 14 high rate of detection of MCPyV DNA in the superficial skin might indicate a cutaneous route 15 of transmission through contact with human skin or contaminated surfaces. The aim of the 16 present study was to investigate the contamination of environmental surfaces by MCPyV. swabbed by laboratory workers wearing gloves, using cotton-21 tipped swabs soaked in phosphate buffer saline (PBS). Samples were collected from various 22 surfaces located in the laboratory involved directly in the study (lab.1), in three other 23 laboratories not involved in MCPyV detection, in public environment within the Montpellier 24 city, and in six individual homes from lab. 1 workers. Swabs were transported at room 25 at -20°C until analyzed. Surfaces that were swabbed were chosen 1

7 8 18 19 1 (

 7181 DNA extraction and DNase treatment 9Swabs were suspended in 600 µL of PBS and DNA was extracted from 200 µL of the 10 suspension with the EasyMag nucleic acid extractor (BioMérieux, Marcy l'Etoile, France). 11For DNase treatment, the residual suspension was separated into two 200 µL fractions. The 12 10X DNase buffer was added and 2 IU of DNase (New England Biolabs, Ipswich, MA) was 13 added in one fraction, the other being completed with the corresponding volume of PBS. Both 14 fractions were incubated 1h at 37°C and heated 10 min at 95°C for DNase inactivation prior 15 DNA extraction. The elution volume was 50 µL, and 5 µL of eluate was used for subsequent 16 PCR assays. A non-used swab processed under the same conditions was included in each run 17 as negative control.MCPyV and human DNA quantitation 20MCPyV DNA was detected and quantified by real-time PCR in the large T-antigen coding 21 region as previously described[Foulongne et al., 2010a]. Positive results were confirmed by a 22 second real-time PCR targeting the VP2/3 region[START_REF] Bialasiewicz | Merkel cell 2 polyomavirus DNA in respiratory specimens from children and adults[END_REF], located outside 23 the regions amplified previously in the laboratory. 24 levels in samples were measured using the LightCycler control DNA kit Roche Diagnostics, Meylan, France) and results were expressed as MCPyV DNA copies/ ng 2 of human DNA or as MCPyV copies/µL for sample comparison when DNase treatment was 3 applied. 4 5

1 Polyomaviruses

 1 are non-enveloped, double stranded DNA viruses that may persist in various 2 environmental media [Bofill-Mass et al., 2001; Jiang et al., 2009]. Results from the present 3 study indicate that MCPyV DNA is detected with a high frequency on the environmental 4 surfaces. 5

Figure 1 1

 1 Figure 1 1

Table 1 :

 1 Detection of human DNA, MCPyV DNA on environmental surfaces

		Human DNA		MCPyV
	Environmental surfaces	Beta-globin target	LT3 target VP2/3 target Viral load (copies/ng of human DNA)
	Lab.1 Incubator handle 1	+	+	+	2,875
	Incubator handle 2	+	+	+	20,226
	Incubator handle 3	+	+	+	52
	Main door handle	+	+	+	2,250
	Stairway banister	+	+	+	2,588
	Door handle 1	+	+	+	611
	Door handle2	+	+	+	167
	Freezer handle	+	+	+	100
	Lift keyboard	+	+	+	1,600
	Hood working surface	+	-	-	na
	Wall1	-	-	-	na
	Wall2	+	-	-	na
	Lab.2 Drink dispenser keyboard 1	+	+	+	2,941

F o r P e e r R e v i e w F o r P e e r R e v i e w


Jens Gustedt

Stéphane Vialle

Hervé Frezza-Buet § , D'havh Boumba

Nicolas Fressengeas

Jeremy Fix

InterCell: a Software Suite for Rapid Prototyping and Parallel Execution of Fine Grained Applications *

Keywords: fine grained parallel models, interactivity, rapid prototyping

InterCell is an open and operational software suite for implementation, code generation and interactive simulation of fine grained parallel computational models. This article describes the software architecture, some use cases from physics and cortical networks as well as first performance measurements.

InterCell: Une suite logicielle pour le prototypage rapide et l'exécution parallèle d'applications à grain fin 6 Résumé : InterCell est une suite logicielle libre et opérationnelle permettant l'implantation, la génération de code et la simulation interactive de modèles de calculs parallèles à grain fin. Cet article décrit son architecture logicielle, ainsi que des cas d'utilisations issus de la physique et du connexionnisme, et présente finalement les premières performances mesurées.

Mots-clés : parallélisme à grain fin; interactivité; prototypage rapide 6 Cet article a été accepté pour publication dans le post proceedings de PARA 2010.

Introduction

The goal of the InterCell project is to help non-experts in parallel computing to use large scale parallel computers when developing models for physical phenomena, especially when these models have to be evaluated at large scale. To achieve this goal a software suite has been developed in order to allow rapid design and implementation of fine grained parallel computing models on coarse grained parallel architectures, e.g clusters or mainframes. The InterCell development cycle typically has several stages:

(1) rapid design of a mathematical model,

(2) automatic implementation of a fine grained parallel simulator,

(3) parallel execution of large scale interactive simulations, and

(4) large scale prototyping from the very beginning of model design. Fine grained models of computation are widely adapted in different application domains. For our project this concerns two of these domains, namely the modeling of physical phenomena that have some notion of 'locality' (spatial or timely) and the modeling and development of neuromimetic networks [START_REF] Ménard | Model of multi-modal cortical processing: Coherent learning in self-organizing modules[END_REF]. But most likely InterCell could be useful for other domains as well.

Fig. 1 introduces the InterCell software architecture. At top level users describe their problems with application domain tools, such as a PDE solver or a cortical inspired neural network simulator. These high level tools generate fine grained parallel simulators, using a C++ library named Booz1 . This library ensures the interactive control of the simulations and in turn uses the parXXL library 2 . With that, it efficiently maps the fine grained computations on coarse grained parallel architectures. The parXXL runtime hides the underlying parallel or distributed hardware. The final software has two parts: a parallel and interactive server that handles the actual computations, and a set of easy-to-use control and visualization clients.

Fine grained parallel computations

Fine grained computations that act on statically structured data (generally matrices) are nowadays well mastered and can be parallelized on coarse grained architectures (typically multicore clusters) with good results.

The case focused here is the computation on unstructured data for which the structure may even change occasionally and where the compute function that has to be executed may differ for each data point. Here an efficient mapping of computations to processors is not straightforward and good efficiency is generally difficult to achieve. parXXL provides a framework that facilitates programming under such constraints and draws good performances out of nowadays platforms.

The parXXL framework, see [START_REF] Gustedt | The parXXL environment: Scalable fine grained development for large coarse grained platforms[END_REF], includes several software layers, as shown in Fig. 1. Important for this project here are the following. par::cell: a set of functionalities and a programming model to design and implement fine grained computations in the paradigm of so-called cellular For the par::cell layer, it allows to group the cell data and output and access them in order or through hashed indices.

par::cntrl: handles the basic communication functionalities. It abstracts from the underlying runtime, currently MPI or POSIX threads. In particular important for this project has been the transfer family of functions that implements a all to all v communication (used when each parXXL process needs to exchange different data with all other processes). In combination with the resizability of the mem::chunk, transfer dispenses to specify communication sizes and to allocate buffers beforehand.

For the par::cell layer, these functions are mainly useful to implement cell communications, cell network creation and update.

par::bench: is used to instrument the library and to collect various performance data. In particular it registers the number of communications and their size, wall-clock and CPU times.

All these features are the foundations of parXXL, and have already been introduced in [START_REF] Gustedt | The parXXL environment: Scalable fine grained development for large coarse grained platforms[END_REF] and [START_REF] Fressengeas | An interactive problem modeller and PDE solver, distributed on large scale architectures[END_REF]. However, we have improved parXXL to support more asynchronous execution of cell networks, to easily collect and save results of large cell networks, and to increase its portability.

Cells can communicate the data from output to input channels in a synchronous or quasi-asynchronous mode. If in synchronous mode, cell input is updated at the end of each computation cycle. In quasi-asynchronous mode, cells are grouped in subsets and the output channels of the different groups are routed at different communication sub-cycles in the middle of the cell computations. So different cells reading a same output channel can read different values, depending on the concrete time of execution of their behavior functions in the computation cycle. The number of communication sub-cycles can be tuned at execution time. More sub-cycles lead to more asynchronism but to longer cell execution cycles.

In order to ease the extraction of results from large cell networks, we have designed some collector generic classes, and we have defined some new missions to easily run these data collection from a controlling sequential program. All these collections of large data are stored in chunks. These have been improved to map into files and avoid memory size limitations. Some optimized functionalities to read and write large data files storing N -dimension arrays of output channel values, have been added to parXXL. For example, they ease the initialization of large cell networks from data large files containing initial values for the output channels.

Finally, three parXXL runtimes exist: a first on top of MPI, a second on top of POSIX threads for multicore shared memory architectures, and a third on top of shared memory segments. All runtimes are available on 32 and 64 bits architectures. Moreover, great efforts have been made to improve the portability of our C++ template classes and functions, and our C++ meta-computing code. All these improvements make parXXL available and efficient on a larger set of parallel architectures.

Interactive parallel computations

One original property of the InterCell software suite is that cellular computation can be performed interactively. It allows visualization, writing and loading of snapshots, setting of cell values. This are all performed while the cellular automaton is briefly suspended. In addition it allows to step through the execution of the application. In our context that means that compute cycle after compute cycle may be observed individually. These features are provided by the Booz library that includes a visualization client, see Fig. 3.

Figure 3: Example of interactive Booz client

This interactivity allows to use a cluster for situated systems, like robots, where cellular computation models the inclusion of an artificial brain in some real robot perceptivo-motor loop. It also provides a real-time view of the running process, that allows to detect convergence problems of the cellular models. Such an on-line availability allows programmers of cellular automata to prototype their model at a large scale, from the very first design stage. This is of primary importance since properties of large scale discrete dynamical systems are not easily predictable from small prototypes. The application of Fig. 5 is modeled as a 2D grid of cells, each connected to its 8 neighbors. Here, each cell represents the elongation of a coil spring that is coupled to neighboring springs, in order to create 2D waves along the grid surface. The springs have different elasticity, the "lens" that is visible in light yellow shows the distribution of the elasticity among the springs.

Examples of InterCell usage

The the next sections, give the details of two simulations are real use cases of the InterCell suite, and that correspond to applicative research that was achieved in our laboratories.

High level application codes

As illustrated in Fig. 1, applications are developed using high level programming environments and not the parXXL or Booz layers directly. The semiconductor simulation detailed in Section 4.2 has been implemented using only the SAGE programming environment. This allows to implement our PDE within a mathematical paradigm, easily. Our PDE solver module then automatically generates C++ source files that wrap Booz and parXXL functionalities. A final C++ compilation produces a parallel application running on any parXXL runtime.

The cortical networks detailed in Section 4.3 have been developed in C++, using our Bijama library (see Fig. 1). Again, the application developer focusses on the expression of his scientific models. For himself, he does not implement process creation, internode cluster communication, or process synchronization. However, the distribution of the neural network on the different cluster nodes is not yet fully automatic and requires some directives of the application developer. This issue in currently under investigation.

Modeling and Simulating a Semiconductor

Fig. 6 is a more complex simulation from semiconductor physics. It shows the result of a simulation of the electrostatic potential in a 2D P-N junction whose N-doped side is the square upper part while the P-doped part is the rest. This computation is done through the sage/escabooz part as described in Fig. 1.

Figure 6: InterCell simulation of a 2D P-N junction

The numerical method is based on a modified version of the Least Squares Finite Element Method (LS-FEM), see [START_REF] Jiang | The Least-squares Finite Element Method: Theory and Applications in Computational Fluid Dynamics and Electromagnetics[END_REF]. From LSFEM, we have derived a "local only" recursive rule. It allows for each point in a mesh to be considered as an independent automaton. This is particularly well suited for fine grained parallel computing. The initial problem is a partial differential system of equations involving a Poisson equation and the field expressions from the doping of the material. Added to this system is a set of boundary conditions: Dirichlet type where ohmic contacts are present, and Neumann type elsewhere.

The complete modeling and development process is thus as follows: the physicist (non-expert in parallelism) programs his equations in the SAGE [START_REF] Stein | Sage Mathematics Software (Version 4.3)[END_REF] language, see Fig. 2, focusing entirely on physical and mathematical issues. Then, the escabooz.sage software suite, formally derives an update rule for each point of a given discretization mesh. Thereby it describes a complete cellular automaton. The SAGE program applies Newton's minimization method to a global error term. This error results from a discretized form of the initial partial differential problem. Following Newton's method, an approximate solution is fed to the automaton. Once run in asynchronous mode, the automaton eventually stabilizes around a fixed point. This is the nearest minimum of the Inria

Modeling and Simulating Cortical Networks

Fig. 7 illustrates a second kind of application of InterCell simulations. In this simulation, we aim at studying the emergent properties of dynamic neural fields, a model of cortical neural tissue [START_REF] Amari | Dynamics of pattern formation in lateral-inhibition type neural fields[END_REF], in particular focusing on sensorimotor control of embedded physical agents (e.g. a robot). The interaction of perceptive, motor and motivational flows of information within the neural network allows the agent to interact on a physical world. The bio-inspired nature of this work requires to simulate large population of neurons that are permanently feeded by a perceptive input and that produce motor actions. To simulate the dynamic neural fields, the continuous equation ( 1) is discretized using the Euler scheme.

τ du dt (x, t) = -u(x, t) + h + y w(x, y)f (u(y, t)) + s(x, t) (1)
where u(x, t) is the membrane potential of the neuron at position x and time t, h is a constant baseline, w(x, y) is the kernel defining the interactions within the neural field and s(x, t) is the input provided at position x and time t. The membrane potential u(x, t) of all the cells evolves according to the same equation and therefore the computations are homogeneous across the cells. Simulating dynamic neural fields is, in this regard, particularly well suited for parallel implementations since a simulation usually involves large populations of finegrained units. InterCell provides essential tools for scaling up models for realistic situations.

The simulation shown in Fig. 7 is a visual search task involving 11 2D dynamic neural fields, each made of 60 × 60 neurons (see [START_REF] Fix | From physiological principles to computational models of the cortex[END_REF] for details). The perceptive input is pre-processed along several dimensions (two colors, two orientations) and feeds a perceptive neural field. Specific connectivities within and between the fields lead to different emergent properties at the level of a neural field such as a competition between potential candidate targets, a working memory of targets that have been analysed or anticipatory mechanisms when camera movements are involved. On the bottom left of Fig. 7 is represented a visualization of the simulation with InterCell tools. The opportunity to visualize the whole network or a part of it is essential for tuning the parameters of the neural fields. In addition, InterCell allows to interact with the simulation online, constantly perturbating the network with a new perceptive input which is critical in the study of sensorimotor control.

The performance measurements provided in Section 5.1 were evaluated on a subpart of the model. This subpart involves three neural fields consisting of an input feeded by five stimuli, a competition neural field and a working memory. The connectivity within this model is rather dense. It contains 10800 neurons with a total of around 30 million connections. InterCell easily handles large networks with dense connections while such a scale-up is hardly handled by a single computer.

The modeling and development process is as follows: the computational neuroscientist (not expert in parallelism) writes done the differential equations governing the evolution of the state of the neurons. This definition is written in C++ with the Bijama library. It involves defining a step method for the units, the connectivity kernel, the parameters of the equation (e.g. h in eq. 1) as well as communication methods that allow to embed the model within the physical environment. Once these methods have been defined, InterCell automatically handles the parallel computations and communications and the situated agent can be controlled by a simulation running on a cluster without taking care of where and how the simulation actually runs.

Experimental performances

Performances of a wave propagation simulation

In Fig. 8 we show the results of a first performance evaluation of the second application of Section 4 on the InterCell cluster, see Fig. 5. This cluster consists of 256 2.66 GHz Xeon bi-core nodes that are connected via standard Gbit Ethernet.

The example application consists of a 100 × 300 grid of cells that is split evenly among the parXXL processes. We experimented several different splitting strategies to find out that (for this example) the difference in performance is negligible. Thus, here we only give the values for a split along the long side (300) of the grid. Thus the grid is divided into 1 × 2 parts, 1 × 3 parts etc, where each part is treated by a separate parXXL process. In one series of experiments we placed one parXXL process per compute node and in a second series we placed two, i.e one parXXL process per compute core.

Each data point in the figures represents an average over several runs of batches of 1000 compute cycles. We have chosen 1000 compute cycles per run, because it leads to execution times of our benchmarks from 5.7s to 45.5s in function of the number of parXXL processes used. These times are all several orders of magnitude greater than the precision of our time measurement tool. We did not observe significant variances of our measurements other than changing the number of process per core or node. So we concluded that the variation that was introduced by the OS or the interconnexion network was negligible. As a consequence, we only performed 3 runs per parameter set to do the averaging.

Plotted are the run times broken down to the time for one compute cycle for the network. Fig. 8(a) shows the time against the number of nodes, Fig. 8(b) the time against the number of parXXL processes. We see that both series show an optimal speedup in the range of 2-8 processes, and up to 16 processes the speedup is still reasonable. From thereon the addition of additional processes / nodes doesn't accelerate the computation. So for the given problem, a number of about 2000 cells per parXXL process is a reasonable minimal requirement. Fig. 8(a) also demonstrates that this setting is well suited to take advantage of the two cores in each node.

Performances of a biologically-inspired neural network

In Fig. 9 we show the results of a first performance evaluation of the biologicallyinspired neural network application introduced in Section 4.3, see the bottom of Fig. 7. Again we used the dual-core nodes InterCell cluster to run our benchmarks, and a similar performance measurement approach. This neural network system is composed of three cortical maps: a medium one and two large ones. Execution attempts on 1 or 2 nodes failed, because of lack of memory. We implemented the medium map on 2 parXXL processes running on 2 CPU cores located on 1 or 2 nodes (dual-core nodes), and we distributed each large map on 1 to 8 processes running on other cores and nodes. We realized two series of benchmarks with 1 and 2 parXXL processes per node. To fulfill the minimum memory requirements of the application, we had to launch at least 4 parXXL processes running on 4 nodes and 6 parXXL process running on 3 nodes, respectively.

We achieved a good scalability distributing the large cortical maps, and a speed up close to 6.8 using 18 = 2 + 2 × 8 nodes in place of 4 = 2 + 2 × 1

Conclusion and perspectives

In this paper we presented InterCell, an open, operational software suite published under the GPL, see http://ims.metz.supelec.fr. This development tool is currently used by researchers in optics, photonics, and cortically-inspired neural networks. The later models are generally large and require interactive execution on large parallel systems. To these researchers, InterCell offers an easy-to-use tool to model and implement on a large, realistic scale. It provides automatic code generation and permits the parallel and interactive control of the simulation. First performance measurements are satisfying and show a good potential to address problems on a larger scale. The next step in the development of InterCell will thus be to tackle applications of a larger scale: complex models are under investigations and large scale simulations are being implemented. Therefore, the Sage program that is currently used to specify the cellular automaton (which is still sequential) has to be parallelized to be able to process large problems rapidly. Also, some serial optimizations remain possible in the parXXL cell management.

Fig. 4

 4 Fig. 4 to 7 show examples of InterCell simulations. Fig. 4 is a classic 2D-Jacobi relaxation, where each cell simply computes the average value of its four neighbors. It has been implemented to test the functionality of our software suite.The application of Fig.5is modeled as a 2D grid of cells, each connected to its 8 neighbors. Here, each cell represents the elongation of a coil spring that is coupled to neighboring springs, in order to create 2D waves along the grid surface. The springs have different elasticity, the "lens" that is visible in light yellow shows the distribution of the elasticity among the springs.The the next sections, give the details of two simulations are real use cases of the InterCell suite, and that correspond to applicative research that was achieved in our laboratories.

Figure 4 :

 4 Figure 4: InterCell simulation of a Jacobi relaxation

Figure 5 :

 5 Figure 5: InterCell simulation of a wave propagation

Figure 7 :

 7 Figure 7: InterCell implementation and run of a biologically-inspired neural network, for environment perception and robot control

InriaInterCell:

  Rapid Prototyping & Parallel Execution of Fine Grained Applications 11 /node parallel, 2 proc/node (b) As a function of the number of run parXXL processes

Figure 8 :

 8 Figure 8: Execution time per compute cycle of the wave propagation simulation

Figure 9 :

 9 Figure 9: Execution time per compute cycle of the biological inspired neural network

Interactive & parallel devoted simulator Cortical neural library escabooz compiler Using a cellular automata implemented in C++/Booz

	computation. This layer allows to dynamically create and connect cells
	Partial Differential Equations to establish cellular networks that are executed cyclically. When created, Cortical inspired neural network each cell is associated to four cell behavior functions: a function that is
	Sage executed in each compute cycle, a query function that can be used to escabooz.sage program PDE solver Bijama library capture the state of the cell, a constructor and a destructor. A network
	of cells can easily be controlled by a sequential program, using missions, cellular automata specification files to create cells, execute one compute cycle, or extract data from the cells.
	Generation of a par::mem: an abstraction layer for handling large chunks of data. These allow cellular automata in C++/Booz for an efficient handling of large tables that are allocated on the heap or
	C++/Booz files inside files and that can be resized dynamically. Technically, such a chunk C++/Booz files may refer to memory on the heap (allocated with malloc), in shared
	parXXL				Booz
	par::cpp parXXL library par::cellnet par::cell par::step par::cntrl par::mem par::sys par::bench	compilation C++	Visualisation Booz client Booz interactive and generic server library	Data sender client Booz Generic and interactive Booz clients Generic and interactive Booz clients Generic and interactive Booz clients
				Interactive
		parXXL runtime	control at runtime
	parXXLrun	Large object (segments
	dynamic runtime support	& files) management
	MPI	Posix threads		Posix mmap
	Execution on	Execution on shared	IO stream
	clusters and Grids	memory mainframes	(camera image, ...)
	Figure 1: Global architecture of our interactive problem modeler and PDE solver
	on large parallel and distributed computers
	✞
	#P o i s s o n ' s e q u a t i o n f o r s e m i c o n d u c t o r d e v i c e s
	eq1 =(lmbda ✯ n l a p ( p h i ( x , y ) , r , dr ) ==
	n i ✯ ( exp ( p h i ( x , y ) ) -exp(-p h i ( x , y ) ) ) -dop ( x , y ) ) . s u b s t i t u t e ( x=0 ,y=0)
	#Newman c o n t i d i o n s on one b o r d e r
	anp=(lmbda ✯nd2 ( p h i ( x , y ) , y , dy ) ==
	n i ✯ ( exp ( p h i ( x , y ) ) -exp(-p h i ( x , y ) ) ) -dop ( x , y ) ) . s u b s t i t u t e ( x=0 ,y=0)
	✝				✆
	Figure 2: SAGE file (extract) specifying the electrostatic potential of a 2D P-N
	junction.
					Inria

segments (allocated through shm open) or in files.

http://ims.metz.supelec.fr/spip.php?rubrique27

http://parxxl.gforge.inria.fr/doxymentation/ RR n➦ 7814

RR n➦ 7814

Inria

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

The authors wish to thank Region Lorraine for its support to the InterCell project in the framework of the 2007-2013 CPER "Modélisations, informations et systèmes numériques (MIS)". Also we want to specially thank Patrick Mercier for his continuous support on the InterCell cluster.

Inria


Keywords:

 and is often used to characterise the whole SBW group. SOUTH BAUCHI EAST 1 -Boghom 2 -Kir 3 -Tala 4 -Guruntum SOUTH BAUCHI WEST

Number in Africa and Beyond: Grammar, Semantics and Social Deixis

27-30 September 2011, Institute for African Studies, University of Cologne 2. Zaar and Gùùs have a very elaborate and profusive TAM system when compared to the other languages.

SBW languages have lost the gender, inclusive/exclusive and dual markers which characterise Afro-Asiatic languages. The remaining singular/plural number opposition is apparent in the paradigms of independent pronouns. From a genetic point of view, Shimizu (op.cit.) has divided these languages into two sub-groups: the North sub-group (Geji and Polci) and the South sub-group (Zeem, Dass and Saya). The same division is observed if we examine the exponents of plurality in SBW languages.

Common SBW does not possess grammatical gender or nominal classes and as a rule, few nouns form a plural (morpho-lexical plural)2 . The plural inside the NP is expressed through the noun modifiers. There is no agreement between the verb and its arguments3 . However, plurality appears in the verb phrase in two places: (i) the formation of the imperatives (ii) a verbal derivation forming what has come to be called, since [START_REF] Newman | Nominal and Verbal Plurality in Chadic[END_REF], 'pluractionals'. The South sub-group (Zeem, Dass, Saya) differs in that it has developed a set of noun plurals through the use of various morphological devices, but most commonly, a -(Vn)sə suffix.

In this paper, we will present first the situation of noun plurals in the northern sub-group (Geji, Polci) which we will then contrast with the situation in the southern sub-group (Zeem, Dass, Saya). Then we will present the situation of verbal plurals. Finally, as a bonus, we will examine the case of number in 2 nd person.

B. MODIFIERS

Plurality is otherwise expressed by the noun modifiers, while the head noun remains invariable. In the nominal system, plurality is marked in the indefinite, in demonstratives, relative pronouns, and in the pronominal system. NB: adjectives have no plural form in these languages. We will show a few examples taken from Zoɗi, a member of the Dass cluster.

INDEFINITE DETERMINER

The indefinite determiner, translated as some/other(s) is ələ m for the singular and ilə m for the plural. kinship terms: ʤ è = grand-fathers ; ʤíː a = grand-children ; áːw = uncles, etc.).

SAYA (ZAAR)

Our survey of the Zaar lexicon has yielded 578 verbs, 52 adjectives, 1479 singular nouns and 50 plural nouns. Regular plurals are formed with the suffix -s 5 , and its variants -ʃi, -tsə, -Vnsə associated to various tone patterns.

B. MODIFIERS

Contrary to the Northern sub-group, the languages of the Southern sub-group vary as regards plural agreement in their determiner, whether indefinite or demonstrative. Let us take our examples from Sigidi and Zaar, two members of the Saya cluster:

INDEFINITE DETERMINER

In Zaar, the indefinite gón does not vary with the number of the head noun it modifies. : za :r gón (a man) ; zàːrsə gón (some people)

In Sigidi, the indefinite determiner (some/other(s))is gón for the singular, gján for the plural: kùn ón / mimíːri ján, 'a boy/some boys'.

DEMONSTRATIVES

The two Zaar demonstratives are: proximal gə n, 'this' and distal íː 'that', used both with the plural and the definite form of the singular: zàrsə gə n/ íː, these/those people zaːr-i gə n/ íː, this/that man.

The two Sigidi demonstratives are: proximal gwíni, 'this' (pl. gíni, 'these') ; distal gwa gə gwi, 'that' (pl. gja gə gi, 'those): zaːr wíni/ wa ə gwi, 'this/that man' ; zàːrsə gíni/gwà gə gwi, (these/those men).

RELATIVE CONSTRUCTION

The relative construction in Zaar uses an invariable relativizer, ɗan, wich does not agree with the pivot noun. Only the resumptive pronoun agrees in number with a [+human] antecedent.

mur-íː

ADJECTIVES

Contrary to what obtains in the Northern sub-group, the adjectives have a singular and a plural form that agrees with the head noun. Morphologically, adjectives are a "nouny" category. They cannot be combined to a negative marker nor to a comparative morpheme. They have a plural and a definite form. When these two affixes are combined, four forms can be obtained. Let's take the adjective 'evil' as an example: lexical definite singular kúsk úːʃi plural u ú u ú ʃi They draw their number feature by agreement with the noun they modify. When they operate as noun modifiers, adjectives can be simply juxtaposed on the left of the noun : <Adj N> or appear on the right and are introduced by genitive link : <N=k Adj>. The GL structure is not used with plural adjectives.

Number in Africa and

III. VERBAL PLURALITY IN SBW

Verb/Subject agreement in SBW languages is limited to the Imperative, with an opposition between singular and plural addressees. Another phenomenon is the presence of a derivation well-known in Chadic languages, producing what has been named 'pluractional verbs' by Paul Newman [START_REF] Newman | Nominal and Verbal Plurality in Chadic[END_REF].

A. THE IMPERATIVE PLURAL

GEJI (GEJI)

The imperative is characterized by a specific tone pattern replacing the lexical tone pattern of the verb: M* for verbs beginning with an initial depressor consonant (D verbs) and HH(M) otherwise (T verbs) 7 . Direct object pronouns and directional adverbial particle (i.e. ka, 'away') are cliticized to the verb, and included in the Imperative tone pattern.

The plural is formed with a -n suffix. An epenthetic /ə/ is added to verbs ending in a final consonant. When the verb finishes in a vowel, the nasal consonant disappears, but the nasal feature remains on the vowel, which results in lengthening and nasalization of the vowel. NB: verbs finishing with /i/ use both forms of the plural: the /i/ is either lengthened or replaced with the -ən suffix.

6 ʧì < tə +yi (be+3SG.AOR).

7 M* = all-mid tones; HH(M) = H on 1 and 2-syllable verbs ; HHM on 3-syllable verbs. See [START_REF] Caron | Depressor Consonants in Geji[END_REF]) for a study of depressor consonants in Geji.

Number in Africa and

POLCI (POLCI)

The situation in Polci is close to that of Geji, with the exception that depressor consonants do not exist in Polci. The tone pattern of the Imperative is H for singular and HL for plural.

ZEEM (CHAARI)

In Chaari, the tone patterns of the Imperative are H for singular and LHL for plural. The plural suffix is -əne.

DASS (ZOƊI)

We have no examples of imperative plurals in Zoɗi.

Number in Africa and

SAYA (SIGIDI)

The form of the Imperative singular is the same as the lexical form of the verbs. The plural is formed with a -(ə)n suffix and HL(L) tones.

SAYA (GUUS)

There are traces of a pluractional derivation through lengthening of the first vowel : In [START_REF] Caron | South-Bauchi West Pronominal and TAM Systems[END_REF] I summarized the situation in the proto-SBW pronominal system in the following table, where no segmental difference is made between singular and plural pronouns: The means developed by the SBW languages to solve the ambiguity between 2sg & 2pl preverbal pronous are quite varied :

1) Baraza & Zoɗi have developed a new set of vowels, resp. kə /kò and ú/kò 2) Langas has used the [+/-voiced] feature to differentiate the singular (kə ) from the plural (gə ) in the 2 nd person only; 3) Other languages have used tone to oppose the singular and the plural: Zakshi opposes High tones for singular to Low tones for plural in the whole paradigm (kə /kə ); Guus does the same with Mid and Low (kə/kə ) ; Zaar Mid and High (kə/kə ). 4) Other languages use a floating tone that attaches to the 1 st syllable of the following verb:

Dir uses this device for all the persons: High for the singular and Low for the plural; Langas combines a High floating tone on the plural 1 st and 2 nd person pronouns with the voice opposition seen above for the 2 nd person; 5) Finally, four languages (Zaranda, Geji, Pelu and Diir) use a suffix that attaches to the 2 nd person plural 10 . This suffix, which is the same as that of the Imperative plural, is the only This suffix which appears here in the 2 nd person plural is a remarkable development in so far as it is the only instance of plural agreement in the verb in SBW languages.

  Beyond: Grammar, Semantics and Social Deixis 27-30 September 2011, Institute for African Studies, University of Cologne

Table 2 . SBW Independent Pronouns

 2

	GEJI			POLCI				ZEEM DASS		SAYA
	Geji Zaranda Pelu Diir	Buli Langas Polci Chaari Baraza Dott Zakshi Sigidi	Zaar
	1s ami ámí:	ami ám	mí	ám	ám	ám	ám	ám ámí	ɲáːni	m y áːni
	2s kí	kí:	kí		ki		kí	kí		kí	kí	k y áːni k y áːni
	3s tí	tí:	tí	yàx	ʧi	yáx	tí	ʧí	yèː		tí	ʧáːni	yáːni
	1p mi	mí:	mi	mì	miː m ː	mì	mèː	m	mà mì	ɲàːné m y àːní
	2p ki	kiní:	ki	n	kiː	n	kì	èː	kò	kò	kì	k y àːné k y àːní
	3p si	sí:	si	wúrí wur wúr	wún ʧèː	èː		ʧì	ʧàːné yàːʃí

  Buk), noun plurals are represented by very few suppletive plurals, generally limited to 'child' and 'woman'. Table1 below lists all the noun plurals found in the sub-group. Zoɗi, although it belongs to the southern sub-group, appears in this summary as it behaves like the northern sub-group of SBW languages.

		singular	plural
	animal	dabbà	dabboːb
	car	móːta	moːtoːʧi

soldiers oːʤoːʤi book tágàrda tàgàrdu Number in Africa and Beyond: Grammar, Semantics and Social Deixis 27-30 September 2011, Institute for African Studies, University of Cologne I. NOUN PLURALS IN THE NORTHERN SUB-GROUP A. NOUN PLURALS Apart from one case of plural formed by suffixation with the suffix -aːsə n (Geji bukaːsə n, 'parent', sg.

Table 3 : Noun Plurals in the Northern SBW sub-group

 3

		child	children	woman	women	thing	things	person	people
	Geji	yén	mîːl	kə li	móːɮì	ili	wúl
	Pelu	yéŋ	miːlí	kə li	móːɮi
	Diir	ɲáː	mímíːri	gerí	myéɬi
	Buli	ʔún	meː
	Langas	leːn	mimer
	Polci	wún	míːr					yàŋ	mbâːm
	Zoɗi	wún	méːr	gət	mə ɬi

Number in Africa and Beyond: Grammar, Semantics and Social Deixis

	3. GENITIVE LINK (GEJI)
	The genitive link (s.) / ʤ (pl.), 'of' is optional and incompatible with [-human] possessors (in
	a broad sense). It appears in the structure <SN1 /ʤ SN2>, <the SN1 of SN2>, where SN2 stands
	for a [+human] possessor . It is sensitive to number, manifesting the number of SN1.
	puka			puka ʤì
	knife	of Audu		knife	of.PL Audu
	Audu's knife.		Audu's knifes.
	The same genitive link manifests itself in possessive pronouns, manifesting the number of the
	possessed:
				Gen. Pro sg.	pl.
				1s
	ɗiː	ma	b n	m	m	ndi
	NEG.PERF	1P	know	thing	some.SG	NEG
	We don't know anything.
	bukáː	mbə rti		ilə m
	after	day		some.PL
	after a few days
	2. DEMONSTRATIVES
	Zoɗi demonstratives are sensitive to number:
				proximal			distal
	Adverbs		woní	here		wéj	there
	Determinants	sg	(ɬáː) oní	this (cow)	(ɬáː) wej	that (cow)
			pl	(ɬáː) ʤoní	these (cows)	(ɬáː) ʤwej	those (cows)
	Pronouns	sg	goní	this one	gwej	that one
			pl	wú ʤoní	these ones	wú ʤwej	those ones
	27-30 September 2011, Institute for African Studies, University of Cologne

gi:ni ʤi:ni 2s gwa: ʤwa: 3s gwa:si ʤwa: i 1p n n ʤin n 2p wa: n ʤwa: n 3p wa: n ʤwa: n

  The relative pronouns are gu for singular and wú ʤu for plural head nouns. Some traces of the suppletive plurals of the north sub-group can be found in the Zeem and Saya clusters of the southern sub-group: However, a much larger group of complex noun plurals 4 have developed in these languages, using suffixation and other morphological devices.Our survey of the Sigidi lexicon has yielded 235 verbs, 15 adjectives, 527 singular nouns and 267 plural nouns. Two classes of plural can be distinguished:Regular plurals use suffixes. The most common is  frequently combined with lengthening of a radical vowel, plus some other morphonological changes (apophony, restitution of etymological consonants, etc.).

					-s pl.suff.	sg.		pl.
					pumpkin	ɓò á	ɓò àː
					cloud	ɓ ːn	ɓ ːn
					groundnut	dàl		dà
					shrew	ʤaːɓa	ʤàːɓàː
					stone	ɗàːj	ɗàː
	4. RELATIVE CONSTRUCTION (ZOƊI)
						apophony sg.	pl.
	toː	séj	kon	wún-i	pi iguana		d	m	gu d èː	a	ndá -ti
	well	then	male	boy-DEF worm do	thing ɓ	REL ɓèː	cont want-VN
	wife Well, then the boy did the thing that he wanted. baboon	d	uːd u áːn
	séj	méː	m ɬ wú ʤu t lizard squirrel	pat ɮàʧ ɓ	ɓ òːn máni ɮ tàːj
	then children girl	REL.PL	3P.AOR bone	take man ɮe a ɮi aːj
	ɗiː		t	do		broom		a vot	ndi vwaːt
	NEG.PERF	3P.AOR	return	3P.ICP
	II. NOUN PLURALS IN THE SOUTHERN SUB-GROUP
	A. NOUN PLURALS
					child	children	woman	women
			Chaari	na ː	mímyéːrə	kə l	mə ɮì
			Guus		ŋǎːŋ	miméːr
			Zaar		ŋáː	məːri

PERF NEG

Then, the girls who had found a husband did not return.

Number in Africa and

Beyond: Grammar, Semantics and Social Deixis 27-30 September 2011, Institute for African Studies, University of Cologne

1. SAYA (SIGIDI)

Nouns finishing in  or  replace these with a -ees suffix:

Other plurals, limited in number, display different types of vowel lengthening and apophony :

áː íː hut b y èːn b y éːnéː old man kwàrí wà ː basket d rʃí d rʃ y èː Two nouns use an -aːsə suffix:

  In Zaar, noun plurals relate to[+animate] terms, e.g. humans and animals. In Sigidi and Chaari, where the number of plurals is proportionally more important than in Zaar, no specific semantic field seems to be predominant, and both animate and inanimate terms have a plural form. This may be due to the fact that the survey of Chaari and Sigidi was done over a couple of weeks, and be used by a speaker. I suspect this was the case during the survey of Sigidi and Chaari, and the lexicon gathered in Zaar has a good chance of reflecting the way the Saya languages work as a whole, from a cognitive point of view.

	The irregularities are proportionally quite numerous:
				sg.	pl.
		woman g t	guɗi
		arrow	pîs	piská
		guest		s m	s md
		sheep		t m	timsá
	As in Sigidi, a good number of family nouns form a pseudo-plural with a -(k)t [-ɣtə] suffix and
	MH tones:
			sg.	pl.
		in-law	ʤìt	ʤiɗ kt
		cousin	úndàː	kundakt
		mother naː	nakt
		sister	waːt	watsakt
		brother jês	jest
	3. CHAARI	-eː pl.suff. locust-bean ɓ ɬ sg.	pl. ɓ ɬ eː
		thorn	ʤ b	ʤ b è :
		leaves	wa ɗ	wà ɗèː
			sg.	pl.
		pot sp.	dàkà	dá áː
		hut	ɗàwkè	ɗàw èː
		dog	kàɗ	káɗíːʃí
		hyena	vúlì	vúl ns
		bone	ɲìs	ɲís ns
		tooth	ʃ y èːn	ʃ y éːn nʃí
		king	l k	l k nʃí
	Final /i/ and /ə/ in the singular exhibit various degrees of apophony:
			sg.	pl.
		water spring àː
			sg.	pl.
		head hen dog pot sp. mouse arm	gàm gèri sg. káɗì ʤá á mbâp táwò	gàm(t)s pl. gers ʤá á áː kaɗa mbapts tàwàː
	chief vulture kwáɗâk 4. SEMANTIC FIELDS OF NOUN PLURALS	u kwaɗaks
		viper	ʤ uː í	ʤi uː ín

5

In the Marti dialect of Zaar, the suffix is -sá, i.e. kansá (from kǎn, uncle), vs kansə in the Ɓogoro dialect.

Number in Africa and

Beyond: Grammar, Semantics and Social Deixis 27-30 September 2011, Institute for African Studies, University of Cologne Our survey of the Chaari lexicon has yielded 190 verbs, 19 adverbs, 25 adjectives, 693 singular nouns and 56 plural nouns. The basic plural suffix is -Vːsə / -Vːʃi /-nsə / -nʃi, combined with various other processes, where V: stands for the lengthening of the final lexical vowel. was strictly morphological, whereas the work on Zaar has been going on for 20 years, and has been more thorough and extensive. During a morphological survey, speakers can produce morphologically sound plurals, by applying processes mechanically, while the resulting plurals Number in Africa and Beyond: Grammar, Semantics and Social Deixis 27-30 September 2011, Institute for African Studies, University of Cologne would hardly

Beyond: Grammar, Semantics and Social Deixis 27

	d ll ʃir	ndu ú	ʃa ndí	lât k muː i
	big stick	short(-legged) pots	new leather
	When they operate as predicates, adjectives use the PTCL.PRED n , and optionally the verb ji,
	'be' :
		modifier	predicate
	singular plural	kúsk zaː an evil man u ú zàrs evil people	D. n úːʃi D. is evil zàrs ʧì 6 n u ú ʃi people are evil

-30 September 2011, Institute for African Studies, University of Cologne

Beyond: Grammar, Semantics and Social Deixis 27

  -30 September 2011, Institute for African Studies, University of CologneThe bare imperative (viz. without an object or a directional adverbial particle) is added a -(n)i suffix:

	bàllì		ballə	ki!		ball-ən	ki 8 !
	turn back	turn_back.IMP.SG	2SG		turn_back-IMP.PL	2PL
			Turn back! (sg.; cf. Fr: Va t'en!)	Turn back! (pl.; cf. Fr: Allez-vous en!)
	Geji		Sg. Imperative	Pl. Imperative
	farm	kól	kólí	kólə nni
	take	ka ː	kámí	kámə nni
	pound	dòp	doɓi	doɓiːni
	stand	ɮə l	ɮəli	ɮələnni
	Exception: a number of monosyllabic verbs ending in a short vowel do not take the -i suffix in
	the singular:
			Geji Imperative	Sg	Pl
			go		su	sú	súːni
			drink		ɬa	ɬá	ɬáːni
			enter		te	té	téːni
			climb		to	tó	tóːni
			emigrate	yo	yó	yóːni
			billow		gù	gu	uːni
			put		zì	zi	zənni

  Plural verbs, also called « pluractionals », mark agreement with a plural subject in case of intransitive verbs, and repeated or distributed action in case of transitive verbs. They are best represented in the Southern sub-group, and more precisely in the Saya sub-branch. In the northern sub-group, only one verb in Geji can be considered to be a pluractional: zine, 'cook', related (?) to zì 'put down'.Two forms of pluractionals exist in Zaːr :-an internal plural through lengthening of the radical vowel, or replacement of this vowel by the vowel /aː/, resulting in a H verb : ʤom / ʤwáːm : 'pile up, gather' (with a plural object) ; kír

	Sigidi Imperatives Sg.	Pl.
	unroll	taː	tâːn
	knead	aː	áː n
	chop	jaːt	jáːt n
	lick	ɓat	ɓát n
	B. PLURAL VERBS ("PLURACTIONALS")
	1. SAYA (ZAAR)
	-an external plural through suffixation of -/ -n. We saw náːt (pl. < nat, 'tie up'), which
	alternates with the form naɗ n (pl. : 'tie up several times, or several things, or several people
	tying up sth.'). We have ɓ t / ɓ ɗ n : 'move along' ; s ː / s ːn ː 'breathe' ; ɬ / ɬ n, 'go' ; wum /
	wum n ː 'feel'.

/ íː , 'run' (with a plural subject) ; nʤol > nʤwáː , 'leave, go' (with a plural subject) ; ɮop / ɮwáːp, 'sting' ; mal / máː , 'get lost' ; nat / náːt, 'tie up' ; dat / dáːt, 'nail' ; ʧim / ʧíːm, 'call' ; k p / k ːp, 'weave, plant' ; m s / m ː , 'die' ; vjer / vjáː , 'insult'

Table 4 . Proto SBW pro.syst.

 4 We can see that a new segmental forms (e.g. a) has emerged in various languages in the 1 st and 3 rd persons to remove the ambiguity. But this segmental ambiguity remains prevalent in all SBW in the 2 nd person, much in the same way as the difference between thou and you has been lost in modern English. However, the SBW languages have found various ways of maintaining the opposition active, as the following table shows for the Aorist/Subjunctive:

	1sg/pl	*n/m
	2sg/pl	*k
	3sg/pl	*t/s

* : ər = [-human] ; jàː =

[+human]

Number in Africa and Beyond: Grammar, Semantics and Social Deixis 27

  -30 September 2011, Institute for African Studies, University of Cologne distinctive mark of plural for Zaranda and Geji, and reinforces the floating Low tone for Diir. Let us see an example of the plural suffix on the 2 nd person plural in the Subjunctive in Pelu: .AOR want 2.SBJV sweep-PL room They want you (pl.) to sweep the room.

	laː	11	poːl hunká.
	3PL.AOR want 2.SBJV sweep room
	They want you (sg.) to sweep the room.
	laː		póːl-n hunká.

3PL

In this presentation, we will ignore the Hausa lexemes borrowed with their original Hausa plural, e.g. in Zaar:

With the exception of the subjunctive. Cf. § V (Post-Scriptum: The 2 nd person Plural in SBW) below.

The complexity of these plurals parallels what is well known for Hausa and other Chadic languages. Cf.[START_REF] Newman | Nominal and Verbal Plurality in Chadic[END_REF].

The verb bàllì (turn back, intr.) is followed by an Intransitive Copy Pronoun. The tonal difference between ki (2sg.) and kî (2pl.) is cancelled by the imperative Mid tone pattern associated with D verbs. This is compensated by the -ən plural suffix.

tə k is analysed as tə+kə = complementizer + Aorist, resulting in a subset of Aorist with a subjunctive meaning.

The presence of nominal and adjectival plurals in the Zeem and Saya clusters seems to be an innovation departing from a situation where plurality is expressed only by the personal pronouns, by the modifiers within the nominal system, and by the imperative 9 . Pluractionals, although they are widespread in many Chadic languages, seem to be an innovation of Zeem and Saya as well. These innovative features may have developed through the influence of plateau languages in the case of Zeem and Saya. The innovation has gone one step further in Zaar proper with the loss of plural agreement on the nominal determiners.