%Kinyarwanda reduplication
\documentclass[12pt]{article}
\usepackage{ucs} % unicode
\usepackage[utf8x]{inputenc}
\textheight =24cm
\textwidth =16.5cm        
\voffset =-1cm
\hoffset =-1cm
\topmargin=-0.7cm
\lineskip =1.4cm
\topmargin=-0.5cm
\lineskip =1.5cm

\newpage
\parskip =1pt
%\usepackage{amssymb,graphicx,bezier,times}
\usepackage{amssymb,graphicx,bezier,amsfonts}
%\input setbmp
\begin{document}
%\twocolumn
%This is better. The title will still be in 1 column and the the rest including the abstract will be in two columns.
\title{Finite State Solutions For Reduplication In Bantu Languages}
%\author{Jackson Muhirwe \\
%Department of Computer Science,\\
%Faculty of Computing and IT,\\
%Makerere University,\\
%jmuhirwe@cit.mak.ac.ug \and
%Trond Trosterud\\
%Department of Linguistics,\\
%Faculty of the Humanities,\\
%University of Tromsø,\\
%trond.trosterud@hum.uit.no}


%\date{June, 2007}

\maketitle
\begin{abstract}
Reduplication is a kind of sound symbolism that has been noted in many languages of the world. The Bantu languages exhibit all three kinds of reduplication that have been reported in many other languages. There is full word reduplication, full stem reduplication and partial stem or syllable reduplication. Reduplication can also be classified as either bounded or unbounded reduplication. Some solutions have been proposed for bounded reduplication. Some of the proposed solutions use ordered replace rules while others use simultaneous two-level rules. In our attempt to solve both bounded and unbounded reduplication we propose a hybrid approach. This approach has been tested on Kinyarwanda, a prototypical Bantu language. The results indicate that finite state methods are sufficient to handle reduplication.
\end{abstract}

Keywords: Finite, State, Reduplication, Bantu, Kinyarwanda

\section{Introduction}
Reduplication is known to many computational morphologists as the remaining problem. It is a kind of sound symbolism that has been reported in many languages of the world.  Unlike concatenative morphology, which involves concatenation of different components to create a word, reduplication involves copying. Reduplication is therefore non-concatenative, and it involves copying of either the whole word or part of the word. The reduplicated part of the word could be a prefix or part of the stem or even a suffix. This copying is what makes reduplication an outstanding problem. Depending on the language, reduplication may be used to show plurality,iterativity, intensification or completeness (Kimenyi, 2004). Some of the notable examples of reduplication in computational morphology that have been reported include Kinande, Latin, Bambara (Roark and Sproat, 2007); Tagalog and Malay (Beesley and Karttunen, 2003; Antworth, 1990). In these cases, one language may be exhibiting full stem reduplication while another may be exhibiting partial stem reduplication (Syllable).

Reduplication may generally be divided into two: bounded and unbounded. Bounded reduplication is the kind that involves just repeating a given part of the word. This has received some significant attention from researchers. Unbounded reduplication, which involves another affix between the base and the reduplicated part, has received little attention and is yet to be fully solved. In principle, finite state machines are capable of handling bounded reduplication, and here some solutions have been proposed. In this paper we present our attempt to handle both kinds of reduplication in Bantu.

Bantu is the largest group of languages spoken in Sub-Saharan Africa. Its speakers account for about 1/3 of the population of Africa. The languages are agglutinative in nature, with complex, mainly prefixing morphology. Typical verb forms may have slots of up to 20 affixes to be attached to the root on both sides: left and right. Reduplication is a common feature in all the languages and generally all verbs undergo some form of reduplication. Adjectives and adverbs tend to undergo full word reduplication, as we shall see in section 2. In this paper we shall use Kinyarwanda as our example language. Kinyarwanda is a typical Bantu language spoken in the great lakes region of East and central Africa.  Guthrie (1971) classified Kinyarwanda as a group D60 Bantu language (D61), together with Kirundi, Fuliiro, Giha, Vinza, Hangaza and Shubi. It is the mother tongue of about 20 million people. It is a national and official language in Rwanda and Burundi. Other speakers include the Giha (Tanzania), Bafumbira (Uganda), ethnic Banyarwanda in Uganda, Banyamulenge and the ethnic Banyarwanda in Masisi and Rutshuro in the Democratic republic of Congo.

