# Leftmost derivations of propagating scattered context grammars: a new proof.

In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.Keywords: formal languages, propagating scattered context grammars, leftmost derivations, generative power

1 Introduction

Propagating scattered context grammars, introduced in [3], represent an important type of semi-parallel rewriting systems. Since their introduction, however, the exact relationship of the family of languages they generate to the family of context-sensitive languages is unknown. The language family generated by these grammars is included in the family of context-sensitive languages; on the other hand, the question of whether this inclusion is proper represents an open problem in formal language theory. There have been several attempts to modify the definition of propagating scattered context grammars to obtain the family of context-sensitive languages (see [1, 2, 7, 9, 11]). The approach discussed in [11] allows the productions to be applied only in a leftmost way and, thereby, obtain the family of context-sensitive languages generated by these grammars. This result is of some interest as the use of context-free, context-sensitive, and unrestricted productions in a leftmost way in the corresponding grammars of the Chomsky hierarchy does not have any impact on their generative power.

The proof in [11] consists of two parts; first, two preliminary lemmas (Lemma [member of] and Lemma 3) are given and then the main result, stated in Theorem 2, is presented as a straightforward corollary of these two lemmas. In Lemma [member of] it is demonstrated how any sentence of some context-sensitive language can be derived by a propagating scattered context grammar which uses leftmost derivations. Every sentence generated in such a way contains, however, some additional symbols. Lemma 3 shows how these symbols can be removed. Together, the proof consists of six-page-long construction part and not even one-pagelong basic idea of the construction which makes it extremely hard to follow. A more formal proof of the correctness of the construction is missing.

This paper aims to present the proof of this result in a much simpler and more readable way. The main difference of our proof lies (1) in the way how the symbols to be rewritten are selected and (2) the way how context-sensitive productions are simulated. Furthermore, the proof is based on a single construction instead of two. All this leads to a significantly simpler and more transparent construction.

2 Preliminaries and definitions

We assume that the reader is familiar with formal language theory (see [10]). For an alphabet V, |V| denotes the cardinality of V x [V.sup.*] represents the free monoid generated by V. The unit of [V.sup.*] is denoted by [epsilon]. Set [V.sup.+] = [V.sup.*] - {[epsilon]}. For w [member of] [V.sup.*], |w| and alph(w) denote the length of w and the set of symbols occurring in w, respectively.

A grammar is a quadruple G = (V, T, P, S), where V is the total alphabet, T [subset] V is the set of terminals, P is a finite set of productions of the form x [right arrow] y, where x [member of] [V.sup.*](V - T)[V.sup.*], y [member of] [V.sup.*], and S [member] V - T is the start symbol of G. If u = [z.sub.1][xz.sub.2], v = [z.sub.1][yz.sub.2], and x [right arrow] y [member of] P, where [z.sub.1], [z.sub.2] [member of] [V.sup.*], then G makes a derivation step from u to v according to x [right arrow] y, symbolically written as u [??] G v [x [right arrow] y] or, simply, u [right arrow] G v. Let [[??].sup.+.sub.G] and [[??]*.sub.G] denote the transitive closure of [[??].sub.G] and the reflexive and transitive closure of [[??].sub.G], respectively. If S [[??].sup.*G] w, where w [member of] T*, S [[??]*.sub.G] w is said to be a successful derivation of G. The language of G, denoted by L(G), is defined as L(G) = {w [member of] T*: S [[??]*.sub.G] w}. If each production of G is of the form x A y [right arrow] xuy, where x, y [member of] [V.sup.*], A [member of] V - T, u [member of] [V.sup.+], then G is a context-sensitive grammar. The family of context-sensitive languages is denoted by L(CS). If each production of G is of one of the following forms: AB [right arrow] CD, A [right arrow] BC, A [right arrow] a, where A, B, C, D [member of] V - T, and a [member of] T, then G is a grammar in the Kuroda normal form.

Lemma 1 ([4]) For every context-sensitive grammar there exists an equivalent grammar in the Kuroda normal form.

