\documentstyle[a4dutch,lingmacros,12pt]{article}

\title{Deterministic Machine \\ -- report on the deterministic parsing
module \\ of the Grammar Checker} 

\author{Jan Hric \and Alexandr Rosen \and Mark\'eta
Stra\v{n}\'akov\'a\thanks{
These are the names of authors who contributed directly to this part of the
report. However, the authors also wish to thank other people whose
contribution was indirect but all the more substantial, most notably Petr
J\"ager, Eva Haji\v{c}ov\'a and Karel Oliva. This does not mean that they
are to be blamed for any defects.}}

\begin{document}

\maketitle

\section{Introduction} 

There are some constructions in natural language, which are frequent,
typical and relatively unambiguous. The `Deterministic Machine' is supposed
to handle such constructions. Motivations for including a preprocessing
module of this type -- the Deterministic Machine (henceforth DM) -- as a
component of the grammar checker are of the following two kinds:

\begin{itemize}

\item Decrease in computational costs (esp. time) is expected if DM succeeds
in predicting correct analyses of some frequently occurring and locally
identifiable grammar phenomena in a significant share of the input.

\item The distinction between the processing of local and sentential
contexts, which is inherent in the two-component design of the system,
enables testing of linguistic hypotheses concerning locality of various
grammar phenomena.

\end{itemize}

The former consideration has influenced one of the fundamental aspects of
the DM design: only left modifications of heads are processed.

To ensure full compatibility of data (lexicon, grammar, input strings and
output structures), the DM is an integral part of the whole system and
shares as many functions as possible with the non-deterministic part.

\section{Basic features of the deterministic machine}

\begin{itemize}

\item DM uses the same lexicon as the non-deterministic module and a subset
of its grammar. The form of lexical entries and grammar rules is identical.
In fact, there is a single grammar and lexicon; grammar rules which describe
phenomena to be covered by DM are identified as such in the grammar.

\item Grammar rules used by DM should cover relatively frequent, locally
detectable phenomena. Furthermore, the grammar rules are restricted to
head-final structures, i.e., right modifiers (complements or adjuncts) are
excluded.  Typical examples consist of head-final adverbial, adjectival and
nominal phrases (possibly including prepositional phrases). Simple cases of
coordination are other likely candidates. Provisions are made for parsing
right modifiers of such heads in the non-deterministic module. The rules can
be ordered into classes, processed successively in more passes.

\item The output of DM is written directly into the chart of the
non-deterministic module as a string of partial parses. If the
non-deterministic module fails to confirm the hypotheses made by DM,
processing backtracks to the original input, which is now parsed by the
non-deterministic module directly.

\item DM accepts as input strings sentences processed by lexical lookup
component, admitting lexical ambiguities. These ambiguities can be resolved
in DM and no more ambiguities should be introduced by the rules.

\item DM processes the input string, a sequence of edges, from left to
right. After all possible rules are applied on all possible sequences of
edges in a certain stretch of the string, delimited by the string beginning
and the edge most recently read from the input, edges used by the rules are
eliminated, and, subsequently, edges which do not form a path within that
stretch. A new edge from the input string (to the right) is then read.

\item DM performs only (partial) analysis of the input. No error checking as
such is done here.

\end{itemize}

\section{Linguistic issues}

\subsection{The extent and organization of grammar}

The question of which grammar phenomena should be covered by DM is an
empirical one: testing on large text samples with different grammar-rule
setups is previewed. As the first approximation of potential candidates, the
following phenomena have been selected (expressed in a quasi-rule notation,
bar levels ignored, heads in capital letters):

\begin{enumerate}

\item adverb $\rightarrow$ adverb + ADVERB

\item coordination of adverbs\footnote{Same as all other structures,
coordination is treated by binary rules, i.e., two rule applications are
necessary to cover the coordination of two conjuncts.}

\item adjective $\rightarrow$ adverb + ADJECTIVE

\item coordination of adjectives

\item noun $\rightarrow$ adjective + NOUN

\item coordination of nouns

\item `prepositional phrase'\footnote{More precisely, {\it noun in
prepositional case}.} $\rightarrow$ preposition + NOUN

