The phenomenon of word order freedom plays an important role in syntactic analysis of many natural languages. This paper introduces a notion of a word order shift, an operation reflecting the degree of word order freedom of natural languages. The word order shift is an operation based upon word order changes preserving syntactic correctness, individual word forms, their morphological characteristics, and their surface dependency relations in a course of a stepwise simplification of a sentence, a so called analysis by reduction. The paper provides linguistic motivation for this operation and concentrates on a formal description of the whole mechanism through a special class of automata, so called restarting automata with the shift operation enhanced with a structured output, and their computations. The goal of this study is to clarify the properties of computations needed to perform (enhanced) analysis by reduction for free word order languages.
The phenomenon of word order freedom plays an important role in syntactic analysis of many natural languages. A relatively free word order combined with additional linguistic constraints constitutes a big challenge for a formal description of syntactic structures.Here we introduce a notion of a word order shift, an operation reflecting the degree of word order freedom of natural languages. The word order shift is a word order change preserving syntactic correctness, individual word forms, their morphological characteristics, and their surface dependency relations in the course of a stepwise simplification of a sentence under investigation, referred to as an analysis by reduction. Section 2 provides a linguistic motivation and informal description of the process.
Section 3 concentrates on a formal description of the whole mechanism through a special class of automata, so called restarting automata with the shift operation enhanced with structured output, pRLe-automata, and their computations.
Previous Work. The paper [
The analysis by reduction has served as a motivation for
new a family of automata, so called restarting automata,
see esp. [
Let us first describe the main ideas behind the method used
for sentence analysis. Analysis by reduction (AR) is based
on a stepwise simplification of an analyzed sentence, see
[
Let us stress the basic constraints imposed on the analysis by reduction: (i) the obvious constraint on preserving individual words (word forms), their morphological characteristics and/or their surface dependency relations; (ii) the constraint on preserving the correctness (i.e., a grammatically correct sentence must remain correct after its simplification); (iii) moreover, the application of the shift operation is limited only to cases when a shift is enforced by the correctness preserving principle of AR, i.e., a simple deletion would result in an incorrect word order and thus violate the principle (ii) above.
As a consequence of AR, it is possible to derive
formal dependency relations between individual sentence
members – pairs of governing and dependent nodes –
based on the possible order(s) of reductions, as it is
described in [
(1) Petr se bojí o otce.
‘Peter – REFL – fears – for – father’ ‘Peter fears for his father.’ The analysis by reduction can be summarized in the following scheme:
delet=e Z~Zdelete
delete? ?shift * se bojí. bojí se o otce.
shifZtZ~ =delete
bojí se.
Example (1) can be simplified in two ways (for simplicity, we do not make distinction between upper and lower case letters at the beginning of the sentence): (i) Either by simple deletion of the prepositional group o otce ‘for father’ (following the constraint on correctness of the simplified sentence, the pair of word forms must be deleted in a single step; see the left branch of the scheme). (ii) Or by deleting the subject Petr (the right part of the scheme); however, this simplification results in an incorrect word order variant starting with the clitic se (such position of a clitic is forbidden in Czech). Thus the shift operation correcting the word order is enforced →shi f t bojí se o otce.
As these possible reductions are independent of each other, we can conclude that the words Petr and o otce are independent – in other words, both of them depend on / modify a word remaining in the simplified sentence, i.e., the verb and its clitic bojí se.
Now, we can proceed in a similar way until we get the minimal correct simplified sentence→ bojí se.
We can notice that the order of reductions reflects the dependency relations in the corresponding dependency tree. Informally, the words are ‘cut from the bottom of the tree’ (in other words, the ‘pruning’ operation is applied on the tree); i.e., a governing node must be preserved in a simplified sentence until all its dependent words are deleted.1 In other words, AR makes it possible to identify the dependency tree for sentence (1): bojí
Z
JJZ Petr se o .
J J otce
The analysis by reduction has been designed to model a
human who is able to check the correctness of the analysis.
However, it is possible to model correct reductions on the
basis of large corpora of natural language sentences, see
[
As a follow-up experiment, we have decided to
supplement the data with ‘suspicious’ types of sentences
identified in previous work on Czech word order freedom, esp.
in [
Let us stress that the role of shifts in the course of the analysis by reduction was limited to cases where a shift ‘corrects’ word order of a simplified sentence – this concerns primarily the cases when an input sentence contains a clitic (as in sentences (1)-(2)).
(2) S teˇžkým se bála pomoci úkolem.
‘with – difficult – REFL – (she) was afraid – to help – task’ ‘With a difficulttask, she was afraid to help.’ Although the sample sentence is rather strange, the splitting of the prepositional group is a grammatical construction in Czech allowing to put a strong stress on an adjective modifying the noun and not on the whole prepositional group.
Due to the dependency relations present in the sentence there is only one possibility how to reduce it, the reduction of the adjective teˇžkým ‘difficult’. Unfortunately, it results in a syntactically incorrect word order: →delete * s se bála pomoci úkolem.
This situation can be corrected in two possible ways, let us focus on one of them:
1Let us note that some relations – e.g., the relation between a preposition 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 reduced in a single step (despite being represented as two nodes in a dependency tree); here we adhere to the practice used in the PDT annotation. →shi f t s úkolem se bála pomoci. (A shift of the noun úkolem ‘task’ next to the preposition.) →delete * se bála pomoci. (Unfortunately, the next reduction must remove the prepositional group s úkolem ‘with task’ making the sentence again ungrammatical due to the clitic on the sentence first position.) →shi f t bála se pomoci. (Now we can repair the sentence by shifting the verb bála to the left.) →delete bála se. (The reduction of the word pomoci ‘help’ ends the process.) Similarly for the second sequence of reductions and shifts. Regardless of the selected sequence, we must apply at least two shifts in the course of AR.
Remark: Note that we limit our observations to simple sentences, i.e., to sentences with a single clause. The reason is obvious, complex sentences might blur the whole picture by bringing additional phenomena into the play. For example, a coordination of clauses might completely change the total number of shifts in a complex sentence regardless of the phenomena contained in individual clauses. In general, each (coordinated) clause can induce a shift in the course of AR, thus the overall number of shifts cannot be bounded. 3
The crucial issue of the application of a word-order shift
in the process of AR is actually identifying WHAT should
be shifted WHERE. In order to model the whole process
by means of a special kind of an automaton, we have to
use special markers – pebbles, which mark the possible
targets of shift locations. For this purpose we are going
to define a restarting automaton with a finite set of special
meta-instructions using pebbles – an pRL-automaton. The
automaton with pebbles was originally introduced in [
We proceed in several steps. First, a restarting automaton with pebbles is enhanced with a shift operation (Section 3.1). Second, a structured output is added (Section 3.2). Finally, a computation of such enhanced automaton is described (Section 3.3). 3.1
Here we present a class of nondeterministic pRL-automata that are suitable for modeling AR – these automata allow for checking the whole input sentence (and marking selected words with pebbles) prior to any changes. It resembles a linguist who can read the whole sentence first, and then can reduce the sentence in a correct way. Thus he/she makes correct steps of the analysis by reduction. We have chosen a nondeterministic model to enable various sequences of reductions. This can serve for the verification of the (in)dependency between the individual parts of a sentence, as was sketched in Section 2.
A pRL-automaton M is (in general) a nondeterministic machine with a finite alphabetΓ, a head q (window of size 1) working on a flexible tape delimited by the left sentinel c and the right sentinel $ (c, $ 6∈ Γ), and two finite sets of restarting meta-instructions R(M) and accepting metainstructions A(M), respectively. Such an automaton makes use of k pebbles p1 · · · , pk.
Let us first describe informally the way how an pRLautomaton works. Each of its finite computations consists of certain phases called cycles, and a last – halting – phase called a tail. In each cycle, the automaton performs two passes through the tape: during the first pass, it marks selected symbols of a processed sentence with pebbles; then during the second pass, it performs its editing operations described by meta-instructions from R(M); the operations can be applied (only) on the symbols marked by pebbles. In each (accepting) tail, the automaton marks all symbols by pebbles – according to a meta-instruction from A(M) –, halts, and accepts the analyzed sentence.
pRL-automaton M is controled by a single restarting metainstruction IR ∈ R(M) of the form
IR = (E0, I1, . . . Is; Op; Restart) (1) where: – each Ii is an instruction of the form (ai, Ei), 1 ≤ i ≤ s, – each Ei is a regular language over Γ; Ei is interpreted as the i-th context of IR (the contexts are usually represented by regular expressions); – each instruction Ii marks the symbol ai ∈ Γ from the tape with the pebble pi within the first pass; – Op = {o1, · · · , op} is an ordered set of editing operations, o j ∈{dl[i], wr[i, b], sh[i, l]|1 ≤ i, l ≤ s, i 6= l, b ∈ Γ}, – o j is the j-th editing operation performed in the second pass: — if o j = dl[i] then it deletes the symbol ai, — if o j = wr[i, b] then it rewrites ai by b, — if o j = sh[i, l] then it shifts ai to the position behind al .
We require a ‘uniqueness’ of operations on a single symbol, i.e., if dl[i] ∈ Op then Op does not contain the operations wr[i, b], sh[i, l] for any b, l.
Performing a meta-instruction: For an (input) sentence w ∈ Γ∗, we define thetape inscription cw$, and a reduction c w0. When trying to execute a cycle C by performing w `IR the meta-instruction IR, it starts with the tape inscription cw$, M will get stuck (and so reject) if w does not permit a factorization of the form w = v0a1v1a2 . . . vs−1asvs (vi ∈ Ei for all i = 0, . . . , s). On the other hand, if w permits factorizations of this form, then one of them is (nondeterministically) chosen.
The automaton processes the input word in two passes: 1. During the first pass of C, M puts the pebble pi on each ai (this corresponds to the instruction Ii, for each i, 1 ≤ i ≤ s). 2. During the second pass of C controlled by the ordered set of operations Op, the tape inscription cw$ is transformed (reduced) into a new tape inscription w0 = v0r1v1 · · · vs−1rsvs, where 1 ≤ i ≤ s: • In the second pass of C, M performs its operations in the prescribed order o1, o2, · · · , op. • ri = λ if there is a deleting operation o j ∈ Op such that o j = dl[i]; i.e., ai is deleted during the cycle C; • ri = b if there is a rewriting operation o j ∈ Op such that o j = wr[i, b]; i.e., ai is rewritten with b during the cycle C; • ri = λ and r j = al ai if there is a shifting operation o j ∈ Op such that o j = sh[i, l]; i.e., ai is shifted behind the symbol marked by the pebble pl during the cycle C; • ri = ai if there is no operation o j ∈ Op applicable on ai. (Note that such an ai may – together with symbols where some of above mentioned operation is applied – create the output structure, see the following section, and thus they must be marked with pebbles.) • At the end of each cycle, the Restart operation is performed: all the pebbles are removed from the new tape inscription w0, and the head is placed on the left sentinel.
Of course, we can delete, rewrite or shift neither the left sentinel c nor the right sentinel $. It is required that during a cycle, M executes at least one delete operation.
If no further cycle is performed, each finite (accepting) computation necessarily finishes in a tail performed according to an accepting meta-instruction.
computations are described by a set accepting metainstructions A(M), each of the form:
IA = (a1, . . . , as, Accept), (2) where ai are symbols from Γ.
Performing a meta-instruction: The tail performed by the meta-instruction IA starts with the inscription on the tape cz$; if z = a1 · · · as, then M marks each symbol ai with the pebble pi, and accepts z (and the whole computation as well). Otherwise, the computation halts with rejection. Note that only operations distributing pebbles are allowed within an accepting meta-instruction – they will serve for building the structured output, as it is described in the following sections.
The notation u `cM v (a reduction of u to v by M) denotes a reduction performed during a cycle of M that begins with the tape inscription cu$ and ends with the tape inscription cv$; the relation `cM∗ is the reflexive and transitive closure of `cM. By REM(M) we denote the set of reductions performed by M.
A string w ∈ Γ∗ is accepted by M, if there is an accepting computation which starts with the tape inscription cw$ and ends by executing an accept operation. By L(M) we denote the language consisting of all words accepted by M; we say that M recognizes (accepts) language L(M).2
Note that we limit ourselves only to such combinations of operations that are adequate (and necessary) for known linguistic examples.
Example: Let us illustrate the notions of restarting and accepting meta-instructions on the analysis of sentence (1) from Section 2. This example formalizes the AR of the sentence Petr se bojí o otce. ‘Peter fears for his father., namely the left branch of its AR (see the scheme in Section 2). The respective pRLe-automaton M is described by two restarting meta-instructions IR1 and IR2 , and one accepting meta-instruction IA, namely:
IR1 = (E0, I11, I21, I31; O12; Restart)
E0 = {Petr se}, I11 = ( bojí , {λ })
O12 = {dl[
I31 = ( otce , {·})
IR2 = (E0, I12, I22, I32; O22; Restart)
E0 = {λ }, I12 = ( Petr, {λ })
O22 = {dl[
I32 = ( bojí , {λ })
IA = ( bojí , se, . , Accept)
The computation consists of two cycles. Within the first
cycle described by the meta-instruction IR1 , the
instructions I11, I21 and I31 put pebbles p1, p2 and p3 on the
symbols containing the words bojí (with the left context Petr
se and empty right context), o, and otce, respectively; the
operations dl[
The following property – obviously ensured by pRLautomata – has a crucial role in our applications of restarting automata.
Weak Correctness Preserving Property. Any
pRL-automaton M is weakly correctness preserving, i.e., (for all
2Note that language L(M) accepted by the automaton M is the same
language as LC(M) in [
v ∈ L(M) and u `cM∗ v imply that u ∈ L(M).
Our goal is to model the analysis by reduction by automata with the following stronger property:
M is correctness preserving, if (for all u, v ∈ Γ∗) u ∈ L(M) and u `cM∗ v imply that v ∈ L(M). 3.2
In this section, we introduce enhanced restarting automata with structured output – the so-called pRLe-automata. During their enhanced computations, these automata build – with the help of pebbles – so called DR-structures, i.e., graphs consisting of items representing individual occurrences of symbols (words) in the input sentence and directed edges between them.
In order to represent a structured output by an pRLeautomaton, the items of flexible tape (representing just sentinels and symbols (= words) of a processed sentence) are enriched with two integers denoting horizontal and vertical position of a respective word in the resulting DRstructure.
An pRLe-automaton is specified in two steps: First, instructions of an pRL-automaton are enhanced with graphs (Sections 3.2.1 and 3.2.2). Second, an application of these enhanced instructions (i.e., its computations) are specified with the help of DR-structures (Sections 3.2.3 and 3.3).
A pRLe-automaton Me = (Γ, c, $, ER(Me), EA(Me)) consists of an alphabet Γ, sentinels c, $ 6∈ Γ, a set of enhanced restarting meta-instructions ER(Me), and a set of enhanced accepting meta-instructions EA(Me).
An enhanced meta-instruction is a pair IEX = (IX , G), where IX is a (restarting or accepting) meta-instruction of a pRL-automaton, and G is a directed acyclic graph G = (U, H). The graph G represents the required structure of symbols processed during the application of the metainstruction IX . In this paper we request G to be a rooted tree. (This restriction ensures linguistically adequate output structures.)
Let IR be a restarting meta-instruction of the form (1) introduced in section 3.1.1. We define the corresponding graph G = (U, H) in the following way: 1. The set of nodes U consists of three disjunct subsets Un, Uw, and Up: • Un = {[i, ai] | dl[i] ∈ Op or wr[i, b] ∈ Op, 1 ≤ i ≤ s}.
We can see that Un covers all (original) words which are deleted or rewritten words within IR (ai ∈ Γ is the word marked with a pebble pi). • Uw = {[i, b] | wr[i, b] ∈ Op, 1 ≤ i ≤ s}}. The set Uw represents words resulting from the rewritten operations within IR. • Up contains the root of G of the form [i, ai] (unless the root is already contained in Uw). 2. An edge (u, v) ∈ H represents: • either deleting: if dl[i] ∈ Op then the edge has the form u = [i, ai], and v = [ j, a j] for some j 6= i ( j is interpreted as a position of respective governing node); • or rewriting: if wr[i, b] ∈ Op then the edge has the form u = [i, ai], and v = [i, b] (i.e., u represents the original symbol ai and v the rewritten)
Let IA be an accepting instruction of the form IA = (a1, . . . , as, Accept) (i.e., as it is introduced in Section 3.1, X = A). Then a corresponding enhanced accepting metainstruction has a form IEA = (IA, G), where G = (U, H) is an enhancing graph; the symbols a1, . . . , as are pebbled and they correspond to the nodes {[1, a1], [2, a2] . . . , [s, as]} of U . For each edge h = (u, v) ∈ H, we suppose that u = [ai, i], v = [a j, j] (1 ≤ i, j ≤ s and i 6= j).
Example: Let us return to the analysis of sentence (1) Petr se bojí o otce. ‘Peter fears for his father.’, see Section 2. In Section 3.1, we have already presented two restarting instructions IR1 and IR2 , and one accepting instruction IA. Here we enrich these instructions with a graph describing the (part of) resulting DR-structures – the respective pRLe-automaton Me is described by enhanced instructions IER1 = (IR1 , G1), IER2 = (IR2 , G2), and IEA = (IA, GA), namely:
G1 = (U1, H1) G2 = (U2, H2) GA = (UA, HA)
U1 = {[1, bojí ], [2, o], [3, otce]} H1 = {([2, o], [1, bojí ]), ([3, otce], [2, o])} U2 = {[1, Petr], [3, bojí ]} H2 = {([1, Petr], [3, bojí ])} UA = {[1, bojí ], [2, se], [3, ·]}
HA = {([2, se], [1,bojí ]), ([3, ·], [1,bojí ])}
In this paragraph, we introduce so-called DR-structures (Delete Rewrite structures), which serve for the representation of output structures of restarting automata. A DRstructure captures syntactic units (words and their categories used in an input sentence and also in its reduced forms) as nodes of a graph and their mutual syntactic relations as edges; moreover, word order is represented by means of total ordering of the nodes.
A DR-structure is a directed acyclic graph D = (V, E), where V is a finite set of nodes, andE ⊂ V × V is a finite set of edges. A node u ∈ V is a tuple u = [i, j, a], where a is a symbol (word) assigned to the node, and i, j are natural numbers, i represents the horizontal position of the node u (i.e., the word order in an input sentence), j represents the vertical position of u (it is equal to a number of rewritings of a word on a particular horizontal position). Each edge h = (u, v) ∈ E, where u = [iu, ju, a] and v = [iv, jv, b] for some non-negative integers iu, iv, ju, jv and a, b ∈ Γ, is either • oblique edge iff iu 6= iv; such edges are interpreted as representing syntactic relations between respective symbols (words), or • vertical edge iff iu = iv and jv = ju + 1; such edges are interpreted as representing a rewriting of a symbol (word) on the respective position iu . We say that D = (V, E) is a DR-tree if the graph D is a rooted tree (i.e., all maximal paths in D end in its single root).
Remark: It is important to say that a DR-structure preserves word order of an original sentence, i.e., the order of nodes in DR-structure (corresponding to words and their categories) is not affected by (possible) shifts. However, shifts affect the way how a DR-structure corresponds to individual reductions of the automaton – an information of both original and changed positions of individual words (and their categories) must be recorded during the computation. 3.3
pRLe-automata Based on the definition, it is clear that for a pRLeautomaton Me, a reduction relation `Me can be defined in the same way as the reduction relation `M of the corresponding pRL-automaton M; further, Me accepts the same language as the M (leaving aside output DR-structures), and we can see that a set of reductions REM(Me) = REM(M), as well.
Similarly as in [
Note that – contrary to [
An (accepting) computation C of Me on an input sentence w starts in the initial configurationCwin = (Twin, Diwn): for the given sentence w = x1 . . . xn (x j ∈ Γ, 1 ≤ j ≤ n), the initial tape content consists in the string of items Twin = [1, 0, x1] · · · [n, 0, xn], and the DR-structure Diwn = (Vwin, 0/ ), where Vwin = {[1, 0, x1], · · · , [n, 0, xn]}. The computation continues by performing several cycles, and it ends by a tail.
A cycle means an application of an enhanced restarting meta-instruction on a given configuration, resulting in a new configuration. During each cycle ofC, some items of the tape content are deleted, rewritten, or shifted (as in a cycle of the original automaton without structures); further, some edges and (rewritten) nodes are added to the DR-structure of the corresponding configuration, in accordance with the graph attached to the respective enhanced meta-instruction (see below for more formal description).
A tail consists in an application of an enhanced accepting meta-instruction – it results in an acceptance of a configuration; further, some edges are added to the current DR-structure in accordance with a graph attached to this enhanced meta-instruction.
Let us stress that during a computation, some nodes and edges may be added to the DR-structures of the computation, and never removed. At the end of each computation, we obtain a DR-tree covering the whole input sentence.
instruction IER.
Let IER = (IR, G) be an enhanced restarting instruction in the previously defined form, withG = (U, H) (see Section 3.2). An application of IER on an enhanced configuration Cw = (Tw, Dw) of a word w results in a new configuration Cw0 = (Tw0 , Dw0 ). The application consists in the following steps: 1. Choosing a factorization of w of the form w = v0a1v1a2 . . . vs−1asvs such that vi ∈ Ei for all i = 0, . . . , s (see the form of a restarting meta-instruction (1)). Let us consider that the items from Tw containing the symbols a1, · · · , as are pebbled.
If w does not permit any factorization of this form, then IER cannot be applied on the configurationCw. 2. Transforming the tape content Tw containing the sentence w into the tape Tw0 containing the sentence w0 = v0r1v1 · · · vs−1rsvs ; ri (1 ≤ i ≤ s), are described in section 3.1). The transformation of Tw to Tw0 keeps the following rules: • each item vi ∈ Tw (1 ≤ i ≤ s) which does not undergo an editing operation is copied to Tw0 , • no deleted item from Tw is transferred to Tw0 , and • each item [ki, ji, ai] from Tw that corresponds to a rewritten symbol ai (hence oi = wr[i, b], b ∈ Γ, 1 ≤ i ≤ s ) is replaced by [ki, ji + 1, b] in Tw0 ; • the shift of an item [i, j, ai] is performed in such a way that the indices i, j remain unchanged in 3. All edges and nodes from the DR-structure Dw are transferred into the new DR-structure Dw0 . 4. For each edge e ∈ H, a new edge is inserted into the new DR-structure Dw0 = (V 0, E0): • if e = ([i, ai], [r, ar]) is a deleting edge from H (1 ≤ r ≤ s), and [ki, ji, ai], [kr, jr, ar] ∈ Tw are the items covering the pebbled symbols ai and ar, respectively, then an oblique edge eo = ([ki, ji, ai], [kr, jr, ar]) is inserted into Dw0 (i.e., into E0). • if e = ([i, ai], [i, bi]) is a rewriting edge and [ki, ji, ai] ∈ Tw is the item covering the pebbled symbol ai, then a vertical edge ev is inserted into E0: ev leads from the item [ki, ji, ai] to the item [ki, ji + 1, bi].
At the same time the node [ki, ji + 1, bi] is added to the set V 0.
We say that the configurationCw0 can be reached in one (restarting) step from the configuration Cw by Me (using the instruction IER) and denote it by Cw |=IMERe Cw0 , or simply by Cw |=Me Cw0 .
instruction IEA.
Let IEA = (I, G) be an enhanced accepting metainstruction, where I = (a1, . . . , as, Accept) and G = (U, H). Let Cw = (T, D) be an enhanced configuration ofMe with the tape content T = [i1, j1, a1], · · · , [is, j j, as] covering the word w= a1 · · · as. Then the application of IEA on the configurationCw results in a new configurationCw0 = (T 0, D0), where D0 = (V 0, E0): 1. T 0 = [i1, j1, a1], · · · , [is, j j, as] = T ; 2. all edges and nodes from the DR-structure D are transferred into the new DR-structure D0; 3. moreover, for each edge e = ([r, ar], [s, at ]) ∈ H the new edge ([ir, jr, air ], [it , jt , ait ]) is inserted into D0.
Similarly as in the previous case, we say that the configurationCw0 can be reached in one (accepting) step from the configurationCw by Me using the instruction IEA, and denote it by C |=IMEAe C0.
We can finally define an accepting computation of an enhanced pRLe-automaton and subsequently also a DRlanguage consisting from the output DR-structures.
Let C = C0,C1, . . . ,Ck be a sequence of configurations such that I – C0 is the initial configuration for a wordw, – Ci |=Mi e Ci+1 holds for all i = 0, . . . , k − 1, – Ii are restarting instructions for all i = 0, . . . , k − 2, – Ik−1 is an accepting instruction.
Then we say that C is an accepting computation of Me, the word w is accepted by Me, and the DR-structure Dk (from the last configuration Ck = (Tk, Dk)) is the output DR-structure of the computation C . We write DR(C ) = Dk.
Let AC(Me) denote the set of all accepting computations of the pRLe-automaton Me. Then the DR-language of Me is the set DR(Me) = {DR(C ) | C ∈ AC(Me)}.
Remark. From the linguistic point of view, DR(Me) should be considered as a set of (shallow) dependencybased syntactic trees / analyses computed by the automaton Me.
Example: Let us return to the example (1), section 2, Petr se bojí o otce. ‘Peter fears for his father.’ In Sections 3.1.2 and 3.2.2, the pRLe-automaton Me – described by two restarting meta-instructions and one accepting meta-instruction together with the graphs enhancing these meta-instructions – was presented. The sequence S = IER1 , IER2 , IEA performs the left branch of the analysis by reduction. In the course of the corresponding computation, the DR-tree D3 is gradually constructed.
Now we can present the accepting computation C = C0,C1,C2,C3 on the sentence (1) determined by the sequence of meta-instructions S. Let Cin = (T in, Din), C1 = (T1, D1), C2 = (T2, D2), C3 = (T3, D3), C0 is the initial configuration ofC , C3 is the accepting configuration. Further we gradually describe T in, T1, T2, T3, and Din, D1, D2, D3, where D3 = DR(C ).
T in = [1, 0, Petr][2, 0, se][3, 0, bojí ][4, 0, o][5, 0, otce][6, 0, ·] Din = (V in, 0/) V in = {[1, 0, Petr], [2, 0, se], [3, 0, bojí ], [4, 0, o], [5, 0, otce][6, 0, ·]} —————– T1 = [1, 0, Petr][2, 0, se][3, 0, bojí ][6, 0, ·] D1 = (V in, E1) E1 = {([4, 0, o], [3, 0, bojí ]), ([5, 0, otce], [4, 0, o])} —————– T2 = [3, 0, bojí ][2, 0, se][6, 0, ·] D2 = (V in, E1 ∪ E2) E2 = {([1, 0, Petr], [3, 0, bojí ])} —————– T3 = T2 D3 = (V in, E1 ∪ E2 ∪ E3)
E3 = {([2, 0, se], [3, 0, bojí ]), ([6, 0, ·], [3, 0, bojí ])} We can see that the presented example is very simple – the context languages from the instructions contain always one string (sometimes the empty one λ ). Moreover, we 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 notice that D3 is a formalization of the
dependency tree from the example (1). (Let us note that a
computation performing the another branch of AR should
create the same DR-tree.)
Observations. Let us finally (and just informally)
formulate some observations concerned the presented notions.
1. The classes of introduced languages, sets of reductions,
and DR-languages create infinite hierarchies with respect
to the number of used pebbles. We are able to prove
exactly such propositions.
2. On the other hand, we can observe that very few
pebbles (six, according to our preliminary hypothesis) suffice
to analyze adequately any sentence from the Prague
Dependency Treebank (see [
The main novelty of the work presented in the paper is an enhancement of a formal system in a way that makes it possible to capture adequately relations between linguistic notions in the course of (enhanced) analysis by reductions, namely it describes dependency structures on the one side, and (complexity of) word order on the other side (for the clarity reason, we do not distinguish between input symbols and their categories in this paper). However, the investigation of these notions is complete neither from the linguistic point of view, nor from the point of view of the formal automata theory.
As for the future work, we plan to continue the research in the direction of combining more types of linguistic phenomena which influence the degree of word order freedom for natural languages as well as enhancing the proposed formal system so that it would capture the added phenomena. Further research of the presented type of automata should present its properties in an exact way, as well.
Further, we plan to propose a refinement of AR
allowing to set constraints on possible reduction steps, namely a
constraint on projective reductions only, as the additional
experiments with a different or modified set of constraints
applied on the shift operation will probably provide new
measures of word order freedom. An interesting research
direction in this respect would be the investigation of
projectivization of sentences prior to the individual reductions
of AR, which might completely change the picture and
allow for a more detailed investigation of an interplay
between clitics and non-projective sentences, see also [
Further investigation of the shift operation might also help to describe the relationship between different levels of formal description of natural languages in the Functional Generative Description, namely between the tectogrammatical and analytical layer. This would strengthen the formal background of the theory.