This paper is organised as follows: In the next section we discuss Kinyarwanda reduplication. We present issues that are relevant to our computational analysis. This is followed by our proposed solution to reduplication, in section 3. Section 4 is a presentation of how the proposed approach was applied to Kinyarwanda. We give a detailed practical account of how to use our proposed approach to deal with reduplication. This is followed by a brief evaluation of the presented solution.


\section{Kinyarwanda Reduplication}
Like most other Bantu languages, Kinyarwanda exhibits full word reduplication, full stem reduplication and partial stem reduplication or syllable reduplication. In addition Kinyarwanda also has cases of suffix reduplication attested mainly in verb extensions. Full word, full stem and partial stem are all different forms of bounded reduplication, and will be treated differently in the transducer. Nasal and associative insertions account for unbounded reduplication in Kinyarwanda. For our discussion in this section we shall look at the bounded forms first and then lastly we consider a few cases of unbounded reduplication.

For readers with an orientation towards theoretical linguistics we shall categorise our examples according to whether they are lexical or grammatical, but for implementation purposes this will not be important. Lexical reduplication is concerned with words that may appear in the dictionary. Reduplicated words may appear in a dictionary as distinct words from the original word which underwent reduplication. Grammatical reduplication is concerned with words or sentences that are reduplicated based on grammatical rules. For instance, only monosyllabic verbs are reduplicated, bi-syllabic and polysyllabic are never reduplicated (Kimenyi, 2004). Prefixes and suffixes, which play key roles in Kinyarwanda morphology, are never reduplicated.

\subsection{Full Word Reduplication}

All adjectives, adverbs and numerals may undergo full word reduplication, cf. table \ref{fwraan}.

\begin{table}[htdp]
\caption{Full word reduplication for adjectives, adverbs and numerals}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Adjectives & Adverbs & Numerals \\
\hline
munini "big" $>$ & vuba "fast"   $>$ & vuba "fast"     $>$ \\
muninimunini "big"       & vubavuba "very fast"     & vubavuba    "very fast"\\
muto "small" $>$ & muto "small"  $>$ & buhoro "slowly" $>$ \\
mutomuto ""small /young" & mutomuto ""small /young" & buhorobuhoro "very slowly" \\
mashya "new" $>$ & mashya  "new" $>$ & buke "little"   $>$ \\
mashyamashya "very new"  & mashyamashya "very new"  & bukebuke "very little" \\
\hline
\end{tabular}
\end{center}
\label{fwraan}
\end{table}%