\item coordination of `prepositional phrases'

\end{enumerate}

The order of rules might correspond to the sequence of passes, or more rules
can be processed in a single pass.

\subsection{Preliminary testing of linguistic adequacy}

\subsubsection{The data}

The function of DM was simulated by hand on samples taken from several texts
-- mainly newspaper texts ({\it Lidov\'e noviny, MF Dnes}, the general
interest magazine {\it El\'an}) and texts from the literary and art magazine
{\it Revolver Revue}. Eighty sentences have been selected, the average number
of words in a sentence being 16.


\subsubsection{The choice and the effect of grammar rules}

At first only LEFT MODIFIERS represented by the following four rules were
processed (heads in capitals; bar levels ignored; agreement beween noun and
its modifying adjective is respected).


\begin{enumerate}

\item[(i)] Adv $\rightarrow$ Adv ADV

\item[(ii)] Adj $\rightarrow$ Adv ADJ

\item[(iii)] Noun $\rightarrow$ Adj NOUN

\item[(iv)] PP $\rightarrow$ Prep NOUN

\end{enumerate}

\begin{enumerate}

\item[ad (i)] The rule (i) was applied six times correctly and six times
incorrectly. The main problem was that the rule was incorrectly applied on
pairs of adverbs which did not form a phrase\footnote{ Also a problem with
relative adverbs appeared -- the rule was incorrectly applied on relative
adverbs followed by a common adverb, but this was just a matter of too
loosely contrained grammar used for this simulation, (e.g. {\it V
lokalit\'ach, kde ji\v{z} bylo po\v{s}kozeno $\ldots$} `in localities where
already has\_been damaged $\ldots$')}.
 
