\documentclass{llncs}
\usepackage{makeidx}  % allows for indexgeneration
%
\begin{document}
\pagestyle{empty}
%
\input{psfig.sty}
%
\mainmatter
%
\title{Selected Types of Pg-Ambiguity;\\
Processing Based on Analysis by Reduction}
\author{Mark\'eta Stra\v{n}\'akov\'a}
\institute{Faculty of Mathematics and Physics, Charles University,
Prague, Czech Republic\\
\email{marketa.stranakova@ufal.mff.cuni.cz}} \maketitle
%
\begin{abstract}
A need for the detection of ambiguous prepositional groups (Pg's)
is discussed in the paper. Criteria for automatic
Pg-disambiguation are presented, with special accent on word
order patterns and verbonominal collocations, the main source of
non-projective constructions caused by non-congruent Pg-modifiers
of nouns. Usefulness of the proposed criteria and their ordering
within an analysis by reduction is introduced.
\end{abstract}
%
\section{Description of the Problem}
%
Based on the stratificational, dependency-oriented Functional
Generative Description of Czech (FGD), four types of ambiguity
can be distinguished according to the level of language
description containing units which introduce the possibility of
two (or more) readings of the sentence.

With prepositional groups (Pg's), the ambiguity defined as an
asymmetric relation between the level of surface structure and
the adjacent morphemic level is frequent, i.e. the situation when
two or more possible functions on the level of the surface
representation of the sentence are expressed by the same
morphemic form (cf. morphemic ambiguity in the terms defined in
[4]). In phrase structure oriented formalisms the corresponding
problem is known as PP-attachment, see [1].

From a strictly syntactic point of view a Pg can modify (depend
on) a verb, a noun  or an adjective (typically deverbal) in the
sentence, as in the following example.
%
\paragraph{Example (1):} {\it V obdob\'{\i}, kdy prudce poklesl z\'ajem
na dom\'ac\'{\i}m trhu, dok\'azala tov\'arna \v{c}\'ast v\'yroby
exportovat.} (PDT, bmd03zua.fs $\sharp$4, shortened)
\\
$[$at - time - when - sharply - fell - demand - on - domestic -
market - managed - factory - part - (of) production - (to)
export$]$
\\
(At the time when the demand on the domestic market sharply fell,
the factory managed to export part of its production.)
\\
Analyzing the Pg {\it na dom\'ac\'{\i}m trhu} [on (the) domestic
market], the valency frame of the noun {\it z\'ajem} [demand] is
important.

{\it z\'ajem} \dots \  Act (Gen/Adj$_{pos}$) Pat ({\it
na}+Loc/{\it o}+Acc)
\\
Thus, the Pg {\it na dom\'ac\'{\i}m trhu} [on (the) domestic
market] can be treated either (a) as a free modifier (Locative)
belonging to the verb {\it poklesnout} [to fall], or \\(b) as an
attribute of the noun {\it z\'ajem} [demand] - either as (ba) a
valency modifier (Patient) or (bb) a free modifier (Locative).
(The valency slot of Pat with {\it z\'ajem} [demand] is occupied
by a General Participant in cases (a) and (bb).)

In general a sentence with a Pg that can be analyzed as a
modifier belonging to any of two (or more) distinct sentence
members can have two (or even more) different meanings (as in (a)
and (ba)) - hence the need for criteria that allow for the
detection of occurrences of ambiguous Pg's.

The appropriate (human) analysis of a sentence is based on a wide
range of syntactic, but also semantic and even pragmatic
knowledge. We try to detect the types of input information the
automatic procedure can take into account and to determine the
criteria both for the detection of Pg-ambiguity and for
Pg-disambiguation.

Prague Dependency Treebank (PDT) serves as a basic source of data
for Czech.
%
\section{Proposal of the Criteria}
%
We presuppose the existence of a lexicon with detailed
information containing complete valency frames for verbs, nouns
and also adjectives. The verbonominal collocations must be also
kept in the lexicon with their valencies. Optionally, the
semantic features of nouns and verbs can be used if they are
available. The procedure proposed operates on data provided by
full morphological analysis.
%
\subsection{Word Order Patterns (WOP's)}
\label{sect:word}
%
The surface word order serves as the basic purely grammatical clue
to the Pg-ambiguity detection. Typically, Pg satisfies word order
constraints, which have been embodied in WOP's.
%
\begin{description}
\item[Basic unambiguous WOP's.] \
\\
- V immediately followed by Pg (such V is the Pg governor);
\\
- Pg at the very beginning of a clause (V is the prototypical Pg
governor);
\\
- Adj and Pg are separated by any verb form (V is the Pg
governor).
\\
These WOP's are relevant for Pg's in prototypical positions. The
analysis of prolific non-projective constructions caused by
non-congruent Pg-modifier of noun is discussed in the subsection
2.2.
  \item[Basic suspicious WOP's.] \
\\
- a sequence of N's at the beginning of a clause followed by Pg;
\\
- a sequence of V, N and Pg (in this order);
\\
- Pg between N and V (from the left to the right);
\\
- Pg between V and Adj (V - Pg - Adj - N) or Pg being followed by
an adjective, a noun and a verb (in this order) (Pg - Adj - N -
V).
\\
There can be strings of nouns instead of a single N in all of
these word order patterns (all of them either without a
preposition or in a prepositional case).
  \item[WOP's with a preferable reading.]\
\\
- N being followed by a congruent Adj and Pg (in this order) (then
Pg is preferably treated as belonging to such Adj);
\\
- Pg between N and a congruent Adj (then Pg is preferably treated
as belonging to such Adj).
\\
There are some regular exceptions to these rules, as the specific
contrastive position of Adj or collocations characteristic for
scientific terminology.
\end{description}
%
%
\subsection{Verbonominal Collocations}
\label{sect:verb}
%
A verbonominal collocation can be described as a collocation of a
noun and a verb (often with very general meaning) where the noun
part has a valency slot filled in by Pg. With verbonominal
collocations, the word order constraints may be violated and thus
the WOP's defined in subsection 2.1 cannot be taken into account.

Two types of verbonominal collocations can be distinguished; both
of them must be kept in the lexicon (among the entries of the
noun item).
\\
- A verbonominal collocation consists of a verb with very general
meaning and of a noun with valency requirements (type (1), {\it
m\'{\i}t \v{s}anci/pen\'{\i}ze na co} [to have a chance/money for
st.], {\it podat st\'{\i}\v{z}nost na koho/co} [to submit (a)
complain of sb./st.]).
\\
- Both a noun and a verb constituting a verbonominal collocation
have valency slots requiring the examined Pg (type (2), {\it
kl\'ast n\'aroky na koho/co} [to make demands on sb./st.]).

From the purely syntactic point of view there are two systematic
possibilities how to analyze such collocations - the Pg can be
treated either as an attributive nominal modifier or/and as a
verbal modifier, which either is registered in a valency frame, or
is its optional free modifier. In agreement with the valency
requirements, we propose the following solution.
%
\begin{description}
  \item[Solution.] Concerning Pg-disambiguation two issues must be solved:
\\
- If only the nominal part of the verbonominal collocation has a
valency slot requiring the examined Pg (type (1)) then the Pg is
analyzed as an adnominal modifier (in agreement with the valency
requirements of the noun). The word order constraints must be
relaxed, non-projective constructions may arise (see below).
\\
- For type (2), where both the name and the verb constituting the
verbonominal collocation require valency Pg-modifier, WOP's are
applied. Two structures are preserved whenever it is possible
(the one treating Pg as an adnominal modifier and the other with
Pg as a verbal modifier).
\end{description}
%
\paragraph{Example (2):} {\it Finan\v{c}n\'{\i} prost\v{r}edky na n\'akup
technick\'eho vybaven\'{\i} a u\v{c}ebnic poskytly \dots  } (PDT,
bm122zua.fs $\sharp$21)
\\
$[$financial - means/sources - for purchase - (of) technical -
equipment - and - textbooks - provided$]$
\\
(Financial sources for technical equipment and textbooks were
provided by \dots )
\\
The verb {\it poskytnout} [to provide] constitutes a verbonominal
collocation together with the noun {\it prost\v{r}edek} [means],
type (1):

{\it prost\v{r}edek} \dots  \ Aim ({\it na}+Acc, {\it pro}+Acc,
{\it k}+Gen)
\\
%
According to the solution proposed the structure with the noun
chosen as the Pg governor is preserved (the other one, with the
Pg as free verbal modifier (also Aim), is excluded).

In such constructions, the Pg modifies the whole verbonominal
collocation and cannot be seen as a purely nominal modifier; this
is supported by the changes in syntactic structure of such groups
in case of adjectival derivation:
\\
{\it poskytnout (prost\v{r}edky (na n\v{e}co))} $\rightarrow $
{\it prost\v{r}edky (poskytnut\'e (na n\v{e}co))}
\\
$[$to provide means for st.$]$  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
$[$means/sources provided for st.$]$
\\
The Pg is treated as a nominal modifier in the verbonominal
collocation. The other syntactic structure is relevant for the
construction with a deverbal adjective: {\it poskytnut\'y} (pl
{\it poskytnut\'e}) [provided] is a congruent attribute following
its governing noun {\it prost\v{r}edky} [means]; thus, according
to the WOP, the Pg  {\it na n\v{e}co} [for st.] is preferably
treated as a modifier of the adjective.
%
\subsubsection{Description of non-projetive constructions.}
The dependency tree is projective if all nodes ($n_i$) - lying
between a governor node ($n_g$) and a node ($n_d$) depending on
$n_g$ - depend (directly or indirectly) on this governor node
($n_g$). Otherwise it is non-projective. (The formal definition of
projectivity and non-projectivity can be found e.g. in [3].)
%
\begin{description}
  \item[Observations.] (valid for verbonominal collocations, type
  (1))
\\
- A valency modifier of a noun expressed by Pg can precede its
noun governor in the surface structure of a sentence. (Analyzing
such a Pg modifier WOP's cannot be applied).
\\
- A valency modifier of a noun expressed by Pg and its noun
governor can be `separated' by the verb form, we can get a
non-projective structure on the level of surface representation
(WOP's cannot be taken into account).
\\
- Free modifiers of a noun expressed by Pg's must follow their
governor on the surface level - the WOP's are applied.
\end{description}
%
\paragraph{Example (3):} {\it Na uve\v{r}ejn\v{e}n\'{\i} odpov\v{e}di m\'a
podle n\v{e}ho pr\'avo ka\v{z}d\'a fyzick\'a nebo pr\'avnick\'a
osoba \dots } (PDT, bmd23zua.fs $\sharp$46, modified))
\\
$[$on - publication - (of) reaction - has - according to - him -
right - every - person - or - legal - entity$]$
\\
(According to him, every person or legal entity has the right of
publication of reaction \dots \ )
\\
The noun {\it pr\'avo} [right] constitutes a verbonominal
collocation, type (1) together with the verb {\it m\'{\i}t} [to
have].

{\it pr\'avo} \dots \ Pat (Gen/{\it na}+Acc/{\it
k}+Dat/infinitive)
\\
The Pg {\it na uve\v{r}ejn\v{e}n\'{\i} (odpov\v{e}di)} [of
publication (of reaction)] meets the valency requirement of the
noun {\it pr\'avo} [right] resulting in a non-projective
construction.
%
\section{Arrangement of the Criteria}
%
An {\bf analysis by reduction} (RA) is a general method that can
naturally underlie any automatic parsing procedure.

The analysis by reduction consists of stepwise simplification of
an extended sentence so that its syntactic correctness is
preserved. In each stage the simplification is realized by
deleting one word of a sentence and possibly rewriting other
words. This process is non-deterministic, in each stage any of the
mutually independent words can be deleted.

In the next paragraphs we propose the partial use of RA for the
detection of Pg-governors. (For the particular description of the
criteria used see [6].)
%
\subsubsection{Routine.}
In every possible stage of analysis in which Pg is reduced all
criteria under consideration are applied.
%
\begin{description}
\item[Step 1.]
The word order pattern of the simplified sentence is specified.
\item[Step 2.]
All valency requirements of autosemantic verbs, nouns and
adjectives are examined. With respect to word order limits (as
they are embodied in WOP) every suitable valency slot is filled
in by the tested Pg. If some verbonominal collocation, type (1)
is detected then the valency requirements are satisfied
regardless of the relevant word order limitations. Possible new
structures are evaluated according to the reliability of valency
frames.
\item[Step 3.]
The information following from the word order pattern of the
simplified sentence is applied. All possible dependencies are
marked. New structures are of lower preference than the ones
described in the preceding point.
\item[Step 4.]
Optionally, semantically based criteria can be applied serving
for the evaluation of existing structures.
\item[Step 5.]
The formal criteria are checked with regard to the original
sentence. If any new structure violates these criteria then it is
excluded from further analysis.
\item[Step 6.]
If at least one new structure satisfies the formal criteria then
Pg is deleted. Otherwise this branch of  analysis is excluded
because it does not preserve the condition of correctness.
\end{description}
%
\paragraph{Example (4):}
{\it Rodiny maj\'{\i} n\'arok na p\v{r}\'{\i}sp\v{e}vek.} (PDT,
bl103zu.fs, shortened)
\\
$[$Families have (a) claim to (an) allowance.$]$
\\
(a) If the verbonominal collocation {\it m\'{\i}t n\'arok} [to
have (a) claim], type (1) is taken into account the reduction of
the Pg {\it na p\v{r}\'{\i}sp\v{e}vek} [to allowance] starts in
two stages (see Fig.1, bold arrows). According to the solution
proposed above the dependency pair {\it n\'arok na
p\v{r}\'{\i}sp\v{e}vek} [claim to allowance] is created (in
agreement with the valency requirement of the noun).
\\
(b) If the verbonominal collocations are not considered the
analysis {\it m\'{\i}t na p\v{r}\'{\i}sp\v{e}vek} is also allowed.
%in (1) and (2).
The reduction of Pg then starts in further two stages (see Fig.1,
dotted arrows).
%
The two analyses satisfy the condition on preserving syntactic
correctness, both are successful. However, the second structure
{\it m\'{\i}t na p\v{r}\'{\i}sp\v{e}vek} accidentally has another
meaning than the original sentence has. Its meaning is connected
with a frozen collocation {\it m\'{\i}t na n\v{e}co
(prost\v{r}edky/pen\'{\i}ze/ \dots )} [to have the wherewithal's
for fee]. The source of this coincidence lies in the lexical
entries, therefore it cannot be covered by general rules.
%
\begin{figure}
\centerline{\psfig{figure=fig2.eps,width=12.2cm}} \caption{The
possible stages during RA}
\end{figure}
%
\section{Conclusions}
We have tried to illustrate the usefulness of criteria for
detection of Pg-ambiguity based on word order patterns and
valency requirements of nouns and adjectives. Special interest
has been devoted to verbonominal collocations and to their
contribution to analysis of non-projective constructions. The
last section has been focused on the analysis by reduction. The
mechanism of this type of analysis has been illustrated and the
treatment of the proposed criteria has been discussed.
%
\subsubsection{Acknowledgement.} The research reported on this
paper has been supported by the grant VS 96/151.
%
\begin{thebibliography}{6}
\bibitem{all}
Allen, J.: Natural Language Understanding. The Benjamin/Cummings
Publishing Company (1987)
\bibitem{ho:ku:ol:pla}
Holan, T., Kubo\v{n}, V., Oliva, K., Pl\'atek, M.: On Complexity
of Word Order. Special Issue TAL on Dependency Grammars (to
appear)
\bibitem{mar}
Marcus, S.: Sur la notion de projectivit\'e. In: Zeitschr. f.
math. Logic und Grundlagen d. Math. XI (1965) 181-192
\bibitem{jpa81}
Panevov\'a, J.: K ot\'azk\'am homonymie a neutralizace ve
stavb\v{e} v\v{e}ty. Jazykovedn\'e \v{s}t\'udie {\bf 16} (1981)
85-89
\bibitem{sga:haj:pan}
Sgall, P., Haji\v{c}ov\'a, E., Panevov\'a, J.: The Meaning of the
Sentence in Its Semantic and Pragmatic Aspects. Dordrecht:Reidel
and Prague:Academia (1986)
\bibitem{str}
Stra\v{n}\'akov\'a, M.: Selected Types of Pg-Ambiguity. PBML {\bf
72} (1999) 29-58
\end{thebibliography}
%
\end{document}
