We study h-lexicalized two-way restarting automaton (hRLWW(i)) that can rewrite at most i times per cycle, for i ≥ 1. This model is useful for the study of lexical syntactic disambiguation (a notion from linguistic) through the formal notion of h-lexicalized syntactic analysis (hLSA). The hLSA is composed of a basic language and the corresponding h-proper language obtained from the basic language by mapping all non-input symbols on input symbols. We compare the properties of input languages, which are the languages traditionally considered in automata theory, to the properties of hLSA, i.e., to the properties of basic and h-proper languages. The basic and h-proper languages of hRLWW(i)automata fulfill the so called reduction correctness preserving property, but the input languages do not. While basic and h-proper languages are sensitive to the size of the read/write window, the input languages are not. Moreover, the basic and h-proper languages are sensitive to the number of rewrite steps per cycle. All that concerns a subclass of context-sensitive languages containing all contextfree languages (and most probably also the class of mildly context-sensitive languages [5]), i.e., a class suitable for studying and classifying syntactic and semantic features of natural languages. We work here also with the parametrized constraint of monotonicity. While using the monotonicity of degree one we can characterize the class of context-free languages, the monotonicity of higher degrees can model more complex syntactic phenomena of whole natural languages (like cross-serial dependencies [5]). Finally, we stress the constraint of weak cyclic form. It preserves the power of hRLWW(i)-automata, and it allows to extend the complexity results obtained for the classes of infinite languages also into the classes of finite languages (parametrized by the number of performed cycles). It is useful for classifications in computational and corpus linguistics, where all the (syntactic) observation are of the finite nature. The main technical novelty of the paper are the results about the sensitivity and insensivity of finite and infinite hLSA and corresponding languages by hRLWW(i)automata.
*The research is partially supported by VEGA 2/0165/16
This paper is a continuation of conference papers [13], [14], and the technical report [15]. Its motivation is to study lexical syntactic disambiguation, which is one of the basic concepts of several linguistic schools, including the schools working with dependency syntax. In order to give a theoretical basis for lexicalized syntax, a model of a restarting automaton that formalizes lexicalization in a similar way as categorial grammars (see, e.g., [1]) – the h-lexicalized restarting automaton (hRLWW), was introduced in [13]. This model is obtained from the two-way restarting automaton of [12] by adding a letter-to-letter morphism h that assigns an input symbol to each working symbol. Then the basic language LC(M) of an hRLWWautomaton M consists of all words over the working alphabet of M that are accepted by M, and the h-proper language LhP(M) of M is obtained from LC(M) through the morphism h.
Further, the set of pairs { (h(w), w) | w ∈ LC(M) }, denoted as LA(M), is called the h-lexicalized syntactic analysis (hLSA) by M. Thus, in this setting the auxiliary symbols themselves play the role of the tagged items. That is, each auxiliary symbol b can be seen as a pair consisting of an input symbol h(b) and some additional syntacticosemantic information (tags).
In contrast to the original hRLWW-automaton that uses exactly one rewrite in a cycle, here we study h-lexicalized restarting automaton (hRLWW(i)) allowing i ≥ 1 rewrites in a cycle. Our effort is to show that this model is suited for a transparent and sensitive modeling of the lexicalized syntactic analysis (lexical disambiguation) of natural languages (compare to [8, 9]).
The lexicalized syntactic analysis based on analysis by reduction is traditionally used to analyze sentences of natural languages with a high degree of word-order freedom like, e.g., Czech, Latin, or German (see, e.g., [8]). Usually, a human reader is supposed to understand the meaning of a given sentence before he starts to analyze it; h-lexicalized syntactic analysis based on the analysis by reduction simulates such a behavior by analysis of sentences, where morphological and syntactical tags have been added to the word-forms and punctuation marks (see, e.g., [9]). We recall some constraints that are typical for restarting automata, and we outline ways for new combinations of constraints. We establish infinite (two-dimensional) ascending hierarchies of language classes of h-proper languages for several subtypes of hRLWW(i)-automata with respect to the number of allowed cycles, the number of symbols deleted during each cycle or the length of scanning window of an automaton.
The paper is structured as follows. In Section 2, we introduce our model and its sub-models, we define the h-proper languages, and we state the reduction correctness preserving property and the reduction error preserving property for the basic languages of deterministic hRLWW-automata. In Section 3, we present the achieved results. The paper concludes with Section 4 in which we summarize our results and state some problems for future work. 2
relation, respectively. Further, we will sometimes use regular expressions instead of the corresponding regular languages. Finally, throughout the paper λ will denote the empty word.
We start with the definition of the two-way restarting automaton as an extension to the original definition from [12]. In contrast to [14], we do not introduce general h-lexicalized two-way restarting list automaton which can rewrite arbitrary many times during each cycle. Instead, we introduce two-way restarting automata which can rewrite at most i times per cycle, for an integer i ≥ 1. Definition 1. Let i be a positive integer. A two-way restarting automaton, an RLWW(i)-automaton for short, is a machine with a single flexible tape and a finitestate control. It is defined through an 9-tuple M = (Q, Σ, Γ, ¢, $, q0, k, i, δ ), where Q is a finite set of states, Σ is a finite input alphabet, and Γ(⊇ Σ) is a finite working alphabet. The symbols from Γ r Σ are called auxiliary symbols. Further, the symbols ¢, $ 6∈ Γ, called sentinels, are the markers for the left and right border of the workspace, respectively, q0 ∈ Q is the initial state, k ≥ 1 is the size of the read/write window, i ≥ 1 is the number of allowed rewrites in a cycle (see later), and δ : Q × PC ≤k → P((Q × {MVR, MVL, W(y), SL(v)}) ∪ {Restart, Accept, Reject}) is the transition relation. Here P(S) denotes the powerset of a set S,
PC ≤k = (¢ · Γk−1) ∪ Γk ∪ (Γ≤k−1 · $) ∪ (¢ · Γ≤k−2 · $) is the set of possible contents of the read/write window of M, v ∈ PC ≤k−1, and y ∈ PC ≤k.
Being in a state q ∈ Q and seeing u ∈ PC ≤k in its window, the automaton can perform seven different types of transition steps (or instructions): 1. A move-right step (q, u) −→ (q0, MVR) assumes that (q0, MVR) ∈ δ (q, u), where q0 ∈ Q and u ∈/ {λ , ¢} · Γ≤k−1 · $. This move-right step causes M to shift the window one position to the right and to enter state q0. 2. A move-left step (q, u) −→ (q0, MVL) assumes that (q0, MVL) ∈ δ (q, u), where q0 ∈ Q and u 6∈ ¢·Γ∗ ·{λ , $}. It causes M to shift the window one position to the left and to enter state q0. 3. An SL-step (q, u) −→ (q0, SL(v)) assumes that (q0, SL(v)) ∈ δ (q, u), where q0 ∈ Q, v ∈ PC ≤k−1, v is shorter than u, and v contains all the sentinels that occur in u (if any). It causes M to replace u by v, to enter state q0, and to shift the window by |u| − |v| items to the left – but at most to the left sentinel ¢ (that is, the contents of the window is ‘completed’ from the left, and so the distance to the left sentinel decreases, if the window was not already at ¢). 4. A W-step (q, u) −→ (q0, W(v)) assumes that (q0, W(v))∈ δ (q, u), where q0 ∈ Q, v ∈ PC ≤k, |v| = |u|, and that v contains all the sentinels that occur in u (if any). It causes M to replace u by v, and to enter state q0 without moving its window. 5. A restart step (q, u) −→ Restart assumes that Restart ∈ δ (q, u). It causes M to place its window at the left end of its tape, so that the first symbol it sees is the left sentinel ¢, and to reenter the initial state q0. 6. An accept step (q, u) −→ Accept assumes that
Accept ∈ δ (q, u). It causes M to halt and accept. 7. A reject step (q, u) −→ Reject assumes that Reject ∈ δ (q, u). It causes M to halt and reject.
A configuration of an RLWW(i)-automaton M is a word αqβ , where q ∈ Q, and either α = λ and β ∈ {¢} · Γ∗ · {$} or α ∈ {¢} · Γ∗ and β ∈ Γ∗ · {$}; here q represents the current state, αβ is the current contents of the tape, and it is understood that the read/write window contains the first k symbols of β or all of β if |β | < k. A restarting configuration is of the form q0¢w$, where w ∈ Γ∗; if w ∈ Σ∗, then q0¢w$ is an initial configuration . We see that any initial configuration is also a restarting configuration, and that any restart transfers M into a restarting configuration.
In general, an RLWW(i)-automaton M is nondeterministic, that is, there can be two or more steps (instructions) with the same left-hand side (q, u), and thus, there can be more than one computation that start from a given restarting configuration. If this is not the case, the automaton is deterministic.
A computation of M is a sequence C = C0,C1, . . . ,Cj of configurations of M, where C0 is an initial or a restarting configuration andCi+1 is obtained from Ci by a step of M, for all 0 ≤ i < j. In the following we only consider computations of RLWW(i)-automata which are finite and end either by an accept or by a reject step. Cycles and tails: Any finite computation of anRLWW(i)automaton M consists of certain phases. A phase, called a cycle, starts in a restarting configuration, the window moves along the tape performing non-restarting steps until a restart step is performed and thus a new restarting configuration is reached. If no further restart step is performed, any finite computation necessarily finishes in a halting configuration – such a phase is called atail. It is required that in each cycle RLWW(i)-automaton executes at most i rewrite steps (of type W or SL) but at least one SL-step. Moreover, it must not execute any rewrite step in a tail.
This induces the following relation of cycle-rewriting by M: u ⇒cM v iff there is a cycle that begins with the restarting configuration q0¢u$ and ends with the restarting configuration q0¢v$. The relation ⇒cM∗ is the reflexive and transitive closure of ⇒cM. We stress that the cycle-rewriting is a very important feature of an RLWW(i)automaton. As each SL-step is strictly length-reducing, we see that u ⇒cM v implies that |u| > |v|. Accordingly, u ⇒cM v is also called a reduction by M.
An input word w ∈ Σ∗ is accepted by M, if there is a computation which starts with the initial configuration q0¢w$ and ends by executing an accept step. By L(M) we denote the language consisting of all input words accepted by M; we say that M recognizes (or accepts) the input language L(M).
A basic (or characteristic) word w ∈ Γ∗ is accepted by M if there is a computation which starts with the restarting configurationq0¢w$ and ends by executing an accept step. By LC(M) we denote the set of all words from Γ∗ that are accepted by M; we say that M recognizes (or accepts) the basic (or characteristic1) language LC.
Finally, we come to the definition of the central notion of this paper, the h-lexicalized RLWW(i)-automaton. Definition 2. Let i be a positive integer. An h-lexicalized RLWW(i)-automaton, or an hRLWW(i)-automaton, is a pair Mb = (M, h), where M = (Q, Σ, Γ, ¢, $, q0, k, i, δ ) is an RLWW(i)-automaton and h : Γ → Σ is a letter-to-letter morphism satisfying h(a) = a for all input letters a ∈ Σ. The input language L(Mb) of Mb is simply the language L(M) and the basic language LC(Mb) of Mb is the language LC(M). Finally, we take LhP(Mb) = h(LC(M)), and we say that Mb recognizes (or accepts) the h-proper language LhP(Mb).
Finally, the set LA(Mb) = { (h(w), w) | w ∈ LC(M) } is called the h-lexicalized syntactic analysis (shortly hLSA) by Mb.
We say that for x ∈ Σ∗, LA(Mb, x) = { (x, y) | y ∈ LC(M), h(y) = x } is the h-syntactic analysis (lexicalized syntactic analysis) for x by Mb. We see that LA(Mb, x) is non-empty only for x from LhP(Mb).
1Basic languages were called characteristic languages in [10] and several other papers, therefore, here we preserve the original notation with subscript C.
L(Mb) ⊆ LhP(Mb) = h(LC(Mb)).
Let us note that h-lexicalized syntactic analysis formalizes the linguistic notion of lexical disambiguation. Each auxiliary symbol x ∈ Γ r Σ of a word from LC(Mb) can be considered as a disambiguated input symbol h(x).
The following two facts ensure the transparency for computations of hRLWW(i)-automata with respect to their basic and h-proper languages.
Fact 1. (Reduction Error Preserving Property) Let M be an hRLWW(i)-automaton. If u ⇒cM∗ v and u ∈/ LC(M), then v ∈/ LC(M).
Fact 2. (Reduction Correctness Preserving Property) Let M be a deterministic hRLWW(i)-automaton. If u ⇒cM∗ v and u ∈ LC(M), then v ∈ LC(M), and h(v) ∈ LhP(M). Notations. For brevity, the prefix det- will be used to denote the property of being deterministic. For any class A of automata, L (A) will denote the class of input languages that are recognized by automata from A, LC(A) will denote the class of basic languages that are recognized by automata from A, and LhP(A) will denote the class of hproper languages that are recognized by automata from A. LA(A) will denote the class of hLSA (h-lexicalized syntactic analyses) that are defined by automata fromA. For a natural number k ≥ 1, L (k-A), LC(k-A), LhP(k-A), and LA(k-A) will denote the class of input, basic, h-proper languages, and hLSA’s, respectively, that are recognized by those automata from A that use a read/write window of size k. 2.1
Further Refinements and Constraints on
RLWW-Automata (hRLWW-Automata) Here we introduce some constrained types of rewrite steps whose introduction is motivated by different type of linguistic reductions.
A delete-left step (q, u) → (q0, DL(v)) is a special type of an SL-step (q0, SL(v)) ∈ δ (q, u), where v is a proper (scattered) subsequence of u, containing all the sentinels from u (if any). It causes M to replace u by v (by deleting excessive symbols), to enter state q0, and to shift the window by |u| − |v| symbols to the left, but at most to the left sentinel ¢.
A contextual-left step (q, u) → (q0, CL(v)) is a special type of DL-step (q0, DL(v)) ∈ δ (q, u), where u = v1u1v2u2v3 and v = v1v2v3 such that v contains all the sentinels from u (if any). It causes M to replace u by v (by deleting the factors u1 and u2 of u), to enter state q0, and to shift the window by |u| − |v| symbols to the left, but at most to the left sentinel ¢.
An RLWW(i)-automaton is called RLW(i)-automaton if its working alphabet coincides with its input alphabet, that is, no auxiliary symbols are available for this automaton. Note that in this situation, each restarting configuration is necessarily an initial configuration. Within an abbreviation for an automata type, R denotes the use of moves to the right, L denotes the use of moves to the left, WW denotes the use of both input and working alphabets, and single W denotes the use of input alphabet only (the working alphabet coincides with the input alphabet).
An RLW(i)-automaton is called RLWD(i)-automaton if all its rewrite steps are DL steps, and it is an RLWC(i)automaton if all its rewrite steps are CL-steps. Further, an RLWW(i)-automaton is called RLWWC(i)-automaton if all its rewrite steps are CL-steps. Similarly, an RLWW(i)-automaton is called RLWWD(i)-automaton if all its rewrite steps are DL-steps. Observe that when concentrating on input languages, DL- and CL-steps ensure that no auxiliary symbols can ever occur on the tape; if, however, we are interested in basic or h-proper languages, then auxiliary symbols can play an important role even though a given RLWW(i)-automaton uses only DL- or CL-steps. Therefore, we distinguish between RLWWC(i)and RLWC(i)-automata, and between RLWWD(i)- and RLWD(i)-automata.
In the following we will use the corresponding notations also for subclasses of RLWW(i)-automata, and hRLWW(i)-automata.
Evidently, we need not distinguish between hRLW(i)automata and RLW(i)-automata, since for the RLW(i)automata the only possible morphism h is the identity. Fact 3. (Equality of Languages for RLW(i)-automata.) For any RLW(i)-automaton M, L(M) = LC(M) = LhP(M).
We recall the notion of monotonicity (see [3, 4]) as an important constraint for computations of RLWW(i)automata. Let M be an RLWW(i)-automaton, and let C = Ck,Ck+1, . . . ,C j be a sequence of configurations ofM, where C`+1 is obtained by a single transition step from C`, k ≤ ` < j. We say that C is a subcomputation of M. If C` = ¢αqβ $, then |β $| is the right distance of C`, which is denoted by Dr(C`). We say that a sub-sequence (C`1 ,C`2 , . . . ,C`n ) of C is monotone if Dr(C`1 ) ≥ Dr(C`2 ) ≥ · · · ≥ Dr(C`n ). A computation of M is called monotone if the corresponding sub-sequence of rewrite configurations is monotone. Here a configuration is called arewrite configuration if in this configuration an SL- or W-step is being applied. Finally, M itself is called monotone if each of its computations is monotone. We use the prefixmon- to denote monotone types of RLWW(i)-automata. This notion of monotonicity has been considered before in various papers (see [7]) similarly as its following generalization.
Naturally, a mon-RLWW(i)-automaton can be used to simulate bottom-up one-pass parsers. In order to simulate also bottom-up multi-pass parsers, a j-monotonicity for restarting automata was introduced in [12]. For an integer j ≥ 1, a RLWW(i)- automaton is called j-monotone if, for each of its computations, the corresponding sequence of rewriting configurations can be partitioned into at most j sub-sequences such that each of these sub-sequences is monotone. We use the prefix mon( j)- to denote jmonotone types of RLWW(i)-automata.
Here we transfer some restricted form of restarting automata called weak cyclic form (wcf) (see [3]) over to RLWW(i)’s. An RLWW M is said to be in weak cyclic form if |uv| ≤ k for each accepting configuration ¢uqv$ of M, where k is the size of the read/write window of M. Thus, before M can accept, it must erase sufficiently many letters from its tape. The prefixwcf- will be used to denote restarting automata in the weak cyclic form. 3 3.1
On the Insensitivity of Input Languages
The following characterizations, which are slight
extensions of known results, show that with respect to their
input languages, (monotone) RLWW(
L (RLWW) = L (k-RLWW(
It remains to prove that each (monotone)
RLWW(
Transformation into weak cyclic form for input
languages. So let M1 be an RLWW(
It is easily seen that M2 is monotone, if M1 is, that it has window size three, and that it accepts the same input language as M1.
Theorem 5. For all k, k0, j ≥ 1, X ∈ {λ , wc f }:
(a) L (k-X-RLWW( j)) ⊆ L (k0-X-RLWW( j0)), for all
k
j0 ≥ d k0 e · j.
(b) CFL ⊂ L (2-X-RLWW( j)).
Proof. Case (a) follows from an easy observation that
a single rewrite operation using a window of size k
k
can be simulated by at most d k0 e rewrite operations
with a window of size k0. To prove (b) we show
that 2-wcf-RLWW(
Given any context-free language L, Niemann and Otto
in [11] showed how to construct a monotone one-way
restarting automaton with window size 3 recognizing L.
As the constructed automaton rewrites at most 2
consecutive symbols in a cycle and RLWW(
the proof of (b) it remains to show that the inclusion is
proper. We will show that the non-context-free language
L = {anb2ncn | n ≥ 0} can be accepted by a
2-RLWW(
The automaton M will use two auxiliary symbols X ,Y whose role is to indicate deleted subwords ab and bc, respectively. Within four cycles the automaton deletes one occurrence of a and c and two symbols b. To do so M scans the contents ω of the tape within the sentinels from left to right and with the right sentinel in its window M distinguishes six situations: 1. if ω = λ then M accepts; 2. if ω = a+b+c+, then M rewrites ab with X and restarts; 3. if ω = a∗X b+c+, then M rewrites bc with Y and restarts; 4. if ω = a∗X b∗Y c∗, then M deletes X and restarts; 5. if ω = a∗b∗Y c∗, then M deletes Y and restarts; 6. finally, in all other situationsM rejects.
Obviously, M iteratively repeats a series of four cycles and
then accepts/rejects in a tail computation. From the above
description, L = L(M) and L ∈ L (2-RLWW(
The previous theorem witnesses the insensitivity of input languages of RLWW(i)-automata with respect to the size of look-ahead window. 3.2 hRLWW(i)-Automata and h-Lexicalized
Syntactic Disambiguation In the following we will study basic and h-proper languages of hRLWW(i)-automata, and we will see that with respect to these languages, hRLWW(i)-automata (and their variants) are sensitive to the window size, number of SLoperations in a cycle, etc.
The reformulated basic result from [13] follows.
Theorem 6. The following equalities hold:
CFL = LhP(mon-RLWW(
The previous theorem witnesses that for any contextfree language there is a deterministic monotone analyzer which accepts the language when each input word is completely lexically disambiguated. 3.3
Weak Cyclic Form for Basic Languages Theorem 7. Let i ≥ 1. For each RLWW(i)-automaton M, there is a wcf-RLWW(i)-automaton Mwcf such that LC(M) = LC(Mwcf), and u ⇒cM∗ v implies u ⇒Mwcf v, for c∗ all words u, v. Moreover, the added reductions are in contextual form. If M is deterministic, j-monotone or simultaneously deterministic and j-monotone, for some j ≥ 1, then Mwcf is deterministic, j-monotone or simultaneously deterministic and j-monotone, respectively.
Proof. Transformation into wcf for basic languages.
Let M be an RLWW(i)-automaton. We describe how M
can be converted into a wcf-RLWW(i)-automaton Mwcf
with the basic language LC(Mwcf) = LC(M). Let us
assume that the size of the window of M is k. It is easy to
see that the language LT accepted by M in tail
computations is a regular sub-language of LC(M). This means that
there exists a deterministic finite automaton AT such that
L(AT ) = LT . Assume that AT has p states. For Mwcf we
now take a window of size kwcf = max{k, p + 1}. Mwcf
executes all cycles (reductions) of M just as M. However,
the accepting tail computations of M are replaced by
computations of Mwcf that work in the following way:
(
From the construction above we immediately see that LC(Mwcf) = LC(M). According to the definition of an RLWW(i)-automaton, the automaton M cannot rewrite during tail computations. Therefore, if M is deterministic then Mwcf is deterministic. Additionally, if M is jmonotone, then Mwcf is j-monotone, too, as the property of j-monotonicity is not disturbed by the delete operations at the very right end of the tape that are executed at the end of a computation. Moreover, all added reductions are in contextual form.
This enables to strengthen Theorem 6 by requiring automata in weak cyclic form only.
Corollary 1. For all X ∈ {RLWW(
CFL = LhP(mon-wcf-X ) = LhP(det-mon-wcf-X ).
Hence, we can require that analyzers for context-free languages are not only monotone, but they also should accept without restart short words only. 3.4
On Sensitivity of hLSA by hRLWW(i)-Automata
Here we will recall that for hRLWW(
First, however, we need to introduce some additional notions. For a type X of RLWW( j)-automata, we denote the subclass of X-automata which perform at most i reductions in any computation as fin(i)-X-automata, and by fin-X, we denote those X-automata that are of type fin(i)-X for some i ≥ 0.
For any hRLWW( j)-automaton M, we use LC(M, i) to denote the subset of LC(M) that consists of all words that M accepts by computations that contain at most i reductions, and we take LhP(M, i) = h(LC(M, i)).
Proposition 8. Let i ≥ 0, j ≥ 1 and let M be a wcfhRLWW( j)-automaton. Then there exists a fin(i)-wcfhRLWW( j)-automaton Mi such that LC(Mi) = LC(M, i), Mi has the same window size as M, and if u ⇒cM v and v ∈ LC(M, i − 1), then u ⇒cMi v. In addition, if M is deterministic, then so is Mi.
and k-fin (i)-wcf-hRLWW( j)-automaton M, the language LC(M, i) is finite. Hence, it is accepted by a finite automaton Ai. Automaton Mi cannot simply accept in tail computations all words from LC(M, i), as the words can be of length greater than k. Therefore, on input w, automaton Mi first simulates Ai. If Ai accepts, then let v1, . . . , vn be all words from LC(M, i − 1) such that w ⇒cM v`, for all `, 1 ≤ ` ≤ n. Then Mi nondeterministically selects some `0 between 1 and n, and executes a cycle that rewrites w into v`0 . Automaton Mi must be able to execute a cycle c w ⇒mi v`, for all `, 1 ≤ ` ≤ n. This is possible, as both
If M is deterministic, then n = 1 and Mi is deterministic, too.
For a positive integer k, we will use the prefixde(k)- to denote those hRLWW-automata for which each reduction shortens the word on the tape by at most k symbols.
From the previous ITAT-contribution [14] we have the following hierarchies.
Theorem 9. For all types X ∈ {hRLW(
LhP(de(k + 1)-pr1-prefX -X ), (c) LA(k-pr1-prefX -X ) ⊂ LA((k + 1)-pr1-prefX -X ), (d) LA(de(k)-pr1-prefX -X ) ⊂
LA(de(k + 1)-pr1-prefX -X ). 3.5
On Sensitivity of LSA by hRLWW(i)-Automata
As a simple consequence of Theorem 6 and the fact
that the RLWW(
Corollary 2. For all i > 1, pref ∈ {λ , det, wcf, det-wcf} and all X ∈ {hRLWW(i), hRLWWD(i), hRLWWC(i)} the following holds:
CFL ⊂ LhP(pre f -X ).
The previous corollary and the following results strongly support the idea that hRLWW(i)-automata are strong and fine enough to cover and classify the complexity of the (surface and deep) syntactic features of natural languages such as subordination (dependency), valency, coordination etc.
Lemma 1. For all j, k ≥ 1 it holds the following:
(
LhP(k-wcf-hRLWW( j)) 6= 0/,
LhP(k-wcf-hRLWW( j)) 6= 0/.
(
For r ≥ 1, s ≥ 0 let L(r,s) = {b, a(r−1)sbs+1}. In order
to show L(r,s) ∈ L (r-det-mon-fin (
Realize that hRLWW(s) automaton with window size r can delete at most rs symbols in any cycle with at most s rewrite (W- or SL-) operations. Since |a(r−1)sbs+1| − |b| = rs, neither wcf-hRLWW(s) automaton with window size r − 1 nor wcf-hRLWW(s − 1) automaton with window size r is able to recognize L(r,s) as its basic or h-proper language.
Now, the languages L(k, j+1) and L(k+1, j) can be used to
prove (
Next we show a similar hierarchy with respect to the
degree on monotonicity which is related to the number of
rewritings in a cycle. The degree of monotonicity is an
important constraint which serves for better approximation of
syntax of natural languages, and their individual features.
Lemma 2. For all j, k ≥ 1 it holds the following:
(
LhP(k-mon( j)-wcf-RLWW( j + 1)) 6= 0/ .
Proof. We provide a parametrized sequence of finite languages nLm(k, j)o∞ , which satisfy
j,k=1 (a) Lm(k, j+1) ∈ L (k-det-mon( j + 1)-wcf-RLWC( j + 1)), (b) Lm(k, j+1) 6∈ LhP(k-wcf-hRLWW( j)), and (c) Lm(k, j+1) 6∈ LhP(k-mon( j)-wcf-RLWW( j + 1)). Let Lm(k, j) = {(ckdkek( j+1)) j, (dkek( j+1)) j} ∪ {ekr j | 0 ≤ r ≤ j + 1}. We can construct a k-det-mon( j)-RLWC( j)automaton Mm(k, j) accepting Lm(k, j) as its input (and basic) language. The automaton scans the word on its tape and distinquishes the following cases: 1. if the word is of the form (ckdkek( j+1)) j, then Mm(k, j) deletes j blocks of ck and restarts;
deletes j blocks of dk and restarts;
j + 1, then Mm(k, j) deletes j blocks of ek and restarts;
It is not hard to partition the right distances of the rewriting configurations from an accepting computation of
gree j of monotonicity is necessary for accepting the input word (ckdkek( j+1)) j, which is accepted by Mm(k, j) after performing j + 3 reductions.
For reasons similar to that ones used in the proof of
ther as an h-proper language of a k-wcf-RLWW( j0 − 1)automaton for any j0 < j nor as an h-proper language of a k-mon( j0)-wcf-RLWW( j)-automaton, for any j0 < j .
The sample languages from the proofs of Lemma 1 and Lemma 2 have disjunctive alphabets and, therefore, they can be combined in order to obtain hierarchies with combined constraints. E.g., the language L(k, j) ∪ Lm(k0, j0) is a language which can be accepted as an h-proper language of a kˆ-det-mon( j0)-wcf-RLWC( jˆ)-automaton, where kˆ= max(k, k0) and jˆ= max( j, j0), but not as an h-proper language of neither a k-wcf-RLWW( j − 1)-automaton, nor a k0-mon( j0 − 1)-wcf-RLWWC( j0).
In a similar way, we obtain the following consequences. We present here only such consequences which can be interpreted as linguistically relevant with respect to the complete lexical disambiguation.
Corollary 3. For all j, k ≥ 1, all prefixes prefX , prefY ∈ {det-wcf, det-fin (i)-wcf} and all X ,Y ∈ {hRLWW, hRLWWD, hRLWWC}, the following holds: (a) LA(k-pre fX -X ( j)) ⊂ LA(k-pre fX -X ( j + 1)), (b) LA(k-pre fX -X ( j + 1)) r LA(k-pre fY -Y ( j)) 6= 0/, (c) LA(k-pre fX -X ( j)) ⊂ LA((k + 1)-pre fX -X ( j)), (d) LA((k + 1)-pre fX -X ( j)) r LA(k-pre fY -Y ( j)) 6= 0/.
If additionally i ≥ j + 3, the following holds: (aa) LA(k-mon( j)-pre fX -X ( j) ) ⊂
LA(k-mon( j + 1)-pre fX -X ( j + 1)), (bb) LA(k-mon( j + 1)-pre fX -X ( j + 1)) r LA(k-pre fY -Y ( j)) 6= 0/, (cc) LA(k-mon( j)-pre fX -X ( j)) ⊂
LA((k + 1)-mon( j)-pre fX -X ( j)), (dd) LA((k + 1)-mon( j)-pre fX -X ( j)) r LA(k-pre fY -Y ( j)) 6= 0/ .
We can see that the h-lexicalized syntactic analyses of det-wcf-hRLWW( j)-automata are sensitive to the maximal number of rewrite (SL- and W-) operations in a cycle and to the size of the window. The syntax of these languages is given directly by individual reductions, i.e., by individual instructions of the hRLWW( j)-automata. Namely the reductions of RLWWC( j)-automata describe (define) the (discontinuous) syntactic constituents of the analyzed words (sentences). Note that the monotonicity of degree one means a synonymy for context-freeness of the accepted languages by restarting automata. The monotonicity of higher degree means a degree of non-contextfreeness of accepted languages. In the previous corollary we have transferred this concept from infinite to finite languages. That can be very useful for classification of individual syntactic features. 4
We have seen that monotone RLWW(i)-automata are not sensitive to the number of deletions and to the size of their window with respect to their input languages and that these languages do in general not yield reduction correctness preserving computations of RLWW(i)-automata. On the other hand, hRLWW(i)-automata satisfy the reduction correctness preserving property with respect to their basic and h-proper languages, and consequently also with respect to their lexicalized syntactic analysis. The reduction correctness preserving property enforces the sensitivity to the number of rewritings in a reduction and to the size of the window.
We believe that the class of h-proper languages of
det-mon(
Our long term goal is to propose and support a
formal (and possibly also software) environment for a further
study and development of Functional Generative
Description (FGD) of Czech (see [9]). We strongly believe that
the lexical disambiguation of FGD can be fully described
by (a certain refinement
of)det-mon(
We stress that our current efforts cover an important gap in theoretical tools supporting computational and corpus linguistics. Chomsky grammars and the corresponding types of automata do not support lexicalized syntactic analysis, as these grammars work with categories bound to individual constituents with respect to constituent syntactic analysis. They do not support syntactic analysis with any kind of correctness preserving property, but they do support several types of insensitivity to the form of individual grammar rules (see several normal forms for context-free grammars, like Chomsky and Greibach normal form [2]), and, finally, they do not support the classification of finite phenomena of (natural) languages.
On the other hand, in corpus linguistics, only finite language phenomena can be observed. Now the basic and hproper languages of hRLWW(i)-automata in weak cyclic form allow common classifications of finite phenomena as well as classifications of their infinite generalizations to the corresponding parts of the Chomsky hierarchy. All these classifications are based on the reduction correctness preserving property and the weak cyclic form. Let us recall for restarting and list automata the monotonicity means a synonymy for context-freeness. Here we are able to distinguish between finite monotone and finite nonmonotone languages (syntactic phenomena), too.
Finally, note that many practical problems in computational and corpus linguistic became decidable if we consider only parametrized finite languages.