\eenumsentence{

\item \shortexnt{5}
{Premi\'er & pot\'e & podrobn\v{e} & vysv\v{e}tlil & $\ldots$}
{Premier &   then   & in\_detail   & explained     & $\ldots$}
 
\item \shortexnt{7}
{Pravidla & \v{c}esk\'eho & pravopisu, & d\'ale & jen & Pravidla, & $\ldots$} 
{Rules & [of] Czech & orthography, & below & only & Rules, & $\ldots$}
 
\item \shortexnt{6}
{A & mo\v{z}n\'a & tak\'e & proto & z{\accent'27u}staly & nepov\v{s}imnuty.} 
{And & maybe & also & therefore & remained & unnoticed.}

}

\item[ad (ii)] The second rule was applied 19 times correctly and 9 times
incorrectly. There was one type of misapplication: again, the rule applied
on adverbs which did not modify the head\footnote{
Similarly as above, relative adverbs were incorrectly interpreted as
modifiers of a following adjective {\it P\v{r}\'{\i}pad{\accent'27u}, kdy
zab\v{e}hl\'y pes napadne $\ldots$} `Cases when [a] stray dog attacks'}. 

\eenumsentence{

\item \shortexnt{5}
{jinde & star\'e & podlahy & podp\'{\i}raj\'{\i} & k{\accent'27u}ly}
{elsewhere & old & floors & are\_supported & by\_piles}

\item \shortexnt{6} 
{Z\'akon & by & neovliv\v{n}oval & negativn\v{e} &
vytv\'a\v{r}en\'{\i} & rodiny} 
{the\_law & would & not\_influence &
negatively & [the] creation/created & of\_family}

}

Sometimes the cause was ambiguity between Prep and Adv\footnote{The
ambiguity of {\it proti} `against' is an arguable case and should probably
be solved by eliminating the adverbial variant.}.

\eenumsentence{

\item \shortexnt{4}
{Podle & jejich & slov & $\ldots$}
{According\_to/vilely & their & words & $\ldots$} 

\item \shortexnt{4}
{kampa\v{n} & proti & jadern\'e & elektr\'arn\v{e}} 
{campaign & against & [the] nuclear & power\_plant}

}

\item[ad (iii)] The third rule was applied 165 times correctly. Except for
the problems concerning right modifiers (which will not be handled by DM),
parallel edges (see below) and coordination (see below) only one error
occurred.

\enumsentence{
\shortexnt{5}
{chr\'anit & bezpe\v{c}nostn\'{\i} & z\'ony & vyhl\'a\v{s}en\'e & OSN} 
{to\_protect & [the] safety & zones & proclaimed & [by the] UN}
}

There were relatively many cases (13) where a noun was adjacent to an
adjective which was not its modifier. Incongruent agreement features mostly
prohibited incorrect application of the rule, but not always -- the only
incorrect application of this rule was of this type.

\eenumsentence{

\item \shortexnt{3}
{rozhodnut\'{\i} & ministerstva & $\ldots$} 
{decision/decided-{\scriptsize masc;pl:nom} & ministry-{\scriptsize
neut;sg:gen/pl:nom,acc,voc} & $\ldots$}

\item \shortexnt{3} 
{roz\v{s}\'{\i}\v{r}en\'{\i} & t\v{e}\v{z}by & v\'apence}
{extension/extended-{\scriptsize masc,pl:nom} & production-{\scriptsize fem;
sg:gen/pl:nom,acc,voc} & of\_limestone}

}

\item[ad (iv)] The last rule was applied 90 times correctly and 22 times
incorrectly. The problems concerned right modifiers again -- 18 cases.

\eenumsentence{

\item \shortexnt{4}
{ve & v\v{e}t\v{s}in\v{e} & p\v{r}\'{\i}pad{\accent'27u} & $\ldots$} 
{in & [the] majority & [of] cases & $\ldots$}

\item \shortexnt{4}
{protestoval & proti & \'utoku & Muslim{\accent'27u}} 
{protested-{\scriptsize 3sg} & against & [the] attack & [by the] Muslims}

}

Such misinterpretations will be handled by the non-deterministic module in a
routine fashion\footnote{All structures parsed by DM enter the
non-deterministic module with the attribute `constituent\_type' set to
`lexical', which makes it possible to parse such `right modifications of
PPs''}. Other problems concerned parallel lexical structures (esp. homonymy
of demonstrative pronouns, see below) and coordination (see below).

\end{enumerate}


\subsubsection{Ambiguities}

The string of lexical representations of the words of an input sentence may
contain parallel edges. In some cases DM accepts one
reading, in other cases it preserves non-determinism from the input.

The proposed strategy was successful in 53 cases and failed in 20 other
cases. Many of these errors (12) concerned the rule (iv) PP $\rightarrow$
Prep NOUN, mainly in connection with the ambiguity between Adj and N
(8 occurences, esp. demonstrative pronouns -- these may be removed by a
modified classification of demonstrative pronouns, see bellow).\newline

\begin{samepage}

Example:

{\it Z tohoto d{\accent'27u}vodu} $\ldots$ `for this reason'


\begin{verbatim}
           Z   tohoto   duvodu  ... 
                 _Adj_
          Prep  /     \     N
         *----*<       >*-------*
          \     \__N__//
           \___PP_____/

\end{verbatim}

The fourth rule was applied on the edges Prep and N, correct reading was
omitted.

This ambiguity caused also another type of errors:\newline

Example:

{\it Jsou  tou   svatou   chv\'{\i}l\'{\i} ,  kdy  $\ldots$} 
`[they] are that sacred/saint moment, when'


\begin{verbatim}
           Jsou  tou   svatou   chvili ,  kdy  ... 
                 _N_     Adj
           V    /   \   /   \     N
         *----*<     >*<     >*-------*
               \\Adj/   \_N_//
                \_____N_____/

\end{verbatim}

Two readings remained (N + Adj, N [Adj + N]), both incorrect.

Ambiguity between Prep and Adv may cause errors, too.\newline

Example:

{\it Podle jejich slov} $\ldots$ `according\_to/vilely their words' 

\begin{verbatim}

           Podle   jejich   slov  ...  
            Prep
           /    \   Adj      N
         *<      >*------*-------*
          \\Adv_/       /
           \_____Adj___/

\end{verbatim}

Other interesting examples:

{\it (St\v{e}ny   a   klenby)   dom{\accent'27u}   ni\v{c}\'{\i}   voda.} 
`Walls and vaults of\_houses/home[ward] is\_destroying/nobody's
water-{\scriptsize nom}.'


\begin{verbatim}

         (Steny   a   klenby)   domu   nici   voda .
                                _N_     _V_
            N    Conj   N      /   \   /   \    N
         *-----*-----*-------*<     >*<     >*-----*
                             \\\Adv/   \Adj//      /
                              \\____Adj____/      /
                               \________N________/

\end{verbatim}

The rules (ii) and (iii) were applied, edges with correct reading (N and V)
were deleted\footnote{ However, the Adv Adj reading is very weird, which is
again due to the loosely constrained specification of the grammar used for
simulation. The word {\it ni\v{c}\'{\i}} in the adjectival reading is
actually possessive pronoun, which can be modified only by a very restricted
class of adverbs like {\it opravdu} `really'.} as a
cul-de-sac.\footnote{Edges are in cul-de-sac if they do not connect both
ends of the graph, i.e. if they do not represent a path from the leftmost to
the rightmost node.}

{\it Toto   posti\v{z}en\'{\i}   lid\'e   ch\'apou }  
$\ldots$ `This-{\scriptsize neut,sg}  afflicted-{\scriptsize
masc.anim.,pl}/affliction-{\scriptsize neut,sg} people-{\scriptsize
masc.anim.,pl} understand.'

\begin{verbatim}

           Toto   postizeni   lide   chapou   ...
           _____N______
          /ADJ     __N__\
         //   \   /     \\    N       V
        *<     >*<       >*-------*--------*
          \_N_/  \\_Adj_/         /
                  \______N_______/

\end{verbatim}

The rule (iii) was applied twice, then the first NP edge was deleted (as a
cul-de-sac).

There are two readings of this sentence:

1. {\it (Toto posti\v{z}en\'{\i}) lid\'e ch\'apou} $\ldots$ (discarded by DM).

2. {\it Toto (posti\v{z}en\'{\i} lid\'e) ch\'apou} $\ldots$ (accepted by DM).


\subsubsection{Coordination}

Another type of linguistic phenomenon considered as a potential candidate to
be treated by DM is coordination of nouns (NP's) and adjectives (AdjP's).

Problems occur in coordination of the type Prep (N + N) (e.g. {\it
Slovn\'{\i}k spisovn\'e \v{c}e\v{s}tiny pro \v{s}kolu a ve\v{r}ejnost}
`Dictionary of literary Czech for school and [the] public'; {\it P\v{r}i
setk\'an\'{\i} s ministrem a p\v{r}edsedou \v{r}ekl $\ldots$)} `during [the]
meeting with [the] minister and [the] chairman [he] said'.\newline

Example:

{\it pro   \v{s}kolu   a   ve\v{r}ejnost} `for school and public'


\begin{verbatim}
           pro   skolu   a   verejnost

           Prep    N    Conj     N
         *-----*-------*---*-----------*
          \_____PP____/ \   \_?Ncoor__//
                         \___?Ncoor'__/

\end{verbatim}

DM applies the rule (iv) on the Prep and first N, this N is deleted
and then the two members of coordination cannot be put together.

As for other type of errors -- DM can connect lexical items which in fact do
not belong together.\newline

Example:

{\it Vid\v{e}l   Marii   a   Kl\'aru   p\v{r}ehl\'edl.} 
`[He] saw Marie-{\scriptsize acc} and Kl\'ara-{\scriptsize acc} [he]
overlooked.'


\begin{verbatim}
           Videl   Marii   a   Klaru   prehledl.

             V      N    Conj     N        V
         *-------*------*----*---------*---------*
                  \      \    \?Ncoor///
                   \      \__?Ncoor'_//
                    \______N_________/

\end{verbatim}

DM  applies   coordination  rules  on   two  N's  and   Conj incorrectly. 
In fact this sentence is composed by two clauses, not by one clause with
coordination of N's.

The following interesting example illustrates the action of DM:\newline

{\it Za  hlavn\'{\i} pova\v{z}oval zdrav\'{\i} a posti\v{z}en\'{\i} lid\'e k
n\v{e}mu nesm\v{e}li.}

`As the\_main\_thing [he] considered health / healthy and affliction /
afflicted people to him were\_not\_allowed.'

\begin{verbatim}

Za  hlavni povazoval zdravi a postizeni lide k nemu nesmeli.
                     ______N________
                    /_N_         _N_\
Prep  Adj      V   //   \  Conj /   \\  N   Prep N    V
*--*------*-------*<     >*---*<     >*----*---*---*------*
                  \\\Adj/       \Adj//    /
                   \\______Adj______/    /
                    \__________N________/

\end{verbatim}

First, both coordination rules for N's and Adj's are applied. The rule (iii)
is used on the resulting Adj and the following N edges with an NP edge as an
output. In the next step the edge corresponding to the coordination of N's
is deleted as a cul-de-sac. Thus N modified by coordination of Adjs remains
as the valid reading. But the correct reading has to interpret {\it
zdrav\'{\i}} as N and {\it nemocn\'{\i}} as Adj.

A small  modification  of  the  sentence  (adding  the  left modifier sv\'e
 -- reflexive possessive -- to the N {\it zdrav\'{\i}} `health') leads to a
 completely different structure:\newline

{\it Za hlavn\'{\i} pova\v{z}oval sv\'e zdrav\'{\i} a posti\v{z}en\'{\i}
lid\'e k n\v{e}mu nesm\v{e}li.}

\begin{verbatim}

Za hlavni povazoval sve zdravi a postizeni lide k nemu
                     _________N________            nesmeli.
                    /__N____           \
                   //    _N_\        _N \
Prep  Adj    V    //Adj /   \  Conj /   \\  N   Prep N   V
*--*-----*--------*---*<     >*---*<     >*----*---*---*---*
                        \Adj/       \Adj/

\end{verbatim}

\end{samepage}

Now, the rule (iii) is applied on Adj {\it sv\'e} and N {\it zdrav\'{\i}},
the edge with Adj for {\it zdrav\'{\i}} is deleted as a cul-de-sac and the
coordination rules for Ns are used (the edge with Adj for {\it
posti\v{z}en\'{\i}} is deleted). Thus the coordination of NP [sv\'e zdrav\'{\i}] and N [posti\v{z}en\'{\i}] remains
as the valid reading. However, the correct reading is discarded as in the
previous sentence.


\subsubsection{Conclusions from preliminary testing}

Evaluation of the results has helped to tune the DM parsing algorithm, to
form an estimate of linguistic phenomena and contexts which DM can handle
and to make a preliminary assessment concerning the choice of grammar rules
and their processing order (if any).

\subsubsection*{Suggestions:}

\begin{enumerate}

\item[(a)] Some semantic \underline{constraints on adverbs} in the rules (i)
and (ii) would be useful.

\item[(b)] \underline{Demonstrative pronouns}: It seems to be better (for
the purposes of DM and perhaps also for the non-deterministic module) to
classify demonstrative pronouns only as Adj (syntactic class), not both as Adj and N.
This would remove some cases of parallel edges and, consequently, some
problems mainly with the application of the rule (iv). This classification
is corroborated by the fact that such situation is relatively frequent when
Adj occurs without N (ellipsis) and demonstrative pronouns seem to behave
similarly as these Adj's.\newline

Example:

{\it L\'{\i}b\'{\i} se mi \v{z}lut\'a barva, modrou r\'ada nem\'am.}

{\it L\'{\i}b\'{\i} se mi tahle barva, tamtu r\'ada nem\'am.}

\item[(c)] \underline{PP $\rightarrow$ Prep  Noun}

The question is whether prepositional phrase is a suitable linguistic
phenomenon to be treated by DM. The problems concerning the rule (iv) are
connected with right modifiersth parallel edges and mainly with
coordination. Testing on more material is needed to substantiate a decision.

\item[(d)] \underline{Coordination} -- similarly as with prepositional phrases, testing on more data is needed.

\end{enumerate}

\section{Description of the algorithm and its implementation}

\subsection{An informal description of the algorithm}

In the following description the term ``head'' will be used  for an edge
which can `fold' other edges during parsing of a sentence, provided that a
grammar rule licenses the action. I.e., the other edges must be labelled by
categories interpretable as being governed by the head.

DM starts at the leftmost edge, proceeds to the right and performs the
following operations on each input string:

If a current edge has subordinate edges at the left-hand side, it folds the
longest chain of subordinated edges, i.e. it creates a new edge, which will
represent the whole folded phrase. If there are several longest chains, it
creates more parallel edges. Then it prunes all used edges and all edges
which do not belong to some continuous path from the start node to the end
node. Processing then continues using the next right-hand edge.

\subsection{Interface to the non-deterministic module}

The whole processing of a single sentence is performed in three stages:

\begin{enumerate}

\item DM processes an input string (a sentence), possibly producing parses
of its substrings as the output.

\item The non-deterministic module processes the output of DM. If the whole
sentence is parsed successfully, then the non-deterministic module writes
out a message ``No errors found'' and stops; else processing continues with
the next stage.

\item The non-deterministic module processes the original input. If DM has
created some edge(s) which are not justified in the broader (sentential)
context, then -- in the current design of the system -- the
non-deterministic module cannot undo such edges in the stage 2. Therefore it
backtracks and attempts to parse the original input. At this stage, it also
looks for errors.

\end{enumerate}

\subsection{Problems and solutions}

\subsubsection{Phases of processing} 

DM need not perform all its computation during one traversal through the
input edges, but it can traverse the input string more times. It can use 
different rules for different linguistic phenomena in successive phases. The
input of DM is the input into the first phase and each subsequent phase
takes as its input the output of the previous phase. The output of the last
phase is the output of the whole DM.
   
The implementation enables the user to define phases and correspondence of
the rules of grammar to the phases.

DM produces correct parses if all left modifiers of a head
are identified before the head itself is interpreted as a left modifier of
another head.

\subsubsection*{Example:}

\begin{itemize}

	\item[Input:] A + B + C

	\item[Rules:] 

	\begin{enumerate} 

		\item B $\rightarrow$ A + B\footnote{Bar levels are ignored.}

		\item C $\rightarrow$ B + C

	\end{enumerate}

\end{itemize}

The rule (1) must be used before the rule (2) in this example to get a
successful parse, i.e. (1) must be used in the same or in a preceding phase
with respect to (2). Else, after application of the rule (2) we get ``A +
C'', and then it is not possible to interpret the edge A as a modifier of B
(without announcing an error). In this case the parsing of the sentence
enters the stage 3 according to the description of the whole algorithm.

We can look at the whole computation of the non-deterministic module as a
phase which follows all phases of DM. If we want to gain full advantage of
DM and to exclude similar cases as in the preceding example then the
deterministic module must

\begin{enumerate}

\item recognize and fold all edges to the left of a head which are
interpretable as modifiers of that head;

\item have rules which can be recursively applied in the same phase.

\end{enumerate}

The need to invoke the non-deterministic module on the original input
sentence will depend on the quality of the output from DM, i.e. on the
quality of decisions which phenomena (and corresponding rules) the
deterministic module will work with. If the decisions will be wrong then
some unnecessary work will be done during the processing by DM (stage 1) and
the following processing of the misinterpreted input by the
non-deterministic module (stage 2), but the behavior of the whole system
will not degrade into a failure. The reason is that the final stage 3
remedies all wrong decisions of DM.

\subsection{The treatment of structures not covered by a single application
of a binary rule}

Both modules, deterministic and non-deterministic, will have the same
grammar. The non-deterministic module does not allow rules which have more
than two items on the right-hand side (i.e., it accepts only `unary' and
binary rules). But some structures including those considered as candidates
for the treatment by DM consist of more than two items. If the construction
of new edges were irreversible then DM would fail to parse the following
strings correctly:

\eenumsentence{
\item	
 \shortexnt{7}
 {velk\'y & + & a & + & mal\'y & + & pes}    
 {big-{\scriptsize adj} & + & and-{\scriptsize conj} & + &
 small-{\scriptsize adj} & + & dog-{\scriptsize n}}
 \label{vampes}
\item
 \shortexnt{7}
 {student & + & a & + & mal\'y & + & pes}    
 {student-{\scriptsize n} & + & and-{\scriptsize conj} & + & small-{\scriptsize adj} & + & dog-{\scriptsize n}}
 \label{sampes}
}


The edge `mal\'y' can be extended to the left with edge `a' in both cases.
But in (\ref{sampes}) there is no other edge with Adj before the edge `a',
and DM is not able to complete the whole structure Adj + Conj + Adj. The
edge corresponding to the unfinished construction `a mal\'y' remains and it
does not allow to parse the whole sentence by the non-deterministic module
correctly. In the following a solution is decribed which blocks the creation
of such incomplete edges.

Newly created edges are distinguished as `complete' or `incomplete'. An edge
is marked as `complete' if it represents a complete linguistic structure.
Otherwise it is marked as `incomplete'. An `incomplete' edge corresponds to
a part of some structure, which consists of at least three elements, where
not all of these elements have so far been parsed. This type of edge has no
lexical meaning and the corresponding string cannot occur in a sentence
alone. All `incomplete' edges are later pruned if they cannot be extended,
i.e. they are never passed over to the following phase. The creation and
pruning of edges allows some kind of nondeterminism, because it is possible
to try to extend the actual head -- the right-most read word -- to the left
side, but if the extension is impossible to complete, thus wrong, the
algorithm is able to recover used edges in the following manner.

Each edge has the status `free', `restorable', `used' or `pruned'. An edge
is initially `free', which means that it was not used for the construction
of a new edge. The edge changes its status to `used' if it was used for the
construction of a `complete' new edge. If it was used for the construction
of some new edges, but all of them were `incomplete', then it acquires the
status `restorable'. If an `incomplete' edge is used for the creation of a
`complete' one, then this information is propagated recursively to all
`restorable' edges, whose status is changed to `used'. As soon as all
possible left modifiers of the currently read head are found (the head is
projected as far to the left as possible), all incomplete edges are pruned
-- their status changes to `pruned' -- as well as all used edges. The
`restorable' edges are changed to `free', because they were used only to
construct an `incomplete' edge.

\subsection{Pseudocode of the deterministic module}

\subsubsection*{Input:}

\begin{description}
\item nodes 1..N
\item edges, marked as `free'
\end{description}

\subsubsection*{Used internal structures:}

\begin{itemize}

\item Each newly created edge can be marked in one of the following ways
according to its completeness:

\begin{itemize}

\item[`complete'] -- can occur as a part of the output;

\item[`incomplete'] -- must be processed in deterministic module

\end{itemize}

\item Each edge has a status from the following list:

\begin{itemize}

\item[`free'] -- not used yet, also initial value
\item[`restorable'] -- used to create only `incomplete' offsprings
\item[`used'] -- used to create at least one `complete' offspring
\item[`pruned'] -- pruned, cannot be used in following phases

\end{itemize}

\end{itemize}

\subsubsection*{Algorithm:}

\begin{verbatim}

1. for all phases do
 2. for all nodes J := 3..N do  // read next word
  3. for all nodes I := J-2..1 do // looking for left expansions
   4. for all heads A from K to J, I<K<J do
    5. for all edges B from I to J, which are not pruned, do
     6. for all rules X -> Y + Z
      7. if Y and Z respectively, match with A and B
           respectively then
           create the new edge X from I to J. Mark the new edge 
           as `free' and `complete' or `incomplete' according
           to the type of the rule.
       9. if X is `complete' then mark A and B as `used',
           otherwise mark them as `restorable'. If A or B
           should be marked as `used' and simultaneously as
           `restorable', then they are marked as `used'.
       10. if X is `incomplete', store the ancestor edges
           A and B, which X was created from.
       11. if A or B were `incomplete'
           edges, which changed its status from `free' or
           `restorable' to `used', then change for
           all ancestors (recursively for all levels)
           stored in step 10 their status to `used'.
      end if (7)
     end for (6)
    end for (5)
   end for (4)
  end for (3)
  12. // pruning
   13. all `incomplete' edges change to `pruned'
   14. all `restorable' edges mark as `free'
   15. all `used' edges mark as `pruned'
   16. all edges, which do not belong to any continuous path
     from node 1 to node N, mark as `pruned'
  end (12) // pruning
 end for (2)
end for (1)

\end{verbatim}

\subsubsection*{Output:}
 All edges, which are not `pruned'. (All of them are `free').

\end{document}