A scattered context grammar (see [1, 2, 3, 5, 6, 7, 8, 9, 11]) is a quadruple G = (V, T, P, S), where V is the total alphabet, T [subset] V is the set of terminals, S [member of] V - T is the start symbol of G, and P is a finite set of productions such that each production has the form ([A.sub.1], [A.sub.2], ..., An)!(x1, x2, ..., [x.sub.n]), for some n [greater than or equal to] 1, where [A.sub.i] [member of] V - T, and [x.sub.i] [member of] [V.sup.*], for all 1 [less than or equal to] i [less than or equal to] n. If each production ([A.sub.1], [A.sub.2], ..., [A.sub.n]) ! (x1, x2, ..., [x.sub.n]) [member of] P satisfies [x.sub.i] [member of] [V.sup.+] for all 11 [greater than or equal to] i [greater than or equal to] n, then G is a propagating scattered context grammar. If ([A.sub.1], [A.sub.2], ..., An) [right arrow] ([x.sub.1], [x.sub.2], ..., [x.sub.n]) [member of] P, u = [u.sub.1][A.sub.1][u.sub.2][A.sub.2] ... [u.sub.n][A.sub.n][u.sub.n+1], and v = [u.sub.1][x.sub.1][u.sub.2][x.s.sub.2] ... [u.sub.n][x.sub.n][u.sub.n+1], where ui [member of] [V.sup.*] for all 1 [less than or equal to] i [less than or equal to] n + 1, then G makes a derivation step from u to v according to p = ([A.sub.1], [A.sub.2], ..., An) ! ([x.sub.1], [x.sub.2], ..., [x.sub.n]), symbolically written as u [[??].sub.G] v [p] or, simply, u[[??].sub.G] v. In addition, if [A.sub.i] [not member of] alph([u.sub.i]) for all 1 [less than or equal to] i [less than or equal to] n, then the direct derivation is leftmost, and we write [u.sub.lm][[??].sub.G] v [p]; if [A.sub.i] [not member of] alph([u.sub.i+1]) for all 1 [less than or equal to] i [less than or equal to] n, then the direct derivation is rightmost, and we write [u.sub.rm][[??].sub.G] v [p]. The language of G, denoted by L(G), is defined as L(G) = {w [member of] T* : S [[??].sub.G*] w}. A propagating scattered context grammar G = (V, T, P, S) uses leftmost or rightmost derivations if its language is defined as L(G, lm) = {w [member of] T* : [S.sub.lm])[[??]*.sub.G] w} or L(G, rm) = {w [member of] T*: [S.sub.rm])[[??]*.sub.G] w}, respectively. The family of languages generated by propagating scattered context grammars which use leftmost or rightmost derivations is denoted by L(PSC, lm) or L(PSC, rm), respectively.

3 Main Results

The following theorem and its proof, which represent the main result of this paper, demonstrate that propagating scattered context grammars which use leftmost derivations are equivalent to context-sensitive grammars.

Theorem 1 L(PSC, lm) = L(CS).

Proof: As propagating scattered context grammars do not contain erasing productions, their derivations can be simulated by linear bounded automata. As a result, L(PSC, lm) [subset or equal to] L(CS). In what follows, we demonstrate that also L(CS) [subset or equal to] L(PSC, lm) holds true by demonstrating that for every grammar in the Kuroda normal form there exists an equivalent propagating scattered context grammar which uses leftmost derivations.

