Our long-term goal is to propose and support an advanced formal (and hopefully also software) environment (framework) for Functional (Generative) Description (FGD) of Czech ([8, 13]), and for similar formal descriptions(see e.g. [6]). This framework should enable to describe the grammaticality and ungrammaticality of a language in a building-kit way. This paper creates one further step to achieve this goal.
We introduce and study the notion of lexically syntactic characterization (LSC) and its complexity features by h-lexicalized two-way restarting automata (hRLWW(i)automata), that can rewrite at most i times per cycle, for i 1, move in both directions (RL), and can re(w)rite using two alphabets (WW). Lexically syntactic characterization creates a characterization of a lexicalized syntax of a language. It is composed of four components: basic language, h-proper language, h-lexicalized syntactic analysis, and analysis by reduction. The h-lexicalized syntactic analysis formalizes the informal concept of lexical disambiguation of sentences. It is supposed that analysis by reduction satisfies the important basic correctness preserving property in order to express the full syntactic disambiguation of basic vocabulary (alphabet).
We stress the sensitivity of syntactic characterizations on the size of windows of the automata, on the number of allowed rewrite operations in one reduction of the automata, and on types of rewrite operations. The LSC’s are sensitive on the mentioned features in a similar way for infinite as well as for finite (individual) syntactic characterizations. We present in that way useful tools for new types of complexity classifications for syntactic phenomena, and we observe that these phenomena in Czech are with respect to this classifications often simple.
One of our long-term goals is to cover an essential gap in theoretical tools supporting computational and corpus linguistics. Chomsky’s and other types of phrase-structure *The research was partially supported by the grant of the Czech Science Foundation No. 19-05704S by the authors stay at Institute of Computer Science, Czech Academy of Sciences.
†The research is partially supported by VEGA 2/0165/16
Copyright ©2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). grammars do not support syntactic lexical disambiguation nor analysis by reduction as these grammars work with categories bound to individual constituents related to constituent syntactic analysis. They do not support modeling of analysis by reduction with any kind of correctness preserving property, they do not support any type of sensitivity to the size of individual grammar (automata) rules (see several normal forms for context-free grammars, like Chomsky normal form [2]), and, finally, they do not support any kind of natural classification of finite syntactic constructions related to (natural) languages.
On the other hand, in traditional and corpus linguistics, only finite language phenomena can be observed. Now the lexically syntactic characterizations of hRLWWC(i)automata with fixed window size, and in strong or weak cyclic form allow common classifications of finite syntactic phenomena as well as classifications of their infinite relaxations. All these classifications are based on the basic correctness preserving property and the strong (weak) cyclic form. The concept of hRLWWC(i)-automaton offers a rich set of constraints for expressing the grammaticality and ungrammaticality of individual natural language phenomena which are here formally expressed by LSC.
Let us recall that for restarting automata the (simple or general) monotonicity property characterizes context-free languages. We distinguish in a new way degrees of complexity of finite and infinite syntactic characterizations in order to naturally classify natural-language syntactic phenomena, which should not be considered (by linguistic intuition) as context-free. We are able to capture, e.g., the well-known Dutch sentence example below, see, e.g., the discussion in [5], which is, on one hand, finite, i.e. formally it is regular, but on the other hand, it is often considered (informally) as non-context free.
Let us recall that example. It is in the form of one branch of (naive, i.e. without the lexical disambiguation) analysis by reduction.
... dat Jan Piet Marie de kinderen zag helpen leren zwemmen
... that Jan Piet Marie the children saw help teach swim The first reduction deletes the (isolated) words “Marie” and “leren”: ... dat Jan Piet de kinderen zag helpen zwemmen ... that Jan Piet the children saw help swim The second reduction deletes the (isolated) words “Piet” and “help”: ... dat Jan de kinderen zag zwemmen ... that Jan the children saw swim
Example 1 at the end of this paper presents another natural language example with the full lexical disambiguation and full analysis by reduction.
A model of restarting automaton that formalizes lexicalized syntactic disambiguation in a similar way as categorial grammars (see, e.g., [1]) – the h-lexicalized restarting automaton (hRLWW) – was introduced in [10]. This model is obtained from the two-way restarting automaton by adding a symbol-to-symbol morphism h that assigns an input symbol to each working symbol. This morphism models the grammatical disambiguation of individual word-forms and punctuation marks. Then the basic language LC(M) of an hRLWW-automaton 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 f(h(w); w) j w 2 LC(M) g, denoted as LA(M), is called the h-lexicalized syntactic analysis (LSA) 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, categories).
Analysis by reduction is traditionally learned in Czech schools. It is used to analyze sentences of natural languages with a higher degree of word-order freedom like, e.g., Czech, Latin, or German. Usually, a human reader is supposed to understand the meaning of a given sentence before he starts to analyze it ([12]); h-lexicalized syntactic analysis based on the analysis by reduction (AR) simulates such a behavior by analysis of sentences, where morphological and syntactical tags have been added to the wordforms and punctuation marks (see, e.g., [8]). An important property of analysis by reduction is the so-called correctness preserving property. Using hRLWW(i)-automata the linguistic correctness preserving property is simulated by the formal notion of basic correctness preserving property.
Actually, the constrained hRLWW(i)-automata that are in a strong cyclic form preserve the essential part of the power of hRLWW(i)-automata but simultaneously they allow to extend the complexity results obtained for the classes of infinite syntactic characterizations also into the classes of finite syntactic characterizations. This is useful for classifications and the learning of individual phenomena in computational and corpus linguistics, where all the (syntactic) observation are of a finite nature. It also allows to design techniques for the localization of syntactic errors (grammar-checking).
Finally, we introduce the formal concept of lexically syntactic characterization (LSC), which creates a formal basis for an environment for syntactic characterizations of natural languages. An important component of LSC is analysis by reduction. Analysis by reduction is in its principle non-deterministic and correctness preserving. That is the reason for the use of non-deterministic, correctness preserving restarting automata. Also, the concept g-monotonicity is forced by the modelling of nondeterministic analysis by reduction. The correctness preserving property represents the full disambiguation for the basic alphabet, in other words for the (manually developed) lexical tags and/or categories.
We show some essential refinements of hierarchies related to the Chomsky hierarchy for formal languages in the area of LSC. We obtain in this way new tools for a natural new type of classification of syntactic phenomena connected with lexicalized syntax formulated in the terms of the theory of automata and formal languages. Let us yet stress that the achieved results are obtained through basic languages and the relation between basic and input alphabets (h-morphism) as the basis for this type of building-kit considerations. It is not possible to obtain similar tools by considering the well-known input languages which are commonly used in the automata theory, and in the theory of restarting automata, as well. 2
By and we denote the subset and the proper subset relation, respectively. Further, we will sometimes use regular expressions instead of the corresponding regular languages. Finally, throughout the paper l will denote the empty word.
We start with the definition of the two-way restarting automaton.
Definition 1. Let i be a positive integer. A two-way restarting automaton, an RLWW(i)-automaton for short, is a machine with a flexible tape and a finite-state control. It is defined through a 9-tuple M = (Q; S; G; ¢; $; q0; k; i; d ), where Q is a finite set of states, S is a finite input alphabet, and G( S) is a finite working alphabet. The symbols from G r S are called auxiliary symbols. Q and G are disjoint. Further, the symbols ¢; $ 62 G, called sentinels, are the markers for the left and right border of the workspace, respectively, q0 2 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 d : Q
PC ( k) ! P((Q fMVR; MVL; SL(v)g) [ fRestart; Accept; Rejectg) is the transition relation. Here P(S) denotes the powerset of a set S, PC ( k) denotes the set of possible contents of the read/write window of size k: f g G ( ¢
k 1) [ Gk [ (G k 1 f$g) [ (f¢g G k 2 f$g) and v 2 PC ( k 1).
Being in a state q 2 Q and seeing u 2 PC ( k) in its window, the automaton can perform six different types of transition steps (or instructions): 1. A move-right step assumes that (q0; MVR) 2 d (q; u), where q0 2 Q and u does not end by the right sentinel $. 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 assumes that (q0; MVL) 2 d (q; u), where q0 2 Q and u does not start with the left sentinel ¢. It causes M to shift the window one position to the left and to enter state q0. 3. A rewrite step with left shortening (an SL-step) assumes that (q0; SL(v)) 2 d (q; u), where q0 2 Q, v 2 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 juj jvj 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 restart step assumes that Restart 2 d (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. 5. An accept step assumes that Accept 2 d (q; u). It causes
M to halt and accept. 6. A reject step assumes that Reject 2 d (q; u). It causes M to halt and reject.
A configuration of an RLWW(i)-automaton M is a word aqb , where q 2 Q, and either a = l and b 2 f¢g G f$g or a 2 f¢g G and b 2 G f$g; here q represents the current state, ab is the current contents of the tape, and it is understood that the read/write window contains the first k symbols of b or all of b if jb j < k. A restarting configuration is of the form q0¢w$, where w 2 G .
In general, an RLWW(i)-automaton M is nondeterministic, that is, d (q; u) can contain two or more elements, for some state q and contents of the read/write window 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; : : : ;C j of configurations of M, where C0 is a restarting configuration and C`+1 is obtained from C` by a step of M, for all 0 ` < 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 an RLWW(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 a tail. It is required that in each cycle RLWW(i)-automaton executes at most i rewrite steps (of type 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 cyclerewriting 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 juj > jvj. Accordingly, u )cM v is also called a reduction by M.
A basic (or characteristic) word w 2 G is accepted by M if there is a computation which starts with the restarting configuration q0¢w$ and ends by executing an accept step. By LC(M) we denote the set of all words from G that are accepted by M; we say that M recognizes (or accepts) the basic (or characteristic1) language LC.
We define the set of correct reductions by M as
CRS(M) = f u )cM v j u; v 2 LC(M) g the analysis by reduction of a word u 2 LC(M) by M as
AR(M; u) = f x )cM z 2 CRS(M) j u ) cM x g; and the analysis by reduction recognized by M as
AR(M) = f AR(M; u) j u 2 LC(M) g:
Finally, we come to the definition of 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; S; G; ¢; $; q0; k; i; d ) is an RLWW(i)-automaton and h : G ! S is a letter-to-letter morphism satisfying h(a) = a for all input letters a 2 S. The basic language LC(Mb) of Mb is the language LC(M), and the analysis by reduction AR(Mb) is the analysis by reduction AR(M).
Further we say that Mb recognizes (or accepts) the hproper language LhP(Mb) = h(LC(M)).
Finally, the set LA(Mb) = f (h(w); w) j w 2 LC(M) g is called the (h-)lexicalized syntactic analysis (shortly LSA) by Mb.
For x 2 S , LA(Mb; x) = f (x; y) j y 2 LC(M); h(y) = x g is the lexicalized syntactic analysis for x by Mb. We see that LA(Mb; x) is non-empty only for x from LhP(Mb).
Let us note that LSA formalizes the linguistic notion of lexical disambiguation of sentences. Each auxiliary symbol x 2 G r S of a word from LC(Mb) can be considered as a disambiguated input symbol h(x).
Let M be an hRLWW(i)-automaton. If u )cM v and u 2 LC(M) induce that v 2 LC(M), and therewith h(v) 2 LhP(M), and (h(v); v) 2 LA(M), then we say that M is basically correctness preserving.
The following fact ensures the transparency for computations of deterministic hRLWW(i)-automata.
1The subscript C is preserved from previous papers where basic languages were called characteristic languages.
Fact 1. Let M be a deterministic hRLWW(i)-automaton. Then M is basically correctness preserving.
Finally, we introduce the concept of lexically syntactic characterization (LSC). Let M be an hRLWW(i)automaton, and u 2 LC(M). We take as LSC(M; u) = f(u; h(u); AR(M; u))g. We say that LSC(M; u) is the lexically syntactic characterization of u by M. Further we take as LSC(M) = fLSC(M; u) j u 2 LC(M) g. We say that LSC(M) is the lexically syntactic characterization (LSC) recognized by M.
Notations. For brevity, the prefixes det- and bcppwill be used to denote the property of being deterministic and basically correctness preserving, respectively. For any class A of automata, LC(A) will denote the class of basic languages that are recognized by automata from A, and LhP(A) will denote the class of h-proper languages that are recognized by automata from A. LA(A) will denote the class of LSA (h-lexicalized syntactic analyses) that are defined by automata from A. AR(A) will denote the class of AR’s (analyses by reduction) that are defined by automata from A. LSC(A) will denote the class of LSC (lexically syntactic characterizations) that are defined by automata from A.
For a natural number k 1, LC(k-A), LhP(k-A), LA(k-A), AR(k-A), LSC(k-A) will denote the class of basic languages, h-proper languages, LSA’s, AR’s, and LSC’s respectively, that are recognized by those automata from A that use a read/write window of size at most k. In other words the prefix k- means the restriction on the size of the read/write window. 2.1
Here we introduce some constrained types of rewrite steps (instructions) whose introduction is motivated by different types of linguistic reductions.
A delete-left step, written as (q0; DL(v)) 2 d (q; u), is a special type of an SL-step (q0; SL(v)) 2 d (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 juj jvj symbols to the left, but at most to the left sentinel ¢.
A contextual-left step, written as (q0; CL(v)) 2 d (q; u), is a special type of DL-step (q0; DL(v)) 2 d (q; u), where u = v1u1v2u2v3, u1; u2 2 G , ju1u2j 1 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 juj jvj symbols to the left, but at most to the left sentinel ¢.
An RLWW(i)-automaton is called an RLWWD(i)automaton if all its rewrite steps are DL-steps. An RLWW(i)-automaton is called an RLWWC(i)-automaton if all its rewrite steps are CL-steps.
In the following we will use the corresponding notation also for subclasses of RLWW(i)- and hRLWW(i)automata. Additionally, for a type X of RLWW(i)automata and an integer k 1, prefix k- will denote the subclass of X of automata of windows size at most k. For example, 3-det-hRLWWC(i) denotes the class of deterministic h-lexicalized RLWWC(i)-automata with window size at most 3.
We recall the notions of monotonicity and gmonotonicity (see [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 of M, 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` = a qb , then jb j 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, where k `1 < `2 < `n j, 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 a rewrite configuration if in this configuration an SL-step is being applied. Finally, M itself is called g-monotone if for each accepting computation of M there is an accepting computation of M with the same first (starting) configuration that is monotone. M is called monotone if all its computations are monotone. Note, that by notions of monotonicity the sequence of all rewritings in a sub-computation is considered, and the cycles are not considered. We use the prefix gmon- (mon-) to denote g-monotone (monotone) types of hRLWW(i)-automata. We can see that any mon-hRLWW(i)-automaton is also a gmon-hRLWW(i)automaton. We work here with the g-monotonicity (cf. [4]) in order to adequately model the non-deterministic character of analysis by reduction. Non-deterministic analysis by reduction is traditionally used to determine the syntactic (in)dependencies in natural language (e.g., Czech) sentences (see, e.g., [7, 6]).
A restriction of the form of restarting automata called strong cyclic form can be transferred to hRLWW(i)automata. An hRLWW M is said to be in strong cyclic form if juvj k for each halting configuration ¢uqv$ of M, where k is the size of the read/write window of M. Thus, before M can halt, it must erase sufficiently many letters from its tape. The prefix scf- will be used to denote restarting automata that are in strong cyclic form. The concept of strong cyclic form is useful for the presented sensitivity properties, and for techniques of grammar-checking (localization of syntactic errors) by hRLWW(i)-automata. 3
In this section we will study lexicalized syntactic characterizations (LSC) of scf-hRLWW(i)-automata by the study of their components, i.e. basic and h-proper languages, LSA’s, and AR’s. We will see that, with respect to LSC, scf-hRLWW(i)-automata (and their variants) are sensitive to several types of constraints, as, e.g., the window size, number of SL-operations (rewritings) in a cycle, (non)determinism, and types of allowed rewriteoperations. Through these constraints we essentially establish and refine the classifications which are derived from the linguistically relevant part of the Chomsky hierarchy and we will do so in several phases. In the first phase we refine the part corresponding to context-sensitive languages by the number of rewritings in a cycle. Next, by using the window size, we refine the individual areas of LSC that are given by the number of rewritings in a cycle. Finally, we use the AR’s for the refinement by the nondeterminism and by the three different types of rewritings (SL, DL, CL). We consider all those types of constraints which are highly relevant for linguistic classifications.
The complexity of sentences can be measured also by the number of used reductions. That is the reason to consider the following concepts. For any RLWW(i)automaton M, we use n( j)-LC(M) and n( j)-LhP(M) to denote the subsets of LC(M) and LhP(M), respectively, consisting of words accepted by computations with at most j reductions (cycles). Analogous notation is used also with any type X of RLWW(i)-automaton: n( j)-LC(X) and n( j)-LhP(X) denote the subclasses of LC(X) and LhP(X), respectively, consisting of languages accepted by computations with at most j reductions (cycles). Similarly we use the prefix n( j)- for the classes of lexically syntactic characterizations, syntactic analyses, and analyses by reduction. E.g., n( j)-LSC(scf-RLWWC(i)) denotes the class of syntactic characterizations obtained from LSC(scf-RLWWC(i)) by allowing only accepting computations with at most j reductions. 3.1
Let us yet note that the prefix bcpp- means the basic correctness preserving property.
Subsequent sections are focused on results related to the sensitivity of scf-hRLWW(i)-automata. In particular, we show the sensitivity of the above mentioned automata on the size of the windows, and on the number of rewritings in a cycle.
(
LhP(k-scf-hRLWW(i 1)) 6= 0/ ,
(
LhP((k 1)-scf-hRLWW(i)) 6= 0/ .
Proof. (
Evidently, M(i;k) can be deterministic, monotone and in 1 strong cyclic form.
Next we show that L1(i;k) cannot be an h-proper language of any RLWW(i0)-automaton in strong cyclic form with i0 < i. For a contradiction, let M be a k-scf-hRLWW(i0)automaton such that Lhp(M) = L(i;k), where i0 < i. As 1 w = ak i+k 2 L1(i;k), jwj > k, and as M is in strong cyclic form, each accepting computation of M on input w must start by a cycle. As ak is the only shorter word in L(i;k), 1 the automaton must rewrite ak i+k into a word w0 such that h(w0) = ak. Hence, it must delete k i symbols. However, this is not possible, as M can rewrite at most k i0 < k i symbols in a cycle – a contradiction.
(
In the same way as in the proof of the above claim, we can show that the language fin( j)-LC(M1(i;k)) cannot be h-proper language of any k-scf-hRLWWC(i0)-automaton with i0 < i.
(
2. accepts in a tail, if n = k; 3. deletes the first occurrence of a and restarts, if n = ` k for some ` > 1; 4. deletes the suffix ak and restarts, if n = ` k + m for some ` 1 and 1 m k 1.
Evidently, M(k) is deterministic, monotone and in strong 2 cyclic form. Moreover, M(k) accepts L2(k) in computations 2 which have no cycle.
Each non-empty h-proper language accepted by a (k 1)-scf-hRLWW(i)-automaton M contains at least one word of length at most (k 1). The language L2(k) is nonempty but it does not contain any word of length at most k 1. Hence it cannot be the h-proper language of any (k 1)-scf-hRLWW(i)-automaton.
Obviously, LC(X) LhP(X), for any type X of hRLWW-automata. Hence with Theorem 2 we have the following consequence.
Proof. The inclusion relations in both claims follow directly from the definitions. For any i 1, we prove that both inclusions are proper using the following sample language L3(i) = f(anbn)i j n 0g. This language is the basic and also the h-proper language of the following 2-det-scf-hRLWWD(i)-automaton M3(i). On input w 2 fa; bg , the automaton: 1. accepts, if w = l , 2. deletes i occurrences of ab (one in each segment a+b+) and restarts, if w is from (a+b+)i. 3. deletes the first occurrence of a and restarts, if w is from (a+b+)` for some positive integer ` 6= i, 4. deletes the first occurrence of a and restarts, if w starts by a and w is not from (a+b+)i, 5. deletes the first occurrence of a and restarts, if w starts by b and contains at least one a, 6. deletes the last occurrence of b and restarts, if w = b` for some ` > 1, 7. rejects, if w = b.
The automaton does not use any auxiliary symbol. It is easy to see that L(M3(i)) = LC(M3(i)) = LhP(M3(i)) = L3(i). As the automaton M(i) is deterministic, it has the basic 3 correctness preserving property. Moreover, the automaton is in strong cyclic form.
On the other hand, let us suppose that L3(i) is the basic language of a k-scf-hRLWW(i0)-automaton M, for some i0 < i. On input w = (anbn)i for a sufficiently large n k, the automaton M must perform at least one cycle w )cM w0, where w0 = (an jbn j)i, for some j, k > j > 0. For that, at least i rewriting steps are necessary – a contradiction.
In a similar way we can prove that L(i) cannot be the 3 h-proper language of any scf-hRLWW(i0)-automaton, for any i0 < i.
LhP(k-gmon-bcpp-scf-hRLWW(
Proof. The h-proper languages of
(mon-hRLWW(
In [10], it was shown that each context-free
language is an h-proper language of a
det-mon-RLWWC(
To prove both proper inclusions we can use the
context-free language L2(k+1) which cannot be h-proper
(and therefore also not be the basic) language of any
k-scf-RLWW(
The first claim of Theorem 4 presents the robustness
of the class of h-proper languages with respect to several
subclasses of gmon-scf-hRLWW(
Notations. We denote for k 1 by k-CFLA the class
LA(k-gmon-bcpp-scf-hRLWW(
Notations. For i 1 we denote by LSC(i) the class LSC(bcpp-scf-hRLWWC(i)) and by LSA(i) the class LA(bcpp-scf-hRLWWC(i)). Taking the union over all natural numbers we obtain classes LSC = Si2N LSC(i) and LSA = Si2N LSA(i).
Proof. Claim (
The sensitivity of hRLWW(i)-automata on the size of their windows can be utilized to essentially refine the hierarchies of LSC’s. These refined hierarchies yield a fine classification of syntactic phenomena in lexicalized syntaxes of natural languages.
Note that prefix k- indicates the window size of the model in mind. So, k-LSC(i) is the class LSC(k-bcpp-scf-hRLWWC(i)); analogously k-LSA(i), and k-LSA. We say that k-LSC(i) is the set of k-restricted lexically syntactic characterizations of degree i, k-LSA(i) is the set of k-restricted lexically syntactic analyses of degree i. k-LSC is the set of k-restricted lexically syntactic characterizations and k-LSA is the set of k-restricted lexically syntactic analyses.
Then, the next corollary easily follows from Theorem 3. Corollary 3. For all i
We start this subsection by a small linguistic example which will help us to demonstrate some of the considerations about sensitivity of LSC’s which is derived from the analysis by reduction.
Example 1. Fig.1 below illustrates analysis by reduction
corresponding to lexically disambiguated (tagged)
sentence:
(
We do not let the reflexive particle ’se’ to be deleted, because we consider a deletion of a sole reflexive particle a forbidden reduction.
Rozhodl.Pred se.AuxT dnes.Adv odstoupit.Obj ..AuxK Rozhodl.Pred se.AuxT odstoupit.Obj ..AuxK
Rozhodl.Pred se.AuxT dnes.Adv ..AuxK
Rozhodl.Pred se.AuxT ..AuxK
In order to obtain more fine and practical type of constraint we refine the notion of strong cyclic form. An khRLWW M is said to be in strong cyclic form of degree i if juvj k i for each halting configuration ¢uqv$ of M. The prefix scf(i)- will be used to denote restarting automata that are in strong cyclic form of degree i. We will illustrate the notion by the previous example.
The analysis by reduction from the previous
example has two branches. It is not hard to see
that it can be simulated by a nondeterministic
1-bcpp-gmon-scf(
fRozhodl, se, dnes, odstoupit, .g and the morphism h given by the following set of equalities: h([Rozhodl:Pred]) = Rozhodl; h([odstoupit:Obj]) = odstoupit; h([.:AuxK]) = ‘.’: h([se:AuxT) = se; h([dnes:Adv]) = dnes;
As no deterministic restarting automaton can provide an analysis by reduction with more than one branch, we obtain the following corollary.
3 it holds the following:
It is not hard to see that similar corollaries hold also if we add different combinations of constraints for the size of the window, for the number of allowed reductions, and for the different types of rewriting.
The following proposition can be easily shown using a set of small (finite) artificial examples of analysis by reduction.
1 it holds the following:
(
We have introduced the concept of lexically syntactic characterization (LSC) by hRLWW(i)-automata. Our aim was to characterize exactly the grammatical and ungrammatical syntactic phenomena in terms close to lexicalized syntax of natural languages. LSC characterizes the explicative power of scf-hRLWW(i)-automata by basic languages.
We consider scf-hRLWW(i)-automata which satisfy the basic correctness preserving property. Together, the strong cyclic form and the basic correctness preserving property enforce the sensitivity to the number of rewritings in a cycle, to the size of the window, and the sensitivity with respect to finite syntactic phenomena. We have transferred syntactic features characterizing context-free syntactic phenomena from infinite to parametrized finite LCS’s. Finally, we have introduced the concept of degree of strong cyclic form and outlined its meaning for characterization of the complexity of analysis by reduction of individual sentences.
Thanks to the long-time study of Prague Dependency
Treebank (PDT), and manually made analysis by
reduction on this material, we believe that the above defined
class 12-LSC(
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 [8, 13]). We believe that the
LSC of full (four level) FGD can be described by tools
very close to 24-LSC(
Finally, note that many practical problems in computational and corpus linguistic became decidable if we consider only languages parametrized by the size of the windows, or even easier by the finite number of reductions.
Aknowledgement. We thank to anonymous referees for their valuable comments.