=Paper=
{{Paper
|id=None
|storemode=property
|title=Formalization of Word-Order Shifts by Restarting Automata
|pdfUrl=https://ceur-ws.org/Vol-1003/2.pdf
|volume=Vol-1003
|dblpUrl=https://dblp.org/rec/conf/itat/LopatkovaP13
}}
==Formalization of Word-Order Shifts by Restarting Automata==
https://ceur-ws.org/Vol-1003/2.pdf
ITAT 2013 Proceedings, CEUR Workshop Proceedings Vol. 1003, pp. 2–9
http://ceur-ws.org/Vol-1003, Series ISSN 1613-0073, c 2013 M. Lopatková, M. Plátek
Formalization of Word-Order Shifts by Restarting Automata∗
Markéta Lopatková and Martin Plátek
Charles University in Prague, Faculty of Mathematics and Physics
Malostranské nám. 25, 118 00 Prague, Czech Republic
lopatkova@ufal.mff.cuni.cz, martin.platek@ufal.mff.cuni.cz
Abstract: The phenomenon of word order freedom plays a number of word order shifts within the analysis by re-
an important role in syntactic analysis of many natural lan- duction. This interplay was exemplified on a sample of
guages. This paper introduces a notion of a word order Czech sentences with clitics and non-projectivities (long
shift, an operation reflecting the degree of word order free- distance dependencies, see esp. [10, 4]). This approach is
dom of natural languages. The word order shift is an op- based upon the method of analysis reduction – a stepwise
eration based upon word order changes preserving syntac- simplification of a sentence preserving its correctness. The
tic correctness, individual word forms, their morphologi- analysis by reduction had been applied in a relatively free
cal characteristics, and their surface dependency relations manner with no constraints on the projectivity of its indi-
in a course of a stepwise simplification of a sentence, a so vidual steps. Our investigation focused on a set of syntac-
called analysis by reduction. tically analyzed Czech sentences from the Prague Depen-
The paper provides linguistic motivation for this opera- dency Treebank (PDT) [2]. The experiment on treebank
tion and concentrates on a formal description of the whole data showed that with only basic constraints on the analy-
mechanism through a special class of automata, so called sis by reduction, see [6], the minimal number of necessary
restarting automata with the shift operation enhanced with shifts for any sentence from the test set did not exceed one.
a structured output, and their computations. This number actually confirmed the initial assumption for
The goal of this study is to clarify the properties of com- Czech as a language with relatively high degree of word-
putations needed to perform (enhanced) analysis by reduc- order freedom; nevertheless, we have continued the search
tion for free word order languages. for more complicated sentences. This lead to the discov-
ery of a special construction requiring (at least) two shifts,
as it is discussed in Section 2.1.
1 Introduction
The analysis by reduction has served as a motivation for
The phenomenon of word order freedom plays an impor- new a family of automata, so called restarting automata,
tant role in syntactic analysis of many natural languages. see esp. [14, 13]. As a first step, analysis by reduction
A relatively free word order combined with additional lin- was modelled as a formal string to string translation using
guistic constraints constitutes a big challenge for a for- a suitable model of restarting automata [9]. Then a class of
mal description of syntactic structures.Here we introduce enhanced restarting automata with an output consisting of
a notion of a word order shift, an operation reflecting the a single DR-tree was introduced, [16]. Finally, the model
degree of word order freedom of natural languages. The was further enhanced – a model of restarting automata that
word order shift is a word order change preserving syntac- assign a set of dependency structures (DR-structures) to
tic correctness, individual word forms, their morphologi- every reduction of an input sentence was discussed, [15].
cal characteristics, and their surface dependency relations DR-structures can capture a set of dependency trees repre-
in the course of a stepwise simplification of a sentence un- senting sentence on different layers of linguistic descrip-
der investigation, referred to as an analysis by reduction. tion in a parallel way. Here we further enrich the perfor-
Section 2 provides a linguistic motivation and informal de- mance of these automata with the shift operation.
scription of the process.
Section 3 concentrates on a formal description of the
whole mechanism through a special class of automata, 2 Analysis by Reduction
so called restarting automata with the shift operation en-
hanced with structured output, pRLe -automata, and their
Let us first describe the main ideas behind the method used
computations.
for sentence analysis. Analysis by reduction (AR) is based
on a stepwise simplification of an analyzed sentence, see
Previous Work. The paper [6] introduced a specific ap- [8]. It defines possible sequences of reductions (deletions)
proach to the problem of measuring the word-order free- in the sentence – each step of AR is represented by deleting
dom. It focused upon an interplay of two phenomena re- a sentence member, possibly accompanied by rewriting a
lated to word order: a (non-)projectivity of a sentence and word of the sentence (and thus its shortening); in specific
∗ The paper reports on the research supported by the grant of GAČR cases, deleting is accompanied by a shift of a word to an-
No. P202/10/1333. other word order position.
Formalization of Word-Order Shifts by Restarting Automata 3
Let us stress the basic constraints imposed on the anal- We can notice that the order of reductions reflects the
ysis by reduction: dependency relations in the corresponding dependency
tree. Informally, the words are ‘cut from the bottom of the
(i) the obvious constraint on preserving individual words tree’ (in other words, the ‘pruning’ operation is applied on
(word forms), their morphological characteristics the tree); i.e., a governing node must be preserved in a sim-
and/or their surface dependency relations; plified sentence until all its dependent words are deleted.1
(ii) the constraint on preserving the correctness (i.e., a In other words, AR makes it possible to identify the de-
grammatically correct sentence must remain correct pendency tree for sentence (1):
after its simplification); bojí
Z
(iii) moreover, the application of the shift operation is lim- JJZ
Petr se o .
ited only to cases when a shift is enforced by the JJ
correctness preserving principle of AR, i.e., a simple otce
deletion would result in an incorrect word order and The analysis by reduction has been designed to model a
thus violate the principle (ii) above. human who is able to check the correctness of the analysis.
However, it is possible to model correct reductions on the
As a consequence of AR, it is possible to derive for-
basis of large corpora of natural language sentences, see
mal dependency relations between individual sentence
[11].
members – pairs of governing and dependent nodes –
based on the possible order(s) of reductions, as it is de-
scribed in [8, 15], see ex. (1) below. Compare also with 2.1 The role of shifts. The above mentioned experiment
other approaches aiming to determine dependency rela- on a set of non-projective sentences from PDT [2] (namely
tions summed up esp. in [1] and [12]. on the sentences with a non-projectivity given by a modal
Example: verb, see [3]) constituted only the first step.
(1) Petr se bojí o otce. As a follow-up experiment, we have decided to supple-
‘Peter – REFL – fears – for – father’ ment the data with ‘suspicious’ types of sentences identi-
‘Peter fears for his father.’ fied in previous work on Czech word order freedom, esp.
The analysis by reduction can be summarized in the fol- in [4]. It allowed to include also less frequent phenom-
lowing scheme: ena into our investigations. As a result, we found a well-
Petr se bojí o otce. formed Czech sentence that requites at least two shifts in
delete Z delete
the course of AR, see the following example (2).
=
~
Z Let us stress that the role of shifts in the course of the
Petr se bojí. * se bojí o otce. analysis by reduction was limited to cases where a shift
delete
?
shift
? ‘corrects’ word order of a simplified sentence – this con-
* se bojí. bojí se o otce. cerns primarily the cases when an input sentence contains
ZZ a clitic (as in sentences (1)-(2)).
shift
~ =delete
bojí se. Example:
Example (1) can be simplified in two ways (for simplicity, (2) S těžkým se bála pomoci úkolem.
we do not make distinction between upper and lower case ‘with – difficult – REFL – (she) was afraid – to help – task’
letters at the beginning of the sentence): ‘With a difficult task, she was afraid to help.’
(i) Either by simple deletion of the prepositional group Although the sample sentence is rather strange, the split-
o otce ‘for father’ (following the constraint on correctness ting of the prepositional group is a grammatical construc-
of the simplified sentence, the pair of word forms must be tion in Czech allowing to put a strong stress on an adjec-
deleted in a single step; see the left branch of the scheme). tive modifying the noun and not on the whole prepositional
(ii) Or by deleting the subject Petr (the right part of the group.
scheme); however, this simplification results in an incor- Due to the dependency relations present in the sentence
rect word order variant starting with the clitic se (such po- there is only one possibility how to reduce it, the reduction
sition of a clitic is forbidden in Czech). Thus the shift op- of the adjective těžkým ‘difficult’. Unfortunately, it results
eration correcting the word order is enforced →shi f t bojí in a syntactically incorrect word order:
se o otce. →delete * s se bála pomoci úkolem.
As these possible reductions are independent of each other, This situation can be corrected in two possible ways, let us
we can conclude that the words Petr and o otce are inde- focus on one of them:
pendent – in other words, both of them depend on / modify 1 Let us note that some relations – e.g., the relation between a prepo-
a word remaining in the simplified sentence, i.e., the verb sition and its ‘head’ noun as well as a verb and some clitic – are rather
technical (not only) from the point of view of AR: such pairs must be
and its clitic bojí se.
reduced in a single step (despite being represented as two nodes in a
Now, we can proceed in a similar way until we get the dependency tree); here we adhere to the practice used in the PDT anno-
minimal correct simplified sentence → bojí se. tation.
4 M. Lopatková, M. Plátek
→shi f t s úkolem se bála pomoci. (A shift of the noun We have chosen a nondeterministic model to enable vari-
úkolem ‘task’ next to the preposition.) ous sequences of reductions. This can serve for the verifi-
→delete * se bála pomoci. (Unfortunately, the next reduc- cation of the (in)dependency between the individual parts
tion must remove the prepositional group s úkolem ‘with of a sentence, as was sketched in Section 2.
task’ making the sentence again ungrammatical due to the A pRL-automaton M is (in general) a nondeterministic
clitic on the sentence first position.) machine with a finite alphabet Γ, a head q (window of size
→shi f t bála se pomoci. (Now we can repair the sentence 1) working on a flexible tape delimited by the left sentinel
by shifting the verb bála to the left.) c and the right sentinel $ (c, $ 6∈ Γ), and two finite sets
→delete bála se. (The reduction of the word pomoci ‘help’ of restarting meta-instructions R(M) and accepting meta-
ends the process.) instructions A(M), respectively. Such an automaton makes
Similarly for the second sequence of reductions and shifts. use of k pebbles p1 · · · , pk .
Regardless of the selected sequence, we must apply at least Let us first describe informally the way how an pRL-
two shifts in the course of AR. automaton works. Each of its finite computations consists
Remark: Note that we limit our observations to simple of certain phases called cycles, and a last – halting – phase
sentences, i.e., to sentences with a single clause. The rea- called a tail. In each cycle, the automaton performs two
son is obvious, complex sentences might blur the whole passes through the tape: during the first pass, it marks se-
picture by bringing additional phenomena into the play. lected symbols of a processed sentence with pebbles; then
For example, a coordination of clauses might completely during the second pass, it performs its editing operations
change the total number of shifts in a complex sentence re- described by meta-instructions from R(M); the operations
gardless of the phenomena contained in individual clauses. can be applied (only) on the symbols marked by pebbles.
In general, each (coordinated) clause can induce a shift in In each (accepting) tail, the automaton marks all symbols
the course of AR, thus the overall number of shifts cannot by pebbles – according to a meta-instruction from A(M) –,
be bounded. halts, and accepts the analyzed sentence.
3.1.1 Restarting meta-instructions. Each cycle of the
3 Restarting Automaton with a Structured pRL-automaton M is controled by a single restarting meta-
Output instruction IR ∈ R(M) of the form
IR = (E0 , I1 , . . . Is ; O p ; Restart) (1)
The crucial issue of the application of a word-order shift
in the process of AR is actually identifying WHAT should where:
be shifted WHERE. In order to model the whole process – each Ii is an instruction of the form (ai , Ei ), 1 ≤ i ≤ s,
by means of a special kind of an automaton, we have to – each Ei is a regular language over Γ; Ei is interpreted as
use special markers – pebbles, which mark the possible the i-th context of IR (the contexts are usually represented
targets of shift locations. For this purpose we are going by regular expressions);
to define a restarting automaton with a finite set of special – each instruction Ii marks the symbol ai ∈ Γ from the tape
meta-instructions using pebbles – an pRL-automaton. The with the pebble pi within the first pass;
automaton with pebbles was originally introduced in [15] – O p = {o1 , · · · , o p } is an ordered set of editing operations,
in order to define dependency output structures, and we o j ∈{dl[i], wr[i, b], sh[i, l]|1 ≤ i, l ≤ s, i 6= l, b ∈ Γ},
are going to enhance its abilities with the shift operation. – o j is the j-th editing operation performed in the second
We proceed in several steps. First, a restarting automa- pass:
ton with pebbles is enhanced with a shift operation (Sec- — if o j = dl[i] then it deletes the symbol ai ,
tion 3.1). Second, a structured output is added (Section — if o j = wr[i, b] then it rewrites ai by b,
3.2). Finally, a computation of such enhanced automaton — if o j = sh[i, l] then it shifts ai to the position behind
is described (Section 3.3). al .
We require a ‘uniqueness’ of operations on a single sym-
bol, i.e., if dl[i] ∈ O p then O p does not contain the opera-
3.1 Restarting Automaton with the Shift Operation tions wr[i, b], sh[i, l] for any b, l.
Operating on Strings Performing a meta-instruction: For an (input) sentence
w ∈ Γ∗ , we define the tape inscription cw$, and a reduction
Here we present a class of nondeterministic pRL-automata w `cIR w0 . When trying to execute a cycle C by performing
that are suitable for modeling AR – these automata allow the meta-instruction IR , it starts with the tape inscription
for checking the whole input sentence (and marking se- cw$, M will get stuck (and so reject) if w does not permit a
lected words with pebbles) prior to any changes. It re- factorization of the form w = v0 a1 v1 a2 . . . vs−1 as vs (vi ∈ Ei
sembles a linguist who can read the whole sentence first, for all i = 0, . . . , s). On the other hand, if w permits factor-
and then can reduce the sentence in a correct way. Thus izations of this form, then one of them is (nondeterminis-
he/she makes correct steps of the analysis by reduction. tically) chosen.
Formalization of Word-Order Shifts by Restarting Automata 5
The automaton processes the input word in two passes: serve for building the structured output, as it is described
1. During the first pass of C, M puts the pebble pi on in the following sections.
each ai (this corresponds to the instruction Ii , for each i, The notation u `cM v (a reduction of u to v by M) denotes
1 ≤ i ≤ s). a reduction performed during a cycle of M that begins with
2. During the second pass of C controlled by the or- the tape inscription cu$ and ends with the tape inscription
∗
dered set of operations O p , the tape inscription cw$ is cv$; the relation `cM is the reflexive and transitive closure
transformed (reduced) into a new tape inscription w0 = of `cM . By REM(M) we denote the set of reductions per-
v0 r1 v1 · · · vs−1 rs vs , where 1 ≤ i ≤ s: formed by M.
A string w ∈ Γ∗ is accepted by M, if there is an accept-
• In the second pass of C, M performs its operations in ing computation which starts with the tape inscription cw$
the prescribed order o1 , o2 , · · · , o p . and ends by executing an accept operation. By L(M) we
denote the language consisting of all words accepted by
• ri = λ if there is a deleting operation o j ∈ O p such M; we say that M recognizes (accepts) language L(M).2
that o j = dl[i];
i.e., ai is deleted during the cycle C; Note that we limit ourselves only to such combinations
of operations that are adequate (and necessary) for known
• ri = b if there is a rewriting operation o j ∈ O p such linguistic examples.
that o j = wr[i, b]; Example: Let us illustrate the notions of restarting and
i.e., ai is rewritten with b during the cycle C; accepting meta-instructions on the analysis of sentence (1)
from Section 2. This example formalizes the AR of the
• ri = λ and r j = al ai if there is a shifting operation
sentence Petr se bojí o otce. ‘Peter fears for his father.,
o j ∈ O p such that o j = sh[i, l];
namely the left branch of its AR (see the scheme in Section
i.e., ai is shifted behind the symbol marked by the
2). The respective pRLe -automaton M is described by two
pebble pl during the cycle C;
restarting meta-instructions IR1 and IR2 , and one accepting
• ri = ai if there is no operation o j ∈ O p applicable on meta-instruction IA , namely:
ai . IR1 = (E0 , I11 , I21 , I31 ; O12 ; Restart)
(Note that such an ai may – together with symbols E0 = {Petr se}, I11 = ( bojí , {λ })
where some of above mentioned operation is applied 1
O2 = {dl[2], dl[3]}, I21 = ( o , {λ })
– create the output structure, see the following sec- I31 = ( otce , {·})
tion, and thus they must be marked with pebbles.) IR2 = (E0 , I1 , I2 , I3 ; O2 ; Restart)
2 2 2 2
E0 = {λ }, I12 = ( Petr, {λ })
• At the end of each cycle, the Restart operation is per- O22 = {dl[1], sh[2, 3]}, I22 = ( se, {bojí})
formed: all the pebbles are removed from the new I32 = ( bojí , {λ })
tape inscription w0 , and the head is placed on the left IA = ( bojí , se, . , Accept)
sentinel. The computation consists of two cycles. Within the first
cycle described by the meta-instruction IR1 , the instruc-
Of course, we can delete, rewrite or shift neither the left tions I11 , I21 and I31 put pebbles p1 , p2 and p3 on the sym-
sentinel c nor the right sentinel $. It is required that during bols containing the words bojí (with the left context Petr
a cycle, M executes at least one delete operation. se and empty right context), o, and otce, respectively; the
If no further cycle is performed, each finite (accepting) operations dl[2] and dl[3] delete the word o (marked with
computation necessarily finishes in a tail performed ac- the pebble p2 ) and otce (marked with the pebble p3 ), re-
cording to an accepting meta-instruction. spectively. Then the automaton restarts (in particular, all
pebbles are removed). Similarly in the second cycle (meta-
3.1.2 Accepting meta-instructions. Tails of accepting instruction IR2 ), the instructions I12 , I22 and I32 mark the re-
computations are described by a set accepting meta- spective words and then operation dl[1] deletes the word
instructions A(M), each of the form: Petr (marked with p1 ) and the operation sh[2, 3] shifts the
word se with the pebble p2 behind the word bojí (with the
IA = (a1 , . . . , as , Accept), (2) pebble p3 ). The accepting instruction IA just marks the
remaining words bojí and se with pebbles.
where ai are symbols from Γ. The following property – obviously ensured by pRL-
Performing a meta-instruction: The tail performed by automata – has a crucial role in our applications of restart-
the meta-instruction IA starts with the inscription on the ing automata.
tape cz$; if z = a1 · · · as , then M marks each symbol ai
with the pebble pi , and accepts z (and the whole compu- Weak Correctness Preserving Property. Any pRL-auto-
tation as well). Otherwise, the computation halts with re- maton M is weakly correctness preserving, i.e., (for all
jection. Note that only operations distributing pebbles are 2 Note that language L(M) accepted by the automaton M is the same
allowed within an accepting meta-instruction – they will language as LC (M) in [15].
6 M. Lopatková, M. Plátek
u, v ∈ Γ∗ ) • U p contains the root of G of the form [i, ai ] (unless the
∗
v ∈ L(M) and u `cM v imply that u ∈ L(M). root is already contained in Uw ).
Our goal is to model the analysis by reduction by automata
with the following stronger property: 2. An edge (u, v) ∈ H represents:
Correctness Preserving Property. A pRL-automaton • either deleting: if dl[i] ∈ O p then the edge has the
M is correctness preserving, if (for all u, v ∈ Γ∗ ) u ∈ form u = [i, ai ], and v = [ j, a j ] for some j 6= i ( j is in-
∗
L(M) and u `cM v imply that v ∈ L(M). terpreted as a position of respective governing node);
3.2 Restarting Automaton with the Shift Operation • or rewriting: if wr[i, b] ∈ O p then the edge has the
Enhanced with Structured Output form u = [i, ai ], and v = [i, b] (i.e., u represents the
original symbol ai and v the rewritten)
In this section, we introduce enhanced restarting automata
with structured output – the so-called pRLe -automata.
During their enhanced computations, these automata build 3.2.2 Enhanced accepting meta-instruction IA .
– with the help of pebbles – so called DR-structures, i.e., Let IA be an accepting instruction of the form IA =
graphs consisting of items representing individual occur- (a1 , . . . , as , Accept) (i.e., as it is introduced in Section 3.1,
rences of symbols (words) in the input sentence and di- X = A). Then a corresponding enhanced accepting meta-
rected edges between them. instruction has a form IEA = (IA , G), where G = (U, H)
In order to represent a structured output by an pRLe - is an enhancing graph; the symbols a1 , . . . , as are pebbled
automaton, the items of flexible tape (representing just and they correspond to the nodes {[1, a1 ], [2, a2 ] . . . , [s, as ]}
sentinels and symbols (= words) of a processed sentence) of U. For each edge h = (u, v) ∈ H, we suppose that
are enriched with two integers denoting horizontal and ver- u = [ai , i], v = [a j , j] (1 ≤ i, j ≤ s and i 6= j).
tical position of a respective word in the resulting DR- Example: Let us return to the analysis of sentence (1)
structure. Petr se bojí o otce. ‘Peter fears for his father.’, see Section
An pRLe -automaton is specified in two steps: First, in- 2. In Section 3.1, we have already presented two restart-
structions of an pRL-automaton are enhanced with graphs ing instructions IR1 and IR2 , and one accepting instruction
(Sections 3.2.1 and 3.2.2). Second, an application of these IA . Here we enrich these instructions with a graph de-
enhanced instructions (i.e., its computations) are specified scribing the (part of) resulting DR-structures – the respec-
with the help of DR-structures (Sections 3.2.3 and 3.3). tive pRLe -automaton Me is described by enhanced instruc-
A pRLe -automaton Me = (Γ, c, $, ER(Me ), EA(Me )) tions IER1 = (IR1 , G1 ), IER2 = (IR2 , G2 ), and IEA = (IA , GA ),
consists of an alphabet Γ, sentinels c, $ 6∈ Γ, a set of en- namely:
hanced restarting meta-instructions ER(Me ), and a set of G1 = (U1 , H1 ) U1 = {[1, bojí ], [2, o], [3, otce]}
enhanced accepting meta-instructions EA(Me ). H1 = {([2, o], [1, bojí ]), ([3, otce], [2, o])}
An enhanced meta-instruction is a pair IEX = (IX , G), G2 = (U2 , H2 ) U2 = {[1, Petr], [3, bojí ]}
where IX is a (restarting or accepting) meta-instruction H2 = {([1, Petr], [3, bojí ])}
of a pRL-automaton, and G is a directed acyclic graph GA = (UA , HA ) UA = {[1, bojí ], [2, se], [3, ·]}
G = (U, H). The graph G represents the required structure HA = {([2, se], [1,bojí ]), ([3, ·], [1,bojí ])}
of symbols processed during the application of the meta-
instruction IX . In this paper we request G to be a rooted
tree. (This restriction ensures linguistically adequate out- 3.2.3 DR-structures.
put structures.) In this paragraph, we introduce so-called DR-structures
(Delete Rewrite structures), which serve for the represen-
tation of output structures of restarting automata. A DR-
3.2.1 Enhanced restarting meta-instruction IER . structure captures syntactic units (words and their cate-
Let IR be a restarting meta-instruction of the form (1) intro- gories used in an input sentence and also in its reduced
duced in section 3.1.1. We define the corresponding graph forms) as nodes of a graph and their mutual syntactic re-
G = (U, H) in the following way: lations as edges; moreover, word order is represented by
1. The set of nodes U consists of three disjunct subsets Un , means of total ordering of the nodes.
Uw , and U p : A DR-structure is a directed acyclic graph D = (V, E),
where V is a finite set of nodes, and E ⊂ V ×V is a finite
• Un = {[i, ai ] | dl[i] ∈ O p or wr[i, b] ∈ O p , 1 ≤ i ≤ s}.
set of edges. A node u ∈ V is a tuple u = [i, j, a], where a is
We can see that Un covers all (original) words which
a symbol (word) assigned to the node, and i, j are natural
are deleted or rewritten words within IR (ai ∈ Γ is the
numbers, i represents the horizontal position of the node
word marked with a pebble pi ).
u (i.e., the word order in an input sentence), j represents
• Uw = {[i, b] | wr[i, b] ∈ O p , 1 ≤ i ≤ s}}. The set Uw the vertical position of u (it is equal to a number of rewrit-
represents words resulting from the rewritten opera- ings of a word on a particular horizontal position). Each
tions within IR . edge h = (u, v) ∈ E, where u = [iu , ju , a] and v = [iv , jv , b]
Formalization of Word-Order Shifts by Restarting Automata 7
for some non-negative integers iu , iv , ju , jv and a, b ∈ Γ, is continues by performing several cycles, and it ends by a
either tail.
A cycle means an application of an enhanced restart-
• oblique edge iff iu 6= iv ; ing meta-instruction on a given configuration, resulting in
such edges are interpreted as representing syntactic a new configuration. During each cycle of C, some items
relations between respective symbols (words), or of the tape content are deleted, rewritten, or shifted (as in
a cycle of the original automaton without structures); fur-
• vertical edge iff iu = iv and jv = ju + 1;
ther, some edges and (rewritten) nodes are added to the
such edges are interpreted as representing a rewriting
of a symbol (word) on the respective position iu .
DR-structure of the corresponding configuration, in accor-
dance with the graph attached to the respective enhanced
We say that D = (V, E) is a DR-tree if the graph D is a meta-instruction (see below for more formal description).
rooted tree (i.e., all maximal paths in D end in its single A tail consists in an application of an enhanced accept-
root). ing meta-instruction – it results in an acceptance of a con-
figuration; further, some edges are added to the current
Remark: It is important to say that a DR-structure pre-
DR-structure in accordance with a graph attached to this
serves word order of an original sentence, i.e., the order of
enhanced meta-instruction.
nodes in DR-structure (corresponding to words and their
Let us stress that during a computation, some nodes and
categories) is not affected by (possible) shifts. However,
edges may be added to the DR-structures of the computa-
shifts affect the way how a DR-structure corresponds to
tion, and never removed. At the end of each computation,
individual reductions of the automaton – an information
we obtain a DR-tree covering the whole input sentence.
of both original and changed positions of individual words
(and their categories) must be recorded during the compu-
tation. 3.3.1 Application of an enhanced restarting meta-
instruction IER .
Let IER = (IR , G) be an enhanced restarting instruction in
3.3 Computations and (Structured) Languages by the previously defined form, with G = (U, H) (see Section
pRLe -automata 3.2). An application of IER on an enhanced configuration
Cw = (Tw , Dw ) of a word w results in a new configuration
Based on the definition, it is clear that for a pRLe -
Cw0 = (Tw0 , Dw0 ). The application consists in the following
automaton Me , a reduction relation `Me can be defined in
steps:
the same way as the reduction relation `M of the corre-
sponding pRL-automaton M; further, Me accepts the same 1. Choosing a factorization of w of the form w =
language as the M (leaving aside output DR-structures), v0 a1 v1 a2 . . . vs−1 as vs such that vi ∈ Ei for all i =
and we can see that a set of reductions REM(Me ) = 0, . . . , s (see the form of a restarting meta-instruction
REM(M), as well. (1)). Let us consider that the items from Tw contain-
Similarly as in [15], computation of an pRLe -automaton ing the symbols a1 , · · · , as are pebbled.
Me is characterized by sequences of its configurations. A If w does not permit any factorization of this form,
configuration is a pair of the form Cw = (Tw , Dw ) , where then IER cannot be applied on the configuration Cw .
Tw (so called tape content of Cw ) is a string of items rep-
resenting current sentence w on the tape and Dw = (V, E) 2. Transforming the tape content Tw containing the sen-
is a DR-structure (see above). The items of Tw create a tence w into the tape Tw0 containing the sentence
subset of V such that Tw contains just all roots of individ- w0 = v0 r1 v1 · · · vs−1 rs vs ; ri (1 ≤ i ≤ s), are described
ual components (trees) of the DR-structure Dw (thus each in section 3.1). The transformation of Tw to Tw0 keeps
item [i, j, xi ] of Tw consists of a word position i (i.e., the the following rules:
horizontal index), a symbol xi on this position (word of
• each item vi ∈ Tw (1 ≤ i ≤ s) which does not
the original sentence), and the number of its rewritings j).
undergo an editing operation is copied to Tw0 ,
Moreover, Tw contains at most one item for each horizontal
position i. • no deleted item from Tw is transferred to Tw0 ,
Note that – contrary to [15] – the items of Tw are or- and
dered; however, their order need not reflect the original • each item [ki , ji , ai ] from Tw that corresponds to
word order of an input sentence as the items (triples) may a rewritten symbol ai (hence oi = wr[i, b], b ∈ Γ,
be re-ordered by a shift operation. 1 ≤ i ≤ s ) is replaced by [ki , ji + 1, b] in Tw0 ;
An (accepting) computation C of Me on an input sen- • the shift of an item [i, j, ai ] is performed in such
tence w starts in the initial configuration Cwin = (Twin , Dinw ): a way that the indices i, j remain unchanged in
for the given sentence w = x1 . . . xn (x j ∈ Γ, 1 ≤ j ≤ n), Tw0 .
the initial tape content consists in the string of items Twin =
[1, 0, x1 ] · · · [n, 0, xn ], and the DR-structure Din in /
w = (Vw , 0), 3. All edges and nodes from the DR-structure Dw are
in
where Vw = {[1, 0, x1 ], · · · , [n, 0, xn ]}. The computation transferred into the new DR-structure Dw0 .
8 M. Lopatková, M. Plátek
4. For each edge e ∈ H, a new edge is inserted into the Let AC(Me ) denote the set of all accepting computations
new DR-structure Dw0 = (V 0 , E 0 ): of the pRLe -automaton Me . Then the DR-language of Me
is the set DR(Me ) = {DR(C ) | C ∈ AC(Me )}.
• if e = ([i, ai ], [r, ar ]) is a deleting edge from
Remark. From the linguistic point of view, DR(Me )
H (1 ≤ r ≤ s), and [ki , ji , ai ], [kr , jr , ar ] ∈ Tw
should be considered as a set of (shallow) dependency-
are the items covering the pebbled symbols ai
based syntactic trees / analyses computed by the automa-
and ar , respectively, then an oblique edge eo =
ton Me .
([ki , ji , ai ], [kr , jr , ar ]) is inserted into Dw0 (i.e.,
into E 0 ). Example: Let us return to the example (1), section 2,
Petr se bojí o otce. ‘Peter fears for his father.’ In
• if e = ([i, ai ], [i, bi ]) is a rewriting edge and
Sections 3.1.2 and 3.2.2, the pRLe -automaton Me – de-
[ki , ji , ai ] ∈ Tw is the item covering the pebbled
scribed by two restarting meta-instructions and one ac-
symbol ai , then a vertical edge ev is inserted into
cepting meta-instruction together with the graphs enhanc-
E 0 : ev leads from the item [ki , ji , ai ] to the item
ing these meta-instructions – was presented. The sequence
[ki , ji + 1, bi ].
S = IER1 , IER2 , IEA performs the left branch of the analysis
At the same time the node [ki , ji + 1, bi ] is added
by reduction. In the course of the corresponding computa-
to the set V 0 .
tion, the DR-tree D3 is gradually constructed.
We say that the configuration Cw0 can be reached in one Now we can present the accepting computation C =
(restarting) step from the configuration Cw by Me (using C0 ,C1 ,C2 ,C3 on the sentence (1) determined by the se-
the instruction IER ) and denote it by Cw |=IMERe Cw0 , or simply quence of meta-instructions S. Let Cin = (T in , Din ), C1 =
by Cw |=Me Cw0 . (T1 , D1 ), C2 = (T2 , D2 ), C3 = (T3 , D3 ), C0 is the initial con-
figuration of C , C3 is the accepting configuration. Further
we gradually describe T in , T1 , T2 , T3 , and Din , D1 , D2 , D3 ,
3.3.2 Application of an enhanced accepting meta- where D3 = DR(C ).
instruction IEA . T in = [1, 0, Petr][2, 0, se][3, 0, bojí ][4, 0, o][5, 0, otce][6, 0, ·]
Let IEA = (I, G) be an enhanced accepting meta- Din = (V in , 0)
/
instruction, where I = (a1 , . . . , as , Accept) and G = (U, H). V in = {[1, 0, Petr], [2, 0, se], [3, 0, bojí ], [4, 0, o], [5, 0, otce][6, 0, ·]}
Let Cw = (T, D) be an enhanced configuration of Me with —————–
the tape content T = [i1 , j1 , a1 ], · · · , [is , j j , as ] covering the T1 = [1, 0, Petr][2, 0, se][3, 0, bojí ][6, 0, ·]
word w= a1 · · · as . Then the application of IEA on the con- D1 = (V in , E1 )
figuration Cw results in a new configuration Cw0 = (T 0 , D0 ), E1 = {([4, 0, o], [3, 0, bojí ]), ([5, 0, otce], [4, 0, o])}
where D0 = (V 0 , E 0 ): —————–
1. T 0 = [i1 , j1 , a1 ], · · · , [is , j j , as ] = T ; T2 = [3, 0, bojí ][2, 0, se][6, 0, ·]
D2 = (V in , E1 ∪ E2 )
2. all edges and nodes from the DR-structure D are E2 = {([1, 0, Petr], [3, 0, bojí ])}
transferred into the new DR-structure D0 ; —————–
T3 = T2
3. moreover, for each edge e = ([r, ar ], [s, at ]) ∈ H the D3 = (V in , E1 ∪ E2 ∪ E3 )
new edge ([ir , jr , air ], [it , jt , ait ]) is inserted into D0 . E3 = {([2, 0, se], [3, 0, bojí ]), ([6, 0, ·], [3, 0, bojí ])}
Similarly as in the previous case, we say that the con- We can see that the presented example is very simple –
figuration Cw0 can be reached in one (accepting) step from the context languages from the instructions contain always
the configuration Cw by Me using the instruction IEA , and one string (sometimes the empty one λ ). Moreover, we
denote it by C |=IMEAe C0 . have not used the operation wr[i] at all. That caused that
all items used in C have their vertical index equal to 0.
We can finally define an accepting computation of an We can notice that D3 is a formalization of the depen-
enhanced pRLe -automaton and subsequently also a DR- dency tree from the example (1). (Let us note that a com-
language consisting from the output DR-structures. putation performing the another branch of AR should cre-
Let C = C0 ,C1 , . . . ,Ck be a sequence of configurations ate the same DR-tree.)
such that
– C0 is the initial configuration for a word w, – Ci |=IMi e Ci+1
holds for all i = 0, . . . , k − 1, Observations. Let us finally (and just informally) formu-
– Ii are restarting instructions for all i = 0, . . . , k − 2, late some observations concerned the presented notions.
– Ik−1 is an accepting instruction. 1. The classes of introduced languages, sets of reductions,
Then we say that C is an accepting computation of Me , and DR-languages create infinite hierarchies with respect
the word w is accepted by Me , and the DR-structure Dk to the number of used pebbles. We are able to prove ex-
(from the last configuration Ck = (Tk , Dk )) is the output actly such propositions.
DR-structure of the computation C . We write DR(C ) = 2. On the other hand, we can observe that very few peb-
Dk . bles (six, according to our preliminary hypothesis) suffice
Formalization of Word-Order Shifts by Restarting Automata 9
to analyze adequately any sentence from the Prague De- References
pendency Treebank (see [2]). It means that the complexity
of analysis by reduction of natural languages is not too [1] Gerdes, K., Kahane, S.: Defining dependencies (and con-
hight; however, it is not too trivial. stituents). In: Gerdes, Hajičová, Wanner (eds.) Proceedings
of Depling 2011. pp. 17–27. Barcelona (2011)
3. In a similar way, we can see that the number of used
[2] Hajič, J., Panevová, J., Hajičová, E., Sgall, P., Pajas, P.,
shifts in one cycle does not need to exceed one. Štěpánek, J., Havelka, J., Mikulová, M., Žabokrtský, Z.,
4. As far as we can foresee, the use of rewritings within Ševčíková-Razímová, M.: Prague Dependency Treebank
the analysis by reduction is forced only by two linguistic 2.0. Linguistic Data Consortium, Philadelphia (2006)
phenomena: coordinations and noun groups with numer- [3] Hajičová, E., Havelka, J., Sgall, P., Veselá, K., Zeman, D.:
als. Moreover, the number of rewritings in one cycle does Issues of Projectivity in the Prague Dependency Treebank.
not need to exceed one. The Prague Bulletin of Mathematical Linguistics 81, 5–22
5. Further, it not hard to see that the shift operation can- (2004)
not be simulated by rewritings within the class of pRLe - [4] Holan, T., Kuboň, V., Oliva, K., Plátek, M.: On Complex-
automata, due to the limited number of rewritings in en- ity of Word Order. Les grammaires de dépendance – Traite-
ment automatique des langues 41(1), 273–300 (2000)
coded in meta-instructions.
[5] Kuboň, V., Lopatková, M.: A case study of a free word
6. Finally, the measure of word-order complexity from [4] order (manuscript)
is not bounded by any natural number for DR-languages
[6] Kuboň, V., Lopatková, M., Plátek, M.: Studying formal
of pRLe -automata. properties of a free word order language. In: Youngblood,
G., McCarthy, P. (eds.) Proceedings of the FLAIRS 25 Con-
Conclusion and Perspectives ference. pp. 300–305. AAAI Press, Palo Alto (2012)
[7] Kunze, J.: Abhängigkeitsgrammatik, Studia Grammatica,
The main novelty of the work presented in the paper is an vol. XII. Akademie Verlag, Berlin (1975)
enhancement of a formal system in a way that makes it [8] Lopatková, M., Plátek, M., Kuboň, V.: Modeling Syntax
possible to capture adequately relations between linguistic of Free Word-Order Languages: Dependency Analysis by
notions in the course of (enhanced) analysis by reductions, Reduction. In: Matoušek, V. et al. (ed.) Proceedings of TSD
namely it describes dependency structures on the one side, 2005. LNCS, vol. 3658, pp. 140–147. Springer (2005)
and (complexity of) word order on the other side (for the [9] Lopatková, M., Plátek, M., Sgall, P.: Towards a Formal
clarity reason, we do not distinguish between input sym- Model for Functional Generative Description: Analysis by
bols and their categories in this paper). However, the in- Reduction and Restarting Automata. The Prague Bulletin
of Mathematical Linguistics 87, 7–26 (2007)
vestigation of these notions is complete neither from the
linguistic point of view, nor from the point of view of the [10] Marcus, S.: Sur la notion de projectivité. Zeitschrift fur
Mathematische Logik und Grundlagen der Mathematik
formal automata theory.
11(1), 181–192 (1965)
As for the future work, we plan to continue the research
[11] Mareček, D., Žabokrtský, Z.: Exploiting reducibility in un-
in the direction of combining more types of linguistic phe-
supervised dependency parsing. In: Proceedings of EMNL-
nomena which influence the degree of word order freedom CoNLL 2012. pp. 297–307. ACL (2012)
for natural languages as well as enhancing the proposed
[12] Mel’čuk, I.A.: Dependency in language. In: Gerdes, Ha-
formal system so that it would capture the added phenom- jičová, Wanner (eds.) Proceedings of Depling 2011. pp. 1–
ena. Further research of the presented type of automata 16. Barcelona (2011)
should present its properties in an exact way, as well. [13] Otto, F.: Restarting Automata and Their Relation to the
Further, we plan to propose a refinement of AR allow- Chomsky Hierarchy. In: Ésik, Z., Fülöp, Z. (eds.) Proceed-
ing to set constraints on possible reduction steps, namely a ings of DLT 2003. LNCS, vol. 2710, pp. 55–74. Springer,
constraint on projective reductions only, as the additional Berlin (2003)
experiments with a different or modified set of constraints [14] Otto, F.: Restarting Automata. In: Ésik, Z., Martin-Vide,
applied on the shift operation will probably provide new C., Mitrana, V. (eds.) Recent Advances in Formal Lan-
measures of word order freedom. An interesting research guages and Applications, Studies in Computational Intelli-
direction in this respect would be the investigation of pro- gence. vol. 25, pp. 269–303. Springer-Verlag, Berlin (2006)
jectivization of sentences prior to the individual reductions [15] Plátek, M., Mráz, F., Lopatková, M.: (In)Dependencies
of AR, which might completely change the picture and al- in Functional Generative Description by Restarting Au-
low for a more detailed investigation of an interplay be- tomata. In: Bordihn, H. et al. (ed.) Proceedings of NCMA
tween clitics and non-projective sentences, see also [5]. 2010. books@ocg.at, vol. 263, pp. 155–170. Österreichis-
Further investigation of the shift operation might also che Computer Gesellschaft, Wien, Austria (2010)
help to describe the relationship between different levels of [16] Plátek, M., Mráz, F., Lopatková, M.: Restarting Automata
formal description of natural languages in the Functional with Structured Output and Functional Generative Descrip-
Generative Description, namely between the tectogram- tion. In: Dediu A. et al. (ed.) Proceedings of LATA 2010.
LNCS, vol. 6031, pp. 500–511. Springer, Berlin Heidelberg
matical and analytical layer. This would strengthen the
(2010)
formal background of the theory.