Let G = (V, T, P, S) be a grammar in the Kuroda normal form. Set [N.sub.1] = (V - T) [union] {[bar.a] : a [member of] T} (suppose that (V - T) [intersection] {[bar.a] : a [member of] T} = [??]), [[??].sub.1] = {[??]:A [member of] [N.sub.1]}. Let n = |[N.sub.1]|; then, we denote the elements of [N.sub.1] as {[A.sub.1], [A.sub.2], ..., [A.sub.n]}. Define the homomorphism [alpha] from [V.sup.*] to [N*.sub.1] as [alpha](A) = A for each A [member of] V - T, and [alpha](a) = [bar.a] for each a [member of] T. Set [N'.sub.[member of]] = {A' : A [member of] V - T}, [N.sub.3] = {<ab>i : a, b [member of] V}, [N/sub.4] = {<Aa>' : A [member of] V - T, a [member of] V }, and

[N.sub.5] = {<a, 0>, <ab, 0> : a, b [member of] V }

[union] {<a, i, j> : a [member of] V - T, 1 [less than or equal to] i [less than or equal to] 3, 1 [less than or equal to] j [less than or equal to] n}

[union] {<ab, 4> : a, b [member of] T}.

Without loss of generality, assume that the sets N1, [??]1, N'2, N3, N'4, N5, {[bar.S], X}, and T are pairwise disjoint. Define the propagating scattered context grammar

[bar.G] = ([N.sub.1] [union] [[??].sub.1] [union] [N'.sub.3] [union] [N'.sub.4] [union] [N.sub.5] [union] {[bar.S], X} [union] T, T, [bar.P], [bar.S]),

where [bar.P] is constructed as follows:

1. (a) For each a [member of] L(G), where a [member of] T, add

([bar.S]) [right arrow] (a) to [bar.P];

(b) For each S [[??].sub.G] ab, where a, b [member of] V, add

([bar.S]) [right arrow] (<ab, 0>X) to [bar.P];

2. For each a, b, c [member of] V, add

(a) (<a, 0>, [alpha](b)) [right arrow] ([right arrow](a), <b, 0>),

(b) ([alpha](a), <b, 0>) [right arrow] (<a, 0>, [alpha](b)),

(c) (<a, 0>, <bc>) [right arrow] ([alpha](a), <bc, 0>),

(d) ([alpha](a), <bc, 0>) [right arrow] (<a, 0>, <bc>) to [bar.P];

3. For each A [right arrow] a [member of] P and b [member of] V, add

(a) (<A, 0>) [right arrow] (<a, 0>),

(b) (<Ab, 0>) [right arrow] (<ab, 0>),

(c) (<bA, 0>) [right arrow] (<ba, 0>) to [bar.P];

4. For each A [right arrow] BC [member of] P and a [member of] V, add

(a) (<A, 0>) [right arrow] (B<C, 0>),

(b) (<Aa, 0>) [right arrow] (B<Ca, 0>),

(c) (<aA, 0>) [right arrow] ([alpha](a)<BC, 0>) to [bar.P];

5. For each AB [right arrow] CD [member of] P, a [member of] V, E [member of] [N.sub.3] [union] [N'.sub.4], F' [member of] {B', <Ba>'}, 1 [less than or equal to] i [less than or equal to] n, and 1 [less than or equal to] j [less than or equal to] n - 1, add

(a) (hAB, 0>) [right arrow] (<CD, 0>),

(b) i. (<A, 0>, B, X) [right arrow] (<A, 1, 1>, B', [A.sub.1]),

ii. (<A, 0>, <Ba>, X) [right arrow] (<A, 1, 1i, <Ba>', [A.sub.1]),

(c) i. (<A, 1, i>, [A.sub.i]) [right arrow] (<A, 2, i>, [[??].sub.i]),

ii. (<A, 2, i>, F', [[??].sub.i]) [right arrow] (<A, 3, i>, F', [A.sub.i]),

iii. (<A, 3, j>, E, [A.sub.j]) [right arrow] (<A, 1, j + 1>, E, [A.sub.j+1]),

(d) i. (<A, 3, n>, B', E, [A.sub.n]) [right arrow] (<C, 0>, D, E, X),

ii. (<A, 3, n>, ,Ba>', [A.sub.n]) [right arrow] (<C, 0>, <Da>, X) to [bar.P];

6. For each a, b, c [member of] T, add

(a) (<ab, 0>) [right arrow] (<ab, 4>),

(b) ([bar.c], <ab, 4>) [right arrow] (c, <ab, 4>),

(c) (<ab, 4>, X) [right arrow] (a, b) to [bar.P].

In short, productions introduced in (1) initiate the derivation, productions from (2) are used to select the nonterminal to be rewritten, productions from (3), (4), and (5) simulate G's productions of the form A [right arrow] a, A [right arrow] BC, and AB [right arrow] CD, respectively, and, finally, productions from (6) finish the derivation. In the following paragraphs, we describe the derivation of [bar.G] in greater detail.

Every derivation starts either by a production introduced in (1a) to generate sentences a [member of] L(G), where a [member of] T, or by a production introduced in (1b) to generate sentences x [member of] L(G), where |x| [greater than or equal to] 2. As [bar.S] does not occur on the right-hand side of any production, productions from (1) are not used during the rest of the derivation.

Consider G's sentential form [a.sub.1][a.sub.2] ... [a.sub.k], where [a.sub.1], [a.sub.2], ..., [a.sub.k] [member of] V, for some k [greater than or equal to] 2. In [bar.G], this sentential form corresponds to

[b.sub.1][b.sub.2] ... [b.sub.r-1]<ar, 0>[b.sub.r+1][b.sub.r+2] ... [b.sub.k-2]<[a.sub.k]-[1a.sub.k]>X,

where [b.sub.i] = [alpha]([a.sub.i]) for all i [member of] {1, 2, ..., r - 1, r + 1, r + 2, ..., k - 2}, for some 1 [less than or equal to] r [less than or equal to] k - 2, or to

[b.sub.1][b.sub.2] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k], 0>X,

where [b.sub.i] = [alpha]([a.sub.i]) for all 1 [less than or equal to] i [less than or equal to] k - 2 (observe that every right-hand side of a production from (1b) represents a sentential form of this kind). To simulate a G's production, the leftmost nonterminal from its left-hand side has to be selected in the sentential form of [bar.G]. This is done by appending 0 to the symbol to be selected by productions from (2). Specifically, for a symbol a [member of] V, (2a) selects the leftmost symbol a immediately following the currently selected symbol and (2b) selects the leftmost symbol a preceding the currently selected symbol. Productions from (2c) and (2d) are used to select and unselect the penultimate nonterminal in [bar.G]'s sentential form which is composed of two symbols from V. Observe that in this way, any symbol (except for the final X) in every sentential form of [bar.G] can be selected. Further, observe that during a derivation, always one symbol is selected.

After the nonterminal is selected, the use of the G's production can be simulated. Productions of the form A [right arrow] a are simulated by (3a) for every selected nonterminal [a.sub.1], [a.sub.2], ..., [a.sub.k-2] and by (3b), (3c) if the penultimate nonterminal (which contains [a.sub.k-1], [a.sub.k]) of the [bar.G]'s sentential form is selected. Analogously, productions of the form A [right arrow] BC are simulated by productions from (4).

Productions from (5a) are used to simulate an application of productions of the form AB [right arrow] CD within the penultimate nonterminal of [bar.G]'s sentential form. In what follows, we demonstrate how productions from (5b), (5c), and (5d) are used if this production is simulated within [a.sub.1][a.sub.2] ... [a.sub.k-2]. Suppose that the sentential form in [bar.G] is of the form

[b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 0>[b.sub.r+1][b.sub.r+2] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k]>X

and we simulate the application of [a.sub.r][a.sub.r+1] [right arrow] [c.sub.r][c.sub.r+1] [member of] P. Recall that [N.sub.1] = {[A.sub.1], [A.sub.2], ..., [A.sub.n]} denotes the set of all symbols which may appear in [b.sub.r+1][b.sub.r+2] ... [b.sub.k-2]. First, to select [b.sub.r+1] = [alpha]([a.sub.r+1]), the production

(<[a.sub.r], 0>, [b.sub.r+1], X) [right arrow] (<[a.sub.r], 1, 1>, [b'.sub.r+1], [A.sub.1])

from (5(b)i) is applied in a successful derivation, so

[b.sub.1][b.sub.2] ... [b.sub.r-1]<ar, 0>[b.sub.r+1][b.sub.r+2] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k]>X

lm)[??][bar.G] [b.sub.1][b.sub.2] ... [b.sub.r-1]<ar, 1, 1>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<a.sub.k-1][a.sub.k]>[A.sub.1].

Observe that if [b.sub.r+1] does not immediately follow <[a.sub.r], 0>, the leftmost b [member of] alph([b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]) satisfying b = [b.sub.r+1] is selected by the production from (5(b)i). The purpose of productions from (5c) is to verify that the nonterminal immediately following <[a.sub.r], 0> has been selected. First, the production

(<[a.sub.r], 1, 1i,A1) [right arrow] (<[a.sub.r], 2, 1i, A1)

from (5(c)i) is applied to tag the first A1 following <[a.sub.r], 1, 1i, so

[b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 1, 1>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b..sub.k-2]<[a.sub.k-1][a.sub.k]>[A.sub.1]

lm)[??][bar.G] [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 2, 1>[b'.sub.r+1][y.sub.1]<[a.sub.k-1][a.sub.k]>[d.sub.1],

where either

[y.sub.1] = [b.sub.r+2][b.sub.r+3] ... [b.sub.m-1] [[??].sub.1][b.sub.m+1][b.sub.m+2] ... [b.sub.k-2], [d.sub.1] = [A.sub.1],

satisfying [A.sub.1] [not member of] alph([b.sub.r+2][b.sub.r+3] ... [b.sub.m-1]), for some 1 [less than or equal to] m [less than or equal to] k - 2, or

[y.sub.1] = [b.sub.r+2][b.sub.r+3] ... [b.sub.k-2], [d.sub.1] = [[??].sub.1],

satisfying [A.sub.1] [not member of] alph([y.sub.1]). Then, the production

(<[a.sub.r], 2, 1>, [b'.sub.r+1], [[??].sub.1]) [right arrow] (<[a.sub.r], 3, 1>, [b'.sub.r+1], [A.sub.1])

from (5(c)ii) is applied to untag the first symbol [[??].sub.1] following [b'.sub.r+1], so

[b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 2, 1>[b'.sub.r+1][y.sub.1]<[a.sub.k-1][a.sub.k]>[d.sub.1],

lm)[??][bar.G] [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 3, 1>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<a.sub.k-1][a.sub.k>[A.sub.1].

This means that if [A.sub.1] occurs between <[a.sub.r], 2, 1> and [b'.sub.r+1], it is tagged by the production from (5(c)i) but it cannot be untagged by any production from (5(c)ii), so the derivation is blocked. Finally, the production

(<[a.sub.r], 3, 1>, <[a.sub.k-1][a.sub.k>,[A.sub.1]) [right arrow] (<[a.sub.r], 1, 2>, <[a.sub.k-1][a.sub.k>, [A.sub.2])

from (5(c)iii) is applied, so

[b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 3, 1>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k>[A.sub.1]

lm)[bar.G] [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 1, 2>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k>[A.sub.2],

and the same verification continues for A2. This verification proceeds for all symbols from N1 so this part of the derivation can be expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with

[u.sub.i] = [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 1, i>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... bk-2hak-1akiAi,

[v.sub.i] = [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 2, i>[b'.sub.r+1][y.sub.i] <[a.sub.k-1][a.sub.k]>[d.sub.i],

[w.sub.i] = [b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 3, i>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k>[A.sub.i],

where [p.sub.i1], [p.sub.i2], and [p.sub.i3] are productions from (5(c)i), (5(c)ii), and (5(c)iii), respectively, for all 1 [less than or equal to] i [less than or equal to] n, 1 [less than or equal to] j [less than or equal to] n - 1, and either

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

satisfying [A.sub.i] [not member of] alph[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for some 1 [less than or equal to] [i.sub.m] [less than or equal to] k - 2, or

[y.sub.i] = [b.sub.r+2][b.sub.r+3] ... [b.sub.k-2], [d.sub.i] = [[??].sub.i],

satisfying [A.sub.i] [not member of] alph([y.sub.i]). After the verification is finished, the application of [a.sub.r][a.sub.r+1] [right arrow] [c.sub.r][c.sub.r+1] [member of] P is simulated by

(<[a.sub.r], 3, n>, [b'.sub .r+1], <[a.sub.k-1][a.sub.k>, [A.sub.n]) [right arrow] (<[c.sub.r], 0>, [c.sub.r+1], <[a.sub.k-1][a.sub.k>, X)

from (5(d)i), so

[b.sub.1][b.sub.2] ... [b.sub.r-1]<[a.sub.r], 3, n>[b'.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k>[A.sub.n]

lm)[??][bar.G] [b.sub.1][b.sub.2] ... [b.sub.r-1]<c.sub.r], 0>[c.sub.r+1][b.sub.r+2][b.sub.r+3] ... [b.sub.k-2]<[a.sub.k-1][a.sub.k> X.

Observe that in order to simulate a production of the form AB [right arrow] CD within [a.sub.k-2][a.sub.k-1], productions from (5(b)ii) and (5(d)ii) have to be used instead of productions from (5(b)i) and (5(d)i) in the simulation described above. The details are left to the reader.

Finally, consider a G's sentence [a.sub.1][a.sub.2] ... [a.sub.k] [member of] [T.sup.+]. This corresponds to

[[bar.a].sub.1][[bar.a].sub.2] ... [[bar.a].sub.r-1]<[a.sub.r], 0>[[bar.a].sub.r+1][[bar.a].sub.r+2] ... [[bar.a].sub.k-2]<[a.sub.k-1][a.sub.k>X,

or

[[bar.a].sub.1][[bar.a].sub.2] ... [[bar.a].sub.k-2]<[a.sub.k-1][a.sub.k], 0>X

in [bar.G] after finishing the simulation. To enter the final phase in [bar.G], we need the sentential form to be in the second above described form. This can be achieved by applying a production from (2c) to the first sentential form. The rest of the derivation can be expressed as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [p.sub.6a] and [p.sub.6c] are productions introduced in steps (6a) and (6c), respectively, and [[xi].sub.6b] is a sequence of k - 2 productions from (6b). As a result, x [member of] L([bar.G], lm) if and only if x [member of] L(G). Therefore, L(CS) [subset or equal to] L(PSC, lm).

As L(PSC, lm) [subset or equal to] L(CS) and L(CS) [subset or equal to] L(PSC, lm), we obtain L(PSC, lm) = L(CS), so the theorem holds. 2

Next, we state the following corollary.

Corollary 1 L(PSC, rm) = L(CS).

Proof: This corollary can be proved by a straightforward modification of the proof of Theorem 1 and its proof is, therefore, left to the reader. 2

received September 17, 2007, revised April 8, 2008, accepted April 11, 2008.

References

[1] H. Fernau. Scattered context grammars with regulation. Annals of Bucharest University, Mathematics-Informatics Series, 45(1):41-49, 1996.

[2] J. Gonczarowski and M. K.Warmuth. Scattered versus context-sensitive rewriting. Acta Informatica, 27:81-95, 1989.

[3] S. Greibach and J. Hopcroft. Scattered context grammars. Journal of Computer and System Sciences, 3:233-247, 1969.

[4] S. Y. Kuroda. Classes of languages and linear-bounded automata. Information and Control, 7(2):207-223, 1964.

[5] T. Masopust. Scattered context grammars can generate the powers of 2. In Proceedings of the 13th Conference Student EEICT 2007, Volume 4, pages 401-404, Brno, 2007. Faculty of Electrical Engineering and Communication BUT.

[6] A. Meduna and J. Techet. Canonical scattered context generators of sentences with their parses. Theoretical Computer Science, 389:73-81, 2007.

[7] A. Meduna and J. Techet. Maximal and minimal scattered context rewriting. In FCT 2007 Proceedings, volume 2007, pages 412-423. Springer Verlag, 2007.

[8] A. Meduna and J. Techet. Reduction of scattered context generators of sentences preceded by their leftmost parses. In Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems, pages 178-185. University of Pavol Jozef Safarik, 2007.

[9] D. Milgram and A Rosenfeld. A note on scattered context grammars. Information Processing Letters, 1:47-50, 1971.

[10] A. Salomaa. Formal Languages. Academic Press, New York, 1973.

[11] V. Virkkunen. On scattered context grammars. Acta Universitatis Ouluensis, Series A, Mathematica 6:75-82, 1973.

Tomas Masopust ([dagger]) and Jiri Techet ([double dagger])

Faculty of Information Technology

Brno University of Technology

Bozetechova 2, Brno 61266

Czech Republic

masopust@fit.vutbr.cz,techet@fit.vutbr.cz

([dagger]) Supported by the Czech Ministry of Education under the Research Plan No. MSM 0021630528.

([double dagger]) Supported by the Czech Grant Agency project No. 102/05/H050.

Printer friendly Cite/link Email Feedback | |

Author: | Masopust, Tomas; Techet, Jiri |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Geographic Code: | 1USA |

Date: | Jun 1, 2008 |

Words: | 4432 |

Previous Article: | Neighbor discovery in multi-hop wireless networks: evaluation and dimensioning with interference considerations. |

Next Article: | Counting descents, rises, and levels, with prescribed first element, in words. |

Topics: |