\documentclass[10pt]{llncs}
\usepackage{graphicx}
\newtheorem{de}{Definition}
%\pagestyle{empty}
%\pagestyle{headings}  % switches on printing of running heads
%\markboth{}{}
\title{Local Grammars and Parsing Coordination of Nouns in Serbo-Croatian}
\author{Goran Nenadi\'c\inst{1}}
\date{}
\authorrunning{G. Nenadi\'c}   % abbreviated author list (for running head)
%
\tocauthor{Goran Nenadi\'c (Faculty of Mathematics, University of Belgrade) 
}
%
\institute{
Faculty of Mathematics, University of Belgrade, Yugoslavia\\
\email{goran@matf.bg.ac.yu} %\texttt{}
}

\begin{document}
%-----------------------------------------------------------------------
%-----------------------------------------------------------------------
%-----------------------------------------------------------------------

\maketitle

%-----------------------------------------------------------------------

\begin{abstract}
Parsing coordination units is important as a part of preprocessing 
phase of an NLP tool. In this paper a method for modeling and 
recognition of coordination of some noun phrase classes in Serbo-Croatian 
will be presented. The model is based on local grammars and can be 
applied to a digital text by using an equivalent finite-state transducer. 
Therefore, the implementation of the model is efficient and can be 
embedded as a preprocessor in a system that performs further linguistic 
analysis of a digital text. Beside the recognition of a coordination 
of noun phrases, we discuss possibilities to check some agreements between 
such a unit and other constituents of a sentence.

\end{abstract}
%--------------------------------------------------------------------
		\section{Introduction}
%-----------------------------------------------------------------------

The increasing production of electronically available texts (either 
on the Web or in other machine-readable forms such as digital
libraries and archives) demands appropriate computer tools that
can perform automatic processing of language resources. In the
first place, a natural language processing (NLP) system needs to
implement models for recognition and isolation of various lexical
and syntactical units for further analysis. For example, an information 
extraction system or a Web search engine should implement procedures 
for extraction of strings of words which represent for example
compound names \cite{nlp2000}, terms specific to a certain
domain \cite{boot}, etc. In this paper we will
analyze a method for modeling of some types of coordination of nouns 
and/or noun phrases in Serbo-Croatian, and, additionally, an approach 
to automated recognition of string sequences which represent such units.

Since a coordination of noun phrases (abbr.~CNP) usually plays a role 
of a subject or of an object in a sentence, the problem of recognition 
and parsing coordination units is important as a part of preprocessing
phase of an NLP tool. Using methods and procedures described in 
\cite{fractal,tsd98,nlp2000}, we can recognize some classes of noun 
phrases (NPs) in a digital text, but the aim of this paper is to 
investigate a computational model for combining NPs in a wider syntactical 
unit that is grouped around a specific coordinating conjunction. The problem 
has been studied for both non-inflective (e.g.~English \cite{hh})
and inflective languages (e.g.~Czeck, \cite{petkevic}), although
different approaches were undertaken. 

A CNP can be very complex: such a unit can involve various noun phrases,
prepositional phrases, names of people, companies, places, etc.
Additionally, since Serbo-Croatian is highly inflective, we have to use
computationally effective way for recognition of lexical and syntactical
units on one hand, and---on the other--- we want to base our model on a 
formalism that is "well-adapted to modeling syntax of natural languages" 
\cite{boot}. Therefore, we have based the model on the system of
electronic lexicons (abbr.~{\bf e-lexicon}) containing electronic
dictionaries and local grammars \cite{gross89}.
In order to check some agreements that have to be followed, 
we have used extended regular expressions \cite{tsd98}. 


%-----------------------------------------------------------------------
			\section{Background and Resources}
%-----------------------------------------------------------------------

The model for building a coordination of constituents of various 
types is usually described in detail in traditional grammar books 
\cite{stanojcic}: a coordination consists of two or more comma separated 
units, which are coordinated by a specific relationship marked by 
using appropriate coordination conjunction. The type of the relationship 
determines the set of conjunctions, and vice-versa. However, information
presented in grammar books are incomplete for building corresponding
computational procedure that can recognize a CNP in a unrestricted
digital text. In order to complete the information needed, we have
explored the corpus\footnote{The corpus we have been working with is
a newspaper corpus containing news text taken from a few Yugoslav daily
newspapers presented on the Internet. The bulk of it included text
automatically collected from URLs {\tt http://www.blic.co.yu}
(homepage of daily newspaper "Blic") and {\tt http://www.politika.co.yu}
(homepage of daily newspaper "Politika").},
and this revealed some additional examples of coordination usage.
The model obtained by analyzing both grammar books rules and the corpus, 
was compiled into {\bf local grammars}.

We give a short overview of a notion of local grammar (for details 
see \cite{gross89,boot}): a local grammar is a finite-state 
transducer that recognizes "well formed" word sequences in a digital 
text and chooses the proper tags for them. It describes a set of 
related strings that have similar structures and that can be processed in 
a uniform way. A local grammar does not describe a sentence as a whole; 
however, it defines and applies lexical constraints to a local environment 
containing a sequence of several words. This way, local grammars can be 
used for lemmatization, lexical disambiguation, recognition of syntactic 
units, etc. Some examples of local grammar application in Serbo-Croatian 
are presented in \cite{teza,fractal,tsd98,nlp2000}. For example, the grammar
\verb|<N> <ADJ:g> <N:g>| denotes the set of three-word noun phrases that 
consist of a noun and frozen forms of an adjective and a noun in genitive case. 
This set includes phrases such as 
{\it Fakultet prime\-nje\-nih umetnosti} 'Faculty of Applied Arts', 
{\it Insitut dru\v{s}tvenih nauka} 'Institute of Social Sciences', 
{\it operacija prirodnog spajanja} 'natural join operation', 
{\it jezik visokog nivoa} 'high level language', etc.

Since a local grammar is finite-state transducer, it can be represented 
either by a graph \cite{gross89,maks1} or by a regular expression, and 
is applied to a digital text after the initial tagging. The tagging is 
performed by the system of lexicons which consists of electronic
dictionaries and pre-stored local grammars \cite{gross89,maks1} used
for reducing lexical ambiguities. An {\it electronic dictionary} is
a specific database that models morphological characteristics of
a specified language \cite{gross89,maks1,dusko}. 

These resources are integrated into a corpus processing system INTEX 
\cite{maks1}, which is developed at the LADL (Laboratoire d'Automatique 
Documentaire et Linguisitque), University Paris VII, and is adjusted for 
Serbo-Croatian at the University of Belgrade. 

%-----------------------------------------------------------------------
		\section{Towards a Local Grammar for CNPs}
%-----------------------------------------------------------------------
Traditional grammar books describe several types of coordination
of NPs:
"conjunctive" coordination (marked by conjunctions {\it i, na, niti, pa, te, 
\ldots}),
"disjunctive" coordination (conjunction {\it ili}),
"adversative" coordination (conjunctions {\it a, ali, nego, ve\'c, \ldots}),
"conclusive" coordination (marked by {\sl particles} {\it dakle, 
prema tome, \ldots}), etc.
The full list of {\it coordinators} (i.e.~coordination conjunctions and 
particles) can be obtained from grammar books\footnote{Our list initially 
contained 24 different coordinators.}. Grammar books additionally clearly state 
that---along with coordinators---comma is used as an obligatory separator 
of the constituents whenever there is no coordinator to separate two of them. 
This description, although informative for a native speaker, was not 
enough to construct the structure of a coordination. Therefore, we have
applied an  approach for constructing corresponding local grammars similar 
to those presented in \cite{tsd99} and \cite{nlp2000}, with coordinators 
being {\it keywords}. The initial step was to extract environments of coordinators 
from the part of the corpus\footnote{Since coordinators are not
inflective, we did not have to lemmatize the corpus before extracting
the environments.}, and to tag them using the system of e-lexicons 
(by means of the system INTEX). 

During the next step, we have applied local grammars for NP recognition
on the tagged extracted sequences, and kept only those that represented
"well formed" CNPs.\footnote{Extracted sequences contained coordinating 
sentences (clauses) as well, but they were discarded as we have restricted our 
research on CNPs.} Having isolated different types of CNP, 
corresponding structures were compiled into local grammars for CNP parsing. 
For the sake of obtaining local grammars reasonably complex and readable,
we have clustered the structures into graphs that match the
types of CNPs described in grammar books. However, by examing the corpus,
some unlisted coordinators\footnote{For example, some abbreviated forms of
coordinators (e.g.~{\it al', nit', il'}, etc.) and colloquial forms 
(e.g.~{\it jo\v{s}te},  etc.) were found in the corpus.} 
and additional CNP structures appeared, and were compiled 
into local grammars, as well.

In order to illustrate the results, we will present an example of 
a local grammar for coordinator {\it i} 'and' (Figure 1), and 
a graph that illustrates some specific CNP structures (Figure 2).\footnote{
 The shaded boxes represent other  graphs which describe noun phrases 
(subgraph {\tt $<$NP$>$}) and prepositional phrases (subraph {\tt $<$P-NP$>$}). During the recognition
 process, the graphs are automatically invoked by INTEX.} 
Figure 3 shows the sample of a text tagged using 
the local grammars for CNP parsing. The tags, obtained by means 
of output of the local grammars' transducers, mark CNPs as separate
syntactical units in a SGML-manner.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{fig1.eps}
\\
\centerline{{\bf Figure 1}: A local grammar for CNPs containing coordinator {\it i} 'and'}
\end{figure}   

\vspace*{-3mm}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{fig2.eps}
\\
\centerline{{\bf Figure 2}: A local grammar for CNPs containing various coordinators}
\end{figure}   

The local grammars presented can recognize strings of words that form
"potential" CNPs, as these local grammars do not check the 
agreements that constituents have to follow. First of all, NP constituents 
in a CNP have to agree in case, what can be modeled by extended 
morphosyntactic regular expressions \cite{tsd98}. The general model 
(that is to be specialized for each of the graphs) is:
{\tt
(<NP:{\itshape x}> <sep>)* <NP:{\itshape x}>  COORD\_CONJ  <NP> (<sep> <NP:{\itshape x}>))*
 } 
denoting that a generic case ({\ttfamily{\itshape x}}) has to be minimal 
morpho-syntactic feature that all constituents has to follow. In general, 
these agreements can be checked by procedures\footnote{A
procedure (written using {\tt flex}) is used to check if there exists a
feature that forms the intersection of features of the constituents.} 
described in \cite{tsd98}. On the 
other hand, when a \verb|COORD_CONJ| is combined with a preposition (as 
illustrated by \verb|<NP:gen>| nodes on Figure 2), the corresponding NPs 
have to appear in the fixed case determined by the preposition \cite{tsd99}, 
what can be encoded in a corresponding local grammar.

\vspace*{-1mm}
\begin{center}
\noindent{\footnotesize{\ttfamily
\begin{tabular}{|ll|}\hline
\hspace*{5mm} & \\
& <CNP>\underline{Zatisxje {\bfseries i} mir na Kosovu}<CNP> traju vecy 48 sati, a 
\\
& <CNP>\underline{vojska {\bfseries i} policija}</CNP> su se sa povukle u <CNP>\underline{kasarne {\bfseries i}} 
\\
& \underline{baze}</CNP>. Stanovnisxtvo je, prema oceni predstavnika MUP-a i 
\\
& opsxtinskih vlasti, prepusxteno na <CNP>\underline{milost {\bfseries i} nemilost}</CNP>
\\
& ekstremistima, koji, kako nam rekosxe u ...
\\
&
\\
& saznali smo od <CNP>\underline{profesora {\bfseries i} roditelja}</CNP> koji su takodye ...
\\
& ... jer su profesori iz Beograda pokrivali sve ostale centre u  
\\
& <CNP>\underline{Niksxicyu, Kragujevcu, Nisxu, Banjaluci {\bfseries i} Palama}</CNP>.
\\
& \\
& Ovakav govor silno zagolica <CNP>\underline{Kunigundu {\bfseries i} Kandida}</CNP>. 
\\
& Kako je Kandid bio primoran da se rastavi <CNP>\underline{{\itshape od} lepe Kunigunde} 
\\
& \underline{{\bfseries i} {\itshape od} starice}</CNP>. 
\\

& \\
& U sumraku njene sobe je tvrdio da zna visxe od nje<CNP>\underline{{\itshape o} Klajstu,} 
\\
& \underline{{\bfseries i} Geteu, {\itshape o} SXeliju {\bfseries i} Kitsu}</CNP>. Njega, kome je poverila sve svoje \hspace*{2mm}
\\
&  <CNP>\underline{uspomene {\bfseries i} slutnje, sate {\bfseries i} snove}</CNP>... 
\\
& 
\\ \hline
\end{tabular}
}

\noindent {\bfseries Figure 3}: A sample of a tagged text      
}    
\end{center}
\vspace*{-2mm}
\enlargethispage{\baselineskip}

Beside the case agreement of constituents, we have analyzed the agreement 
between a CNP and corresponding adjectives and/or verb phrases. 
When an adjective or verb is to be "applied" to all constituents of 
a CNP, it is almost always in plural\footnote{In some cases that are
precisely determined by specific compound coordinators (e.g.~{\it kao i}
'like'), the verb can appear in the singular form.}. If all constituents
have the same gender, an adjective or a verb could have the same
(not obligatory); otherwise, the masculine is used regardless of the
gender of constituents (e.g.~{\itshape 'nasi(A:p{\bfseries m})
dragi(A:p{\bfseries m}) dete(N:s{\bfseries n}) i bake(N:p{\bfseries f})'}
'our dear child and grandmothers').
These agreements can be also checked by defining and applying extended 
regular expressions.

%-----------------------------------------------------------------------
	       \section{Conclusion and Further Research}
%-----------------------------------------------------------------------

This paper presents the initial stage of research in modeling
coordination of noun phrases in a highly inflective language such
as Serbo-Croatian.
The method presented can be used for modeling new CNP structures and, 
consequently, for CNP parsing. Local grammars were constructed around 
typical keywords that denote coordinators. Since it is based on local 
grammars i.e.~finite-state tools, the implementation is efficient and 
can be embedded as a preprocessor in a system that performs further 
linguistic analysis of a digital text. 

However, the local grammars presented are by no means complete, although 
they do not make false recognition. By examination of large corpora, local 
grammars can be improved: the percentage of successfully recognized 
coordination of nouns depends on the number of local grammars that are 
defined and applied to a digital text. For further research, we plan to 
enlarge and complete local grammars presented.

Inserts that can occur between constituents of a CNP need to be parsed 
either as special "particles" (the list can be extracted only partially 
from grammar books) or as  embedded sentences.\footnote{Consider examples:
{\itshape Pozvao je Peru, Marka {\bfseries a bogami \v{c}ak} i Milana} 
'He invited Peter, Marko and even Milan as well', or 
{\itshape Pozvao je Peru, Marka, {\bfseries a ju\v{c}e je pozvao \v{c}ak} 
i Milana.} 'He invited Peter, Marko  and yesterday he invited Milan as well'.}
Further research includes parsing these complex inserts. Additionally,
parsing some other types of coordination seems to be very important:
beside coordination of NPs, coordination of adjectives (e.g.~{\itshape
{\bfseries Milanov i Petrov} brat}) and adverbs (e.g.~{\itshape i\v{s}ao
je {\bfseries izmoreno ali sigurno}}) have to be studied as well.


%-----------------------------------------------------------------------
\begin{thebibliography}{99}

\bibitem{gross89}
Gross M., Perrin D. (eds.):
Electronic Dictionaries and Automata in Computational Linguistics, 
Lecture Notes in Computer Science, Berlin, Springer Verlag, 1989

\bibitem{boot}
Gross M.: 
A Bootstrap Method for Construction Local Grammars, 
in Monograph on 125th anniversary of the Faculty of Mathematics, 
University of Belgrade, pp. 231-249, 1998

\bibitem{hh}
Haugeneder H.: 
A Computational Model for Processing Coordinate Structures: 
Parsing Coordination will-out Grammatical Specification,
Proc. of ECAI 92, Vienna, Austria, 1992

\bibitem{teza} 
Nenadi\'c G.: Algorithms for compound word recognition in mathematical 
texts and applications, M.Sc.~thesis, Faculty of Mathematics, University 
of Belgrade, 1997 

\bibitem{fractal}
Nenadi\'c G., Vitas D.: 
Formal Model of Noun Phrases in Serbo-Croatian, 
BULAG 23, Universite Franche-Compte, 1998

\bibitem{tsd98}
Nenadi\'c G., Vitas D.: 
Using Local Grammars for Agreement Modeling in Highly Inflective Languages, 
in Proc.~of First Workshop TSD 98, Brno, 1998

\bibitem{tsd99} 
Nenadi\'c G., Spasi\'c I.: 
The Acquisition of Some Lexical Constraints from Corpora, 
in Text, Speech and Dialogue - TSD '99, 
Lecture Notes in Artificial Intelligence 1692, 
Springer Verlag, 1999

\bibitem{nlp2000} 
Nenadi\'c G, Spasi\'c I: Recognition and Acquisition of Compound 
Names from Corpora, in NLP-2000,  
Lecture Notes in Artificial Intelligence, Berlin,  2000


\bibitem{petkevic}
Petkevi\v{c} V.: Nominal Subject and Verbal Predicate, in 
in Proc.~of Third European Conference on Formal Description of Slavic 
Languages FDSL-3, 1999

\bibitem{maks1}
Silberztein M.: 
Dictionnaries \'electroniques et analyse automatique de textes:
le syst\'eme INTEX,
Masson, Paris, 1993

\bibitem{stanojcic} 
Stanoj\v{c}i\'c \v{Z}., Popovi\'c LJ.:
Gramatika srpskoga jezika, Zavod za ud\v{z}benike i nastavna
sredstva, Beograd, 1994

\bibitem{dusko}
Vitas, D.:
Mathematical Model of Serbo-Croatian Morphology (Nominal Inflection),
PhD thesis, Faculty of Mathematics, University of Belgrade, 1993

\end{thebibliography}

\end{document}
%-----------------------------------------------------------------------
%-----------------------------------------------------------------------