% \textbf{Adjectives}\\
% munini "big" $>$ muninimunini "big"\\
% muto     "small" $>$ mutomuto ""small /young"\\
% mashya  "new" $>$ mashyamashya "very new"\\
% 
% \textbf{Adverbs}\\
% vuba "fast" $>$ vubavuba    "very fast"\\
% buhoro "slowly" $>$ buhorobuhoro "very slowly"\\
% buke "little" $>$ bukebuke     "very little"\\
% 
% \textbf{Numerals}\\
% rimwe `'one' rimwerimwe 'one by one or once in a while' \\
% kabiri 'two' kabirikabiri 'two by two' \\
% gatatu 'three' gatatugatatu 'three by three'

\subsection{Full Stem Reduplication}

This involves reduplication of the whole stem resulting in a new word with a different meaning from its parent. This kind of reduplication has been observed in both verbs and nouns and can be both at lexical and grammatical level. Formally, it differs from word reduplication in that the verb and noun class prefix does not participate in the reduplication, whereas word reduplication reduplicates the class prefix as well, cf. ka-biri=ka-biri vs. gu-taga=taga.

Verbs differ from nouns in that all verbs may be reduplicated. In many cases, the resulting reduplicated verb keeps the same basic meaning, but adds iterativity , continuity, etc. In other cases, the result is a change in meaning. For nouns, the situation is different. Here, reduplication is semantically restricted to meaning "kind of", "associated to", and only a subset of the nouns undergo reduplication.

In our transducer, we open for reduplication for all verbs, whereas reduplicating nouns are singled out as a separate group in the lexicon, cf. \ref{vnredup}.


\begin{table}[htdp]
\caption{Verb and noun reduplication}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Verb Reduplication & Noun reduplication \\
\hline
gutagataga        "to walk like a baby"	  &inkurakura        "kind of bird"\\
gukambakamba      "to crawl"  		  &ikigorigori       "maize stem"\\
kumaramara        "to be embarrassed"		  &amahenehene       "goats milk"\\
kuguyaguya        "to console a sleeping baby"&ipikipiki         "motor cycle"\\
\hline
\end{tabular}
\end{center}
\label{vnredup}
\end{table}%



% \textbf{Verb Reduplication}\\
% gutagataga        "to walk like a baby"\\
% gukambakamba    "to crawl"\\
% kumaramara        "to be embarrassed"\\
% kuguyaguya        "to console a sleeping baby"\\
% 
% In all the above cases we see iterativity, continuity of events or an activity done many times.
% 
% \textbf{Noun reduplication}\\
% inkurakura        "kind of bird"\\
% ikigorigori        "maize stem"\\
% amahenehene        "goats milk"\\
% ipikipiki        "motor cycle"\\

In all the verb cases we see iterativity, continuity of events or an activity done many times. In the noun examples it may be noticed that reduplication refers to the description of an object, to what an object does, or to an association based upon the original meaning.

\subsubsection{Grammatical Reduplication}

This involves reduplication of existing word forms, thereby forming new words with different meanings. Grammatical reduplication may be realized at word level or at sentence level. Here we shall consider reduplication at word level only; sentence level processes are outside the scope of a morphological transducer. The reader is advised to consult Kimenyi (1986) for sentence level reduplication.

Also in this category it is the whole stem that is reduplicated. Most of the examples belonging to this category are of verb reduplication.

Examples include the following:\\
kugenda "to walk"  $>$ kugendagenda    "to walk around"\\
kubunda "to bend" $>$ kubundabunda    "to walk bending"\\
kubumba "to mould" $>$ kubumbabumba "to continue moulding"\\
guhonda "to knock" $>$ guhondahonda    "to knock repeatedly"\\

Notice from the examples above that this type of reduplication is limited to two-syllable stems, and most of these verbs end with a nasal cluster $NC$. Two syllable verbs referring to continuous events are never grammatically reduplicated, e.g gukunda "to love", kwanga "to hate" guhinga "to cultivate". They may undergo lexical reduplication, though. So, in an analysis invoking semantic disambiguation, trisyllabic reduplicated verbs will be discarded as candidates for grammatical reduplications.

\subsection{Partial Stem Reduplication}

In this case the initial reduplicated syllable has the form $CV$, $VC$ or $CVN$. Cf. table \ref{NV}\\

\begin{table}[htdp]
\caption{Partial reduplication of nouns and verb}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Verbs & Nouns \\
\hline
kujejeta    "to drop /leak" & iseseme    "nausea"\\
gusesera    "to go through a fence with a bent back" & ingegera   "crook"\\
kubabara    "to fill pain" & umururumba "greed"\\
kunyunyuza  "to suck" & ibijojoba  "rain drops"\\
\hline
\end{tabular}
\end{center}
\label{NV}
\end{table}%

% \textbf{Verbs}\\
% kujejeta    "to drop /leak"\\
% gusesera    "to go through a fence with a bent back"\\
% kubabara    "to fill pain"\\
% kunyunyuza    "to suck"\\
% 
% \textbf{Nouns}\\
% iseseme    "nausea"\\
% ingegera    "crook"\\
% umururumba    "greed"\\
% ibijojoba    "rain drops"\\



\subsection{Unbounded Reduplication}

This is still a challenge, and it involves two cases in Kinyarwanda, nasal insertion and the insertion of the associative between the reduplicates.

\subsubsection{Nasal Insertion}

These cases may be few but they do exist. The majority of the cases are verbs. Few nouns exhibit this kind of behaviour, \ref{nasvn}.

\begin{table}[htdp]
\caption{Nasal insertion in verbs and nouns}
\begin{center}
\begin{tabular}{|l|l|}
\hline
Verbs & Nouns \\
\hline
gutontoma "to make pig's noise" & igipampara    "a useless thing" \\
kuvumvura "to talk (insulting)"\\
gutantamura "to tear up"\\
\hline
\end{tabular}
\end{center}
\label{nasvn}
\end{table}%

% \textbf{Verbs}\\
% gutontoma    "to make pig's noise"\\
% kuvumvura    "to talk (insulting)"\\
% gutantamura    "to tear up"\\
% 
% \textbf{Nouns}\\
% igipampara    "a useless thing"


\subsubsection{Associative insertion}

Associative insertion has mainly been observed in demonstratives when they reduplicate. An associative infix such as na "and" is inserted between the reduplicates.

\textbf{Demonstratives}\\
uyunguyu "this one", abangaba "these ones"\\
ahangaha "Here", ahanaha "such and such a place" ikiniki  "this and this one

\section{The proposed approach}

In order to handle the different issues presented above we used a hybrid approach. The hybrid approach is a combination of two-level rules and replace rules. These two formalisms represent the state of the art and practice in computational morphology. The two formalisms are powerful, well designed and well understood.

\subsection{Two-level Formalism}

The two-level formalism has been the dominant formalism in Computational Morphology since its invention by Koskenniemi in 1983 (Koskenniemi, 1983). Since then the approach has been used to develop morphological analysers for very many languages around the world, including the Bantu language Swahili (Hurskainen, 1992). This formalism has been the major motivation force behind renewed interests in computational morphology since 1983. The two-level formalism is based on two-level rules which are applied to a lexicon to facilitate lexical to surface level mappings. The two-level rules are compiled either by hand (Antworth, 1990) or by machine (Karttunen, 1992) into finite state networks. The rule network may now be applied to a lexicon that has been compiled into a finite state network. A two-level based morphological analyser is developed by composing the two-level rule network with the lower side of the finite state lexicon network. The two-level rules are symbol to symbol rules which apply to the lexicon in parallel. The developer does not have to worry about the order of the rules. The only problem is that rules tend to conflict. With computerised compilers, such conflicts are no longer a problem. The compiler shows which rules are conflicting, so that the developer can resolve them. The output from a two-level morphological analyser is never affected by the order of the rules.

Two-level rules are generally of the form\\
CP OP LC \_ RC\\
where $CP$ = Correspondence Part;  $OP$ = Operator; $LC$ = Left Context; $RC$ = Right Context\\

There are four different kinds of rules that may be used to describe morphological alternations of any language.

\begin{enumerate}
\item    a:b =$>$ LC \_ RC. This rule states that lexical //a// can be realized as surface b ONLY in the given context. This rule is a context restriction rule
\item    a:b $<$= LC \_ RC This rule states that lexical //a// has to be realized as surface b ALWAYS in the given context. This rule is a surface coercion rule.
\item    a:b $<$=$>$ LC \_ RC this is a composite rule which states that lexical //a// is realized as surface be ALWAYS and ONLY in the given context.
\item    a:b /$<$= LC \_ RC This is an exclusion rule that states that lexical //a// is never realized as surface //b// in the given context.
\end{enumerate}

These rules may be compiled into finite state acceptors either by hand or automatically using one of the available Two-level rule compilers. For the purpose of this research we used the Xerox Finite State Tools.

\subsection{Replace Rules}

On the other hand the replace rules were introduced by Karttunen in 1995 motivated by the rewrite rules model developed by Kay and Kaplan (1994). The replace rules are regular expressions that make it possible to map the lexical level strings to surface level strings. Replace rules have been very popular in Computational Morphology and have been used to develop many morphological analysers.

Replace rules are compiled into a finite state network and this network is applied to the lower side of the lexicon network to map the lower level strings to the surface level strings. It is worthy noting that replace rules are feeding rules and therefore apply in a cascade. Each rule uses the result of the preceding rule. Because of this, a linguist writing language grammar using replace rules notation must order rules in a proper way, otherwise the results may not be right.

Replace rules have one clear advantage over two-level rules. They can map symbols to symbols; symbols to strings; strings to symbols; and strings to strings. Replace rules are very handy when it comes to writing string to string mappings. In this case you write only one rule instead of the many rules you would otherwise have to write while using two-level rules. Replace rules take the following four forms:


Unconditional replacement
\begin{verbatim}
A -> B
\end{verbatim}

Unconditional parallel replacement (Several rules with no contexts)
\begin{verbatim}
A1 -> B1, A2 -> B2, ...... An -> Bn
\end{verbatim}
Conditional replacement. (One rule with contexts)
\begin{verbatim}
UPPER -> LOWER || LEFT _ RIGHT
\end{verbatim}

Conditional parallel replacement.
\begin{verbatim}
UPPER1 -> LOWER1 ||
LEFT1 _ RIGHT1 ,,  UPPER2 -> LOWER2 || LEFT2 _ RIGHT2,,..,,UPPERn -> LOWERn ||
LEFTn _ RIGHTn
\end{verbatim}
\subsection{Comparison of the two Formalisms}
\begin{itemize}
\item Replace rules are organised vertically in a cascade and feed each other. Two-level rules, on the other hand side, are organised horizontally and apply in parallel.
\item Because replace rules are feeding rules, they must be properly ordered. Order is not important in two-level rules and would not affect the output.
\item Replace rules conceptually produce many intermediate levels when mapping from lexical to surface level.
\item Since two-level rules apply simultaneously, there is no ordering problem. The only problem that arises are conflicts that the linguist must deal with. But as we said earlier, this is no longer a problem since current two-level compilers can detect the rule conflicts and then the grammar writer can deal with them accordingly.
\end{itemize}
\subsection{Towards a Hybrid Approach}
As much as we have seen that these two formalisms have differences, they all work very well and are efficient at doing what they were designed to do. They have the same mathematical properties, and none of the formalisms can be claimed to be superior over the other, per se.
It is further claimed that choosing between two-level rules and replace rules is just a matter of personal choice. This is true as far the general areas of application of each of these rules are concerned. Our experience has shown that two-level rules are much easier to learn and conceive how they work. This experience is also shared by Trosterud and Uibo who also while working on Sami found it much easier to learn two-level rules but again proposed that it would be possible to combine both formalisms (Trosterud and Uibo, 2005). We found it easy to learn two-level rules and we used them to develop our Kinyarwanda Noun morphological analyser(Muhirwe and Barya, 2007). We later redesigned the system using the replace rules as part of the hybrid approach to the morphological analysis of the Kinyarwanda morphology. Beesley and Karttunen also realised that each one of these rules has strong points and week points. There are incidences where it is much easier to use two-level rules and there are other incidences where it is easier to use replace rules over two-level rules (Beesley and Karttunen, 2003).
Let us look at an example to strengthen our argument. In solving limited partial stem reduplication in Tagalog, Antworth used two level rules to model the solution. This same example was repeated by Beesley and Karttunen (2003). Efforts to rewrite the solution using replace rules resulted in many rules. We used this approach to solve the problem of partial reduplication in Kinyarwanda.

\begin{verbatim}
Alphabet %+:0 b c d f g h j k l m n p q r s t v x y z a e i o u;
Sets
C = b c d f g h j k l m n p q r s t v x y z;
V = a i e o u á é í ó ú ;

Rules
"R for realisation as Consonant"
R:CC <=> _ E: %+: CC;    where CC in C;

"E realisation as vowel"
E:VV <=> _ %+: (C:) VV;    where VV in V;
\end{verbatim}

Now compare this with the replace rules solution.
\begin{verbatim}
define Vow [ a | i | e | o | u | á | í | é | ó | ú ] ;
define Cns [ b | c | d | g | h | j | k | l | m | n | p | q | r | s
           | t | v | w | y | z ];

define RedupRules R -> b || _ E %+ b
.o. R -> c || _ E %+ c
.o. R -> d || _ E %+ d
.o. ...
Add the other consonants as well

Lastly add the vowels correspondences
    E -> a || _ %+ (Cns) a
.o. E -> e || _ %+ (Cns) e
.o. %+ -> 0 ;
\end{verbatim}

Add as many vowels as you have for your language. For Kinyarwanda we have to include even the accented versions of the vowels shown above.

We can see that in this situation, the replace rules are inferior to two-level rules. Generally we can say that depending on the application, one approach may have an advantage over the other. Replace rules have an edge over two-level rules when it comes to string to string mapping. When the strings are of unknown length, two-level rules cannot be applied, and we will have to use special compilation routines from the xfst toolbox. In other words, replace rules are more appropriate if the mapping requires replacement of a string, whereas two-level rules are more appropriate when only symbols are involved, and especially when sets of symbols are involved. Based on this we decided to combine the two approaches to take advantage of each formalism's strength.


\section{Implementation}

At the outset, we wanted to solve three problems: Full wordform reduplication (we will follow established practice and refer to it as word reduplication), stem reduplication and first syllable or partial stem reduplication. Our hybrid approach was used as follows. We used the two-level rules to solve the problem they are best at solving: partial stem reduplications. Beesley and Karttunen's compile-replace algorithm was then used to handle full word and full stem reduplication.

\subsection{Full word and full stem Reduplication}
The full word and full stem reduplication was handled by use of the replace rules and the compile-replace algorithm. The compile-replace algorithm is based on the insight that any string $S$ can be reduplicated using regular expressions of the form  \{S\}\textasciicircum2.  The central idea behind the application of the compile-replace algorithm therefore is looking for a way to enclose the stem with the delimiters \{ and \}\textasciicircum2. This was done by enclosing the whole stem with \textasciicircum[\{S\}\textasciicircum2\textasciicircum] in the lexicon, and given a reduplication context, the compile-replace algorithm is applied to the lower side of the lexicon network, doubling the stem. When the reduplication context is not present, the delimiters were simply deleted. As an example, take a look at part of thelexc lexicon below:

\begin{verbatim}
LEXICON Root
0:^[{    AdjRoots;
0:^[{    AdvRoots;
\end{verbatim}

This continues to the adverb and adjective or to any other sublexicon
\begin{verbatim}
LEXICON AdjRoots
kinini    AdjSuff;
kito      AdjSuff;
muto      AdjSuff;
\end{verbatim}

Lastly we can add the suffix
\begin{verbatim}
LEXICON    AdjSuff
+Adjective:0    Redupli;

LEXICON    Redupli
+Reduplic:}^2^]    #;
%+unmarked:0       #;
\end{verbatim}

After compiling the lexicon and applying the compile-replace algorithm to the lower side, the alternation rules can then be applied to constrain the surface realisation of the reduplicated words. In this case most of the surface alternation rules were written using replace rules formalism.
\subsection{Partial stem reduplication}
The solution provided by Antworth in PC Kimmo is a good solution to handling limited length reduplication. We therefore adapted this solution to provide a solution to first syllable reduplication in Kinyarwanda. The rules we used were presented in the previous section. We used the two-level rules because of their convenience, but, as noted, one will get the same result by using replace rules. These two-level rules were compiled into a finite state network and then intersected using the two-level compiler \textit{twolc}. The rule network was then applied to the lower side of the lexicon network to produce the required output on the surface. In the lexicon we had to include a feature that would interact with the rules to cause reduplication:
\begin{verbatim}
Lexicon PSPrefix
[Redupli]:RE+  PVRoot;
Lexicon PVRoot
jeta    VFinal;
\end{verbatim}
In Kinyarwanda, the partial stem reduplication is of three types, $CV$, $VC$ and $CVN$ reduplication. We thus made three different templates, all modeled upon the rule shown here.
\subsection{Unbounded reduplication}
The solution provided above for partial reduplication seemed to work very well until we tested the results, and then we found that there were some interesting challenges.
\begin{enumerate}
\item some stems reduplicate and cause insertion of a nasal. For example
/gu + kama/     $>$ /gukankama/ \\
/gu + toma/     $>$ / gutontoma/
\item there were cases of complex consonants which when present makes the reduplication problem harder. Antworth's solution was for fixed length CV reduplicates and it is in this case rendered inefficient. Examples
/gucyocyora/ \\
/kunyunyuza/ \\
/gushwashwanya/
\item when demonstratives reduplication, a presentative affix /nga/ is inserted in the middle of the reduplicates
\end{enumerate}
In order to solve the first challenge, we carried out more negative tests and looked for cases of words that were not recognized. Of these we identified reduplicates where a nasal is inserted and we found that such cases are not very frequent. The majority of verbs and nouns undergo full stem reduplication, for which the provided solution was adequate. The remaining few undergo partial stem or first syllable reduplication. There are also cases of stems that undergo both full stem and partial stem reduplication, but these were not a challenge at all.
So our solution to the nasal insertion challenge was to write a rule that would insert a nasal between the reduplicating prefix and the base stem.
\begin{verbatim}
[] -> n || _ [ [t o m a] | [k a m a] | ....| [v u r a]]
\end{verbatim}

The second problem involving complex consonants was solved by representing each complex by a multicharacter symbol that is not used in the lexicon. For example, in /kunyunyuza/ there is a complex consonant $ny$ which is part of the reduplicate. We represent all occurrences of $ny$ with N and the following rule will be applied lastly to effect the surface realisation.
\begin{verbatim}
N -> ny
\end{verbatim}
The third problem was solved by using replace rules. The problem of reduplication of demonstratives was partly solved by application of the compile-replace algorithm and replace rules. We used a replace rule to insert /nga/ in all the reduplicated demonstratives.
\begin{verbatim}
[] -> [ n g a ] || _ demo .#.
\end{verbatim}

\subsection{Evaluation and tests}
The partial, full stem and full word reduplication lexica were compiled and composed together in a finite state network. We applied the network of all the rules described above for all the different issues to the lower side of the lexicon network. We then carried out tests for both analysis and generation. We did both negative testing and positive testing. Positive involved testing the system on the words that were part of the lexicon. These we found were all correctly analysed. Below are some of the results:
\begin{verbatim}
apply up> ikigorigori
iki[CL7-SG]gori[stem_redupli][noun]
apply up> kugendagenda
ku[Inf]genda[stem_redupli][verb]
Demonstratives with nga insertion
aka[DEM-12][dem_redupli][Demonstrative]
akongako
ako[DEM-12][dem_redupli][Demonstrative]
Nasal insertion
gutontoma
ku[Inf][Redupli]toma[verb]
Complex consonants
kunyunyuza
ku[Inf][Redupli]Nuza[verb]
Full stem reduplication
gusomasoma
ku[Inf]soma[stem_redupli][verb]
Full word reduplication
muninimunini
munini+Adjective+Reduplic
\end{verbatim}

Negative testing involved selecting words from our untagged corpus of Kinyarwanda. Since these words were not part of the lexicon, they were not recognized and were then duly added to the lexicon. Adding a new word to the lexicon is very easy since it only involves identifying the reduplicating part of the word and it is then added to the appropriate sub-lexicon. This testing will be continued as we discover new reduplicated words.

The tests indicated above were manual tests. We created another test set to be carried out automatically. In this case we created a test file with about 100 known reduplicated forms of different word categories in Kinyarwanda. The results indicated that the earlier problems due to unbounded reduplication: complex consonants, insertion of nasals and the prefix /nga/ have now been fully solved.

\section{Conclusion}
The solutions provided in this paper have demonstrated that finite state technology is sufficient to handle all forms of reduplication. The hybrid approach proposed in this paper makes it easy to handle all forms of reduplication problems attested in the Bantu languages. Judging from the reduplication problems reported about in the literature, we can say that these solutions would effectively solve all forms of reduplication. This approach could also be used with other problems in morphological analysis.  The finite state developer can solve morphological problems using the most appropriate approach depending on whether what is being replaced is a symbol or a string. A developer adopting this approach has to be careful with the ordering of the networks on the stack.
\section *{References}
\begin{enumerate}
\bibitem{Antworth90}Antworth, Evan L. 1990. PC-KIMMO: a two-level processor for morphological
analysis. No. 16 in Occasional publications in academic computing. Dallas:
Summer Institute of Linguistics.
\bibitem{BeesleyandKarttunen03} Beesley, K. AND Karttunen Lauri. (2003). Finite State Morphology: CSLI Studies in Computational Linguistics. Stanford University, CA: CSLI Publications.
%\bibitem{Goldsmith76} Goldsmith, John. 1976. Autosegmental phonology. PhD dissertation, MIT, Cambridge, Massachusetts.
\bibitem{Guthrie71}Guthrie, M. 1971. Comparative Bantu. Vol. I-IV. Farnborough: Gregg International.
\bibitem{Hurskainen92} Hurskainen, A. (1992). A two-level computer formalism for the analysis of Bantu Morphology an application to Swahili Nordic journal of African studies 1(1): 87-119 (1992)
\bibitem{Karttunen92} Karttunen, L., Kaplan, R., and Zaenen, A., (1992). Two-level morphology with composition. Xerox Palo Alto Research Center - Center for the Study of Language and Information. Stanford University.
\bibitem{Karttunen95} Karttunen, L, (1995) The replace Operator. Proceedings of ACL-95, pp 16-23, Boston Massachusetts.
%\bibitem{Karttunen05} Karttunen, L., (2005). Twenty-five years of finite-state morphology available online\\ www2.parc.com/istl/members/karttune/publications/25years.pdf
\bibitem{Kay94} Kay, M., Kaplan, R., Regular Models of Phonological rule systems Computational Linguistics, Special issue on Computational phonology, pg 331-378
%\bibitem{Kimenyi80}Kimenyi, A.(1980) A Relational Grammar of Kinyarwanda. Berkeley and Los Angeles. University of California Press.
\bibitem{Kimenyi86} Kimenyi, A. (1986) Syntax and semantics of reduplication: A semiotic account La Linguistique, Vol 22 Fasc 2/1986
%\bibitem{Kimenyi02}Kimenyi, A. (2002) A tonal Grammar of Kinyarwanda An Autosegmental and Metrical Analysis.The Edwin Mellen Press Ltd.
\bibitem{Kimenyi04}Kimenyi, A. (2004) Kinyarwanda morphology, In the International Handbook for inflection and word formation vol2.
\bibitem{Kimmo83a} Koskenniemi, K. (1983). Two-level morphology: a general computational model for word-form recognition and production. Publication No. 11. University of Helsinki: Department of General Linguistics.
%\bibitem{Muhirwe07a} Muhirwe, J. and V. Baryamureeba (2007) Towards Computational Morphological Analysis for Kinyarwanda. Proceedings of the 1st International conference on Computer science and informatics,Feb 2007, Nairobi, Kenya.
\bibitem{Muhirwe07b} Muhirwe, J. (2007) Towards a two-level morphological analysis of Kinyarwanda nouns. Paper read at the 37th Annual conference of African linguistics, March 2007 Florida, USA.
\bibitem{Roark07} Roark, B and Sproat, R. 2007. Computational Approaches to Morphology and Syntax. Oxford University Press, in press.
%\bibitem{Sproat92}Sproat, R.(1992). Computation and Morphology MIT press
\bibitem{Trond05} Trosterud, T and Uibo, H. (2005). Consonant gradation in Estonian and Sámi: two-level solution In: Inquiries into Words, Constraints and Contexts. Festschrift in the Honour of Kimmo Koskenniemi 60th anniversary. CSLI Publications 2005.

\end{enumerate}
% Set the ending of a LaTeX document
\end{document}


