View source for Scattered Context Grammars research

== Introduction ==
Scattered context grammars were introduced by S. Greibach and J. Hopcroft in 1969 as a straightforward generalization of context-free grammars. Each production of these grammars contains ''n'' context-free productions which are applied in parallel to the current sentential form. For example a scattered context production 

<math>(A, B, C) \rightarrow (aA, bB, cC)</math>

which consists of three context-free productions, 

<math>A \rightarrow aA, B \rightarrow bB, C \rightarrow cC,</math>

is applicable to the sentential form ''aAbBcC'' so that all context-free components are applied in parallel and the nonterminals on their left-hand sides are in the same order as they appear in the sentential form. As a result, 

<math>a{\color{Blue}A}b{\color{Blue}B}c{\color{Blue}C} \Rightarrow a{\color{Blue}aA}b{\color{Blue}bB}c{\color{Blue}cC}.</math>

It is easy to see that by adding productions ''(S &rarr; ABC)'' and ''(A, B, C) &rarr; (a, b, c)'', where ''S'' is the start symbol of the grammar, we can easily describe the non-context-free language 

<math>\{a^nb^nc^n : n \geq 1 \}.</math>

The first advantage of scattered context grammars can be seen here - by using several context-free productions in parallel, we are able to describe some context-sensitive languages. Furthermore, by only extending context-free grammars, which are well studied and used in many practical applications, we preserve the simplicity of language description. In addition, for modeling context dependencies which span over the whole sentential form (for example in the above example), the description is much simpler than when using ordinary context-sensitive grammars.

== Basic Definitions ==

=== Formal Languages ===
The reader is expected to be familiar with the basics of formal language theory. This section is intended to describe the used terminology rather than explaining the basics of formal language theory.

An ''alphabet'' ''V'' is a finite nonempty set, 
whose members are called ''symbols''. The ''cardinality'' of ''V'', ''|V|'', is the number of ''V'''s members. A finite sequence of symbols from ''V'' is a ''string'' or, synonymously, a ''word'' over ''V''; specifically, ''&epsilon;'' is referred to as the ''empty string''. The 
''length'' of a string ''x &isin; V <sup>*</sup>'', denoted by ''|x|'', 
is the number of elements in ''x''. For ''U &sube; V'', ''|x|<sub>U</sub>'' denotes the number of occurrences of elements from ''U'' in a string ''x''.
By ''V<sup>*</sup>'', we denote the set of all strings over ''V''; ''V<sup>+</sup> = V<sup>*</sup> - {&epsilon;}''. Any subset ''L &sube; V<sup>*</sup>'' is a ''language'' over ''V''. By ''alph(x)'' we denote the set of all symbols occurring in a string ''x''. Set

<math>alph(L) = \bigcup_{x \in L}{alph(x)}.</math>

Let ''x,y &isin; V<sup>*</sup>'' be two strings over an alphabet ''V''. The 
''concatenation'' of ''x'' with ''y'', denoted by ''xy'', is the string 
obtained by appending ''y'' to ''x''. 
For all ''i &ge; 0'' the ''i''th ''power of x'', 
denoted by ''x<sup>i</sup>'', is recursively defined as 
# ''x<sup>0</sup> = &epsilon;'' and
# ''x<sup>i</sup> = x x<sup>i-1</sup>'' for ''i &ge; 1''.
The ''reversal'' of ''x'', denoted by ''rev(x)'', is ''x'' written in the reverse order. Let ''L<sub>1</sub>, L<sub>2</sub> &sube; V<sup>*</sup>'' be 
two languages over ''V''. The concatenation of ''L<sub>1</sub>'' and ''L<sub>2</sub>'', denoted by ''L<sub>1</sub>L<sub>2</sub>'', is defined as 

<math>L_1L_2 = \{xy : x \in L_1, y \in L_2\}.</math>

The ''right quotient'' of ''L<sub>1</sub>'' with respect to ''L<sub>2</sub>'', denoted by ''L<sub>1</sub> / L<sub>2</sub>'', is defined as 

<math>L_1 / L_2 = \{y : yx \in L_1, \mbox{ for some } x \in L_2\};</math>

similarly, the ''left quotient'' of ''L<sub>1</sub>'' with respect to ''L<sub>2</sub>'', denoted by ''L<sub>2</sub> \ L<sub>1</sub>'', is defined as 

<math>L_2 \backslash L_1 = \{y : xy \in L_1, \mbox{ for some } x \in L_2\}.</math>

We also use a special type of the right and the left quotient. The ''exhaustive right quotient'' of ''L<sub>1</sub>'' with respect to ''L<sub>2</sub>'', denoted by ''L<sub>1</sub> // L<sub>2</sub>'', is defined as 

<math>L_1 // L_2 = \{x : x \in L_1 / L_2, \mbox{ and no word in } L_1 // L_2 \mbox{ is a proper prefix of } x \};</math>

similarly, the ''exhaustive left quotient'' of ''L<sub>1</sub>'' with respect to ''L<sub>2</sub>'', denoted by ''L<sub>2</sub> \\ L<sub>1</sub>'', is defined as 

<math>L_2 \backslash\backslash L_1 = \{x : x \in L_2 \backslash L_1, \mbox{ and no word in } L_2 \backslash L_1 \mbox{ is a proper suffix of } x\}.
</math>

Apart from binary operations, we also make some unary operations with languages. 
Let ''L &sube; T<sup>*</sup>''. 
The ''i''th power of ''L'', ''L<sup>i</sup>'', is defined as 
# ''L<sup>0</sup> = {&epsilon;}'' and 
# ''L<sup>i</sup> = L L<sup>i-1</sup>'' for ''i &ge; 1''.
The ''Kleene star'' of ''L'', ''L<sup>*</sup>'', is defined as 

<math>L^* = \bigcup_{i \geq 0}{L^i}</math>

and the 
''Kleene plus'' of ''L'', ''L<sup>+</sup>'', is defined as 

<math>L^+ = \bigcup_{i \geq 1}{L^i}.</math>

Notice that ''L<sup>+</sup> = L L<sup>*</sup> = L<sup>*</sup> L'' and ''L<sup>*</sup> = L<sup>+</sup> &cup; {&epsilon;}''. 

'''References'''

{{cite | 
  authors    = A. Meduna|
  title     = Automata and Languages: Theory and Applications|
  journal= Springer|
  address   = London|
  year      = 2000|
  pages     = 920|
  url = http://www.springer.com/east/home/computer/artificial?SGWID=5-147-22-2001013-0
}}

{{cite | 
  authors    = G. Rozenberg and A. Salomaa|
  title     = Handbook of Formal Languages|
  volume    = 1-3|
  journal= Springer|
  address   = Berlin|
  year      = 1997|
  pages     = 2051|
  url = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-1475771-0
}}

{{cite | 
  authors    = A. Salomaa|
  title     = Formal Languages|
  journal= Academic Press|
  address   = New York|
  year      = 1973|
  pages     = 322|
  url = http://portal.acm.org/citation.cfm?id=27647
}}

=== Scattered Context Grammars ===

A ''scattered context grammar'' is a quadruple

<math>G = (V, T, P, S),\,</math> 

where
# ''V'' is the total alphabet, 
# ''T &sub; V'' is the set of terminals,
# ''P'' is a finite set of productions of the form ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>)'', where ''n &ge; 1'', ''A<sub>i</sub> &isin; V-T'' and ''x<sub>i</sub> &isin; V<sup>*</sup>'' for all ''1 &le; i &le; n'', 
# ''S &isin; V - T'' is the start symbol of ''G''.
If 

<math>u = u_1 A_1 u_2 A_2 \ldots u_n A_n u_{n+1},</math>

<math>v = u_1 x_1 u_2 x_2 \ldots u_n x_n u_{n+1},</math>

and 

<math>p = (A_1, \ldots, A_n) \rightarrow (x_1, \ldots, x_n) \in P,</math>

where ''u<sub>i</sub> &isin; V<sup>*</sup>'' for all ''1 &le; i &le; n'', then ''G'' makes a derivation step from ''u'' to ''v'' according to ''p'', symbolically written as ''u &rArr; v [p]'', or, simply, ''u &rArr; v''. In addition, if ''A<sub>i</sub> &notin; alph(u<sub>i</sub>)'' for all ''1 &le; i &le; n'', then the direct derivation is ''leftmost'', and we write ''u <sub>lm</sub>&rArr; v [p]''; if ''A<sub>i</sub> &notin; alph(u<sub>i+1</sub>)'' for all ''1 &le; i &le; n'', then the direct derivation is ''rightmost'', and we write ''u <sub>rm</sub>&rArr; v [p]''.
Set ''lhs(p) = A<sub>1</sub> A<sub>2</sub>...A<sub>n</sub>'', ''rhs(p) = x<sub>1</sub> x<sub>2</sub>...x<sub>n</sub>'', and ''len(p) = |A<sub>1</sub>...A<sub>n</sub>| = n''.
If ''len(p) &ge; 2'', ''p'' is said to be a ''context-sensitive production'', while for ''len(p) = 1'', ''p'' is said to be ''context-free''.
The ''scattered context language'', is a language generated by a scattered context grammar ''G = (V, T, P, S)'', denoted by ''L(G)'', and defined as

<math>L(G) = \{x \in T^* : S \Rightarrow^* x\}.</math>

If every derivation step in every successful derivation in ''G'' is leftmost, ''G'' ''generates L(G) in a leftmost way''. If every step in every successful derivation in ''G'' is rightmost, ''G'' ''generates L(G) in a rightmost way''. 
The family of languages generated by scattered context grammars is denoted by 

<math>\mathcal{L}(SC).</math>

=== Propagating Scattered Context Grammars ===

A ''propagating scattered context grammar'' is a scattered context grammar ''G = (V, T, P, S)'' in which each ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>) &isin; P'' satisfies ''x<sub>i</sub> &isin; V<sup>+</sup>'' for all ''1 &le; i &le; n''. The ''propagating scattered context language'' is a language generated by a propagating scattered context grammar. The family of languages generated by propagating scattered context grammars is denoted by 

<math>\mathcal{L}(PSC).</math>.

'''References'''

{{cite | 
  authors    = S. Greibach, J. Hopcroft |
  title     = Scattered Context Grammars |
  journal   = Journal of Computer and System Sciences |
  volume    = 3 |
  year      = 1969 |
  pages     = 233-247 |
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

== Results ==

=== Known Results ===

==== Generative Power ====

'''Based on'''

{{cite | 
  authors    = S. Greibach, J. Hopcroft |
  title     = Scattered Context Grammars |
  journal   = Journal of Computer and System Sciences |
  volume    = 3 |
  year      = 1969 |
  pages     = 233-247 |
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

{{cite | 
  authors    = V. Virkkunen | 
  title     = On Scattered Context Grammars |
  journal   = Acta Universitatis Ouluensis |
  volume    = Series A, Mathematica 6 |
  year      = 1973 |
  pages     = 75-82 |
  url       = http://www.kirjasto.oulu.fi/julkaisutoiminta/acta/
}}

'''Results'''

'''Theorem'''

<math>\mathcal{L}(SC) = \mathcal{L}(RE).</math>

'''Theorem'''

<math>\mathcal{L}(CF) \subset \mathcal{L}(PSC) \subseteq \mathcal{L}(CS).</math>

'''Open Problem'''

<math>\mathcal{L}(PSC) \subset \mathcal{L}(CS) \mbox{ or } \mathcal{L}(PSC) = \mathcal{L}(CS)?</math>

==== Normal Forms of Propagating Scattered Context Grammars ====

'''Based on'''

{{cite | 
  authors    = S. Greibach, J. Hopcroft |
  title     = Scattered Context Grammars |
  journal   = Journal of Computer and System Sciences |
  volume    = 3 |
  year      = 1969 |
  pages     = 233-247 |
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

'''Definitions'''

A ''2-limited grammar'' is a propagating scattered context grammar ''G = (V, T, P, S)'' such that
# ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (w<sub>1</sub>, ..., w<sub>n</sub>) &isin; P'' implies ''n &le; 2'', and for each ''1 &le; i &le; n'', ''1 &le; |w<sub>i</sub>| &le; 2'' and ''w<sub>i</sub> &isin; (V-{S})<sup>*</sup>''.
# ''(A) &rarr; (w) &isin; P'' implies ''A = S''.

'''Results'''

'''Theorem'''
If ''G'' is a propagating scattered context grammar, then there exists a 2-limited grammar ''G''' with ''L(G') = L(G)''.

==== Closure Properties of Propagating Scattered Context Grammars ====

'''Based on'''

{{cite | 
  authors    = S. Greibach, J. Hopcroft |
  title     = Scattered Context Grammars |
  journal   = Journal of Computer and System Sciences |
  volume    = 3 |
  year      = 1969 |
  pages     = 233-247 |
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

'''Definitions'''

An ''abstract family of languages'' is a pair ''(T,'' '''''L''''' '')'', or '''''L''''' when ''T'' is understood, where
# ''T'' is a countably infinite set of symbols;
# For each ''L &isin;'' '''''L''''' there is a finite set ''T<sub>1</sub> &sube; T'' such that ''L &sube; T<sub>1</sub><sup>*</sup>'';
# ''L &ne; &oslash;'' for some ''L &isin;'' '''''L''''';
# '''''L''''' is closed under the operations of union, concatenation, Kleene plus, inverse homomorphism, ''&epsilon;''-free homomorphism, and intersection with a regular language.

'''Results'''

'''Theorem'''
The family of propagating scattered context languages is closed under intersection, ''&epsilon;''-free substitution, substitution by an ''&epsilon;''-free context free language, linear erasing, and permutations.  

'''Theorem'''
The family of propagating scattered context languages is an abstract family of languages.

'''Theorem'''
If ''L'' is a recursively enumerable language, then there exists a propagating scattered context language ''L''' and a homomorphism ''h'' such that ''h(L') = L''.

'''Theorem'''
The family of propagating scattered context languages is not closed under arbitrary homomorphism and quotient by a regular language.

'''Theorem'''
The emptiness problem is recursively unsolvable for propagating scattered context grammars.

==== Extended Propagating Scattered Context Grammars ====

'''Based on'''

{{cite | 
  authors    = J. Gonczarowski, M. K. Warmuth |
  title     = Scattered Versus Context-Sensitive Rewriting |
  journal   = Acta Informatica |
  volume    = 27 |
  year      = 1989 | 
  pages     = 81-95 |
  url       = http://www.springerlink.com/content/100460/
}}

'''Definitions'''

An ''extended propagating scattered context grammar'' is a scattered context grammar ''G = (V, T, P, S)'', in which every ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>) &isin; P'' satisfies ''|x<sub>1</sub>...x<sub>n</sub>| &ge; n''.

'''Results'''

'''Theorem'''
The family of languages generated by extended propagating scattered context grammars coincides with the family of context-sensitive languages.

==== Propagating Scattered Context Grammars Using Leftmost Derivations ====

'''Based on'''

{{cite | 
  authors    = V. Virkkunen | 
  title     = On Scattered Context Grammars |
  journal   = Acta Universitatis Ouluensis |
  volume    = Series A, Mathematica 6 |
  year      = 1973 |
  pages     = 75-82 |
  url       = http://www.kirjasto.oulu.fi/julkaisutoiminta/acta/
}}

{{cite | 
  authors    = T. Masopust, J. Techet| 
  title     = Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof|
  journal   = unpublished manuscript |
  volume    =  |
  year      = 2007 |
  pages     = 1-8 |
  url       = http://unpublished
}}

'''Definitions'''

A ''propagating scattered context grammar which uses leftmost'' or ''rightmost derivations'' is a propagating scattered context grammar ''G = (V, T, P, S)'' whose language is defined as

<math>L(G, lm) = \{x \in T^* : S \;{}_{lm}\!\!\Rightarrow^* x\}</math>

or

<math>L(G, rm) = \{x \in T^* : S \;{}_{rm}\!\!\Rightarrow^* x\},</math>

respectively.
The family of languages generated by propagating scattered context grammars which use leftmost or rightmost derivations is denoted by 

<math>\mathcal{L}(PSC, lm) \mbox{ or } \mathcal{L}(PSC, rm),</math>

respectively.

'''Results'''

'''Theorem'''

<math>\mathcal{L}(PSC, lm) = \mathcal{L}(CS).</math>

'''Theorem'''

<math>\mathcal{L}(PSC, rm) = \mathcal{L}(CS).</math>

==== Reduction of Scattered Context Grammars ====

'''Based on'''

{{cite | 
   authors = A. Meduna|
   title = Economical Transformations of Scattered Context Grammars to Phrase-Structure Grammars|
   pages = 225-242|
   journal = Acta Cybernetica|
   year = 1998|
   url = http://www.inf.u-szeged.hu/actacybernetica/
}}

{{cite | 
   authors = A. Meduna|
   title = Generative Power of Three-Nonterminal Scattered Context Grammars|
   pages = 625-631|
   journal = Theoretical Computer Science|
   volume = 2000|
   number = 239|
   year = 2000|
   url = http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description
}}

{{cite | 
  authors    = G. Vaszil |
  title     = On the Descriptional Complexity of Some Rewriting Mechanisms Regulated by Context Conditions |
  journal   = Theoretical Computer Science |
  volume    = 330 |
  year      = 2005 |
  pages     = 361-373 |
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description
}}

'''Definitions'''

For a scattered context grammar ''G = (V,T,P,S)'', 
its ''nonterminal complexity'' is the number of nonterminals in ''G''. If ''G'' is a scattered context grammar, 
then its ''degree of context-sensitivity'', symbolically written as ''dcs(G)'',
is defined as the number of context-sensitive productions in ''G''.
The ''maximum context sensitivity'' of ''G'' is the greatest
number in ''{len(p<sub>i</sub>) - 1 : 1 &le; i &le; |P|}'', symbolically denoted by ''mcs(G)''. The ''overall context sensitivity'' of ''G'', denoted by ''ocs(G)'', is the sum of all members in ''{len(p<sub>i</sub>) - 1 : 1 &le; i &le; |P|}''.

'''Results'''

'''Theorem'''
There are context-sensitive languages which cannot be described by a scattered context grammar ''G = (V, T, P, S)'' satisfying ''|V-T| = 1''.

'''Theorem'''
Every recursively enumerable language is generated by a scattered context grammar ''G = (V, T, P, S)'' satisfying ''|V-T| = 3, dcs(G) = &infin;, mcs(G) = &infin;, ocs(G) = &infin;''.

'''Theorem'''
Every recursively enumerable language is generated by a scattered context grammar ''G = (V, T, P, S)'' satisfying ''|V-T| = 5, dcs(G) = 2, mcs(G) = 3, ocs(G) = 6''.

'''Theorem'''
Every recursively enumerable language is generated by a scattered context grammar ''G = (V, T, P, S)'' satisfying ''|V-T| = 8, dcs(G) = 6, mcs(G) = 1, ocs(G) = 6''.

'''Theorem'''
Every recursively enumerable language is generated by a scattered context grammar ''G = (V, T, P, S)'' satisfying ''|V-T| = 4, dcs(G) = 4, mcs(G) = 5, ocs(G) = 20''.

'''Theorem'''
Let ''H = (M, T, R, S)'' be a phrase-structure grammar in Kuroda normal form. Then, there exists a scattered context grammar ''G = (V, T, P, E)'' that satisfies
# ''L(G) = L(H)'',
# ''|M| = |V| + 5'',
# ''P'' contains 4 new context productions,
# ''P'' contains 1 new context-free production.

'''Open Problem'''
Can every recursively enumerable language be described by a scattered context grammar containing only two nonterminals?

=== Own Research ===

==== Generation of Sentences with Their Parses ====

'''Based on'''

{{cite | 
   authors = A. Meduna, J. Techet|
   title = Generation of Sentences with Their Parses: the Case of Propagating Scattered Context Grammars|
   pages = 11-20|
   journal = Acta Cybernetica|
   volume = 2005|
   number = 17|
   year = 2005|
   address = Szeged|
   url = http://www.inf.u-szeged.hu/actacybernetica/
}}

{{cite | 
   authors = A. Meduna, J. Techet |
   title = Canonical Scattered Context Generators of Sentences with Their Parses|
   pages = 73-81|
   volume = 389|
   number = 1|
   journal = Theoretical Computer Science|
   year = 2007|
   url = http://dx.doi.org/10.1016/j.tcs.2007.07.044
}}

{{cite | 
   authors = J. Techet|
   title = Scattered Context Generators of Sentences with Their Parses|
   pages = 68-77|
   journal = Pre-proceedings of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science|
   year = 2005|
   address = Znojmo|
   url = http://www.memics.cz
}}

{{cite | 
   authors = A. Meduna, J. Techet|
   title = Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses|
   pages = 178-185|
   journal = Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems|
   year = 2007|
   address = High Tatras|
   url = http://dcfs07.ics.upjs.sk/
}}

'''Definitions'''

We assume that for every scattered context grammar ''G = (V, T, P, S)'', there is a set of ''production labels'', denoted by ''lab(G)'', such that ''|lab(G)| = |P|''; as usual, ''lab(G)<sup>*</sup>'' denotes the set of all strings over ''lab(G)''.  Furthermore, there is a bijection from ''P'' to ''lab(G)'' such that if this bijection maps a production ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>)'' to a label ''l &isin; lab(G)'', we say that ''(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>)'' ''is labeled with'' ''l'', symbolically written as 

<math>l:(A_1, \ldots, A_n) \rightarrow (x_1, \ldots, x_n).</math>

To express that ''x &rArr;<sup>*</sup> y'', where ''x, y &isin; V<sup>*</sup>'', by using a sequence of productions labeled with ''p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>n</sub>'', we write ''x &rArr;<sup>*</sup> y [&rho;]'', where ''&rho; = p<sub>1</sub>...p<sub>n</sub> &isin; lab(G)<sup>*</sup>''. 

Let ''G = (V, T, P, S)'' be a scattered context grammar and let ''S &rArr;<sup>*</sup> x [&rho;]'', where ''x &isin; T<sup>*</sup>'' and ''&rho; &isin; lab(G)<sup>*</sup>''; then, ''x'' is a ''sentence generated by G according to parse &rho;''. Let ''lab(G) &sube; T''. ''G'' is a ''proper generator of its sentences with their parses'' if and only if 

<math>L(G) = \{x : x = y\rho, y \in (T - lab(G))^*, \rho \in lab(G)^*, S \Rightarrow^* x \; [\rho]\};</math>

in addition, if ''G'' generates ''L(G)'' in a leftmost or a rightmost way, ''G'' is a ''proper leftmost'' or a ''proper rightmost generator of its sentences with their parses''. Similarly, ''G'' is a ''proper generator of its sentences preceded by their parses'' if and only if

<math>L(G) = \{x : x = \rho y, y \in (T - lab(G))^*, \rho \in lab(G)^*, S \Rightarrow^* x \; [\rho]\};</math>

in addition, if ''G'' generates ''L(G)'' in a leftmost way, ''G'' is a ''proper leftmost generator of its sentences preceded by their parses''.
Notice that these definitions impose no restrictions on derivations in a proper leftmost generator. However, every proper leftmost generator ''G'' satisfies the property that if ''G'' makes a non-leftmost step during a derivation, then this derivation cannot generate a member of ''L(G)''. The same applies for proper rightmost generators.

'''Results'''

'''Theorem''' 
For every recursively enumerable language ''L'', there exists a propagating scattered context grammar ''G'' such that ''G'' is a proper generator of its sentences with their parses and ''L = L(G) // lab(G)<sup>+</sup>''. 

'''Theorem'''
For every recursively enumerable language ''L'' there exists a propagating scattered context grammar ''G = (V', T', P, S)'' such that ''G'' is a proper leftmost generator of its sentences with their parses, ''|V'-T'| &le; 6'', and ''L = L(G) // lab(G)<sup>+</sup>''.

'''Theorem'''
For every recursively enumerable language ''L'' there exists a propagating scattered context grammar ''G = (V', T', P, S)'' such that ''G'' is a proper rightmost generator of its sentences with their parses, ''|V'-T'| &le; 6'', and ''L = L(G) // lab(G)<sup>+</sup>''.

'''Theorem'''
For every recursively enumerable language ''L'' there exists a propagating scattered context grammar ''G = (V', T', P, S)'' such that ''G'' is a proper leftmost generator of its sentences preceded by their parses, ''|V'-T'| &le; 6'', ''mcs(G) = 3'', and ''L = lab(G)<sup>+</sup> \\ L(G)''.

'''Theorem'''
For every recursively enumerable language ''L'' there exists a propagating scattered context grammar ''G = (V', T', P, S)'' such that ''G'' is a proper leftmost generator of its sentences preceded by their parses, ''|V'-T'| &le; 9'', ''mcs(G) = 1'', and ''L = lab(G)<sup>+</sup> \\ L(G)''.

'''References'''

{{cite | 
 authors   = V. Geffert|
 title     = Context-Free-Like Forms for the Phrase-Structure Grammars|
 journal   = Proceedings of the Mathematical Foundations of Computer Science 1988|
 year      = 1988|
 pages     = 309-317|
 publisher = Springer-Verlag|
 address   = New York|
 url = http://www.mfcs.sk
}}

{{cite | 
  authors    = H. C. M. Kleijn and G. Rozenberg|
  title     = On the Generative Power of Regular Pattern Grammars|
  journal   = Acta Informatica|
  volume    = 20|
  year      = 1983|
  pages     = 391-411|
  url = http://www.springerlink.com/content/100460/
}}

==== Generalized k-Limited Erasing ====

'''Based on'''

{{cite | 
   authors = J. Techet|
   title = k-Limited Erasing Performed by Scattered Context Grammars|
   pages = 227-234|
   journal = Proceedings of the 2nd International Workshop on Formal Models WFM '07|
   year = 2007|
   address = Hradec nad Moravicí|
   url = http://www.isim.cz/wfm2007/
}}

'''Definitions'''

Let ''cf((A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>)) = {A<sub>1</sub> &rarr; x<sub>1</sub>, ..., A<sub>n</sub> &rarr; x<sub>n</sub>}''. The ''core grammar underlying a scattered context grammar'' ''G = (V, T, P, S)'' is denoted by ''core(G)'' and defined as the context-free grammar ''core(G) = (V, T, cf(P), S)'' with ''cf(P) = {A &rarr; x : A &rarr; x &isin; cf(p)'' for some ''p &isin; P}''. Let ''v = u<sub>1</sub>A<sub>1</sub>u<sub>2</sub>A<sub>2</sub>...u<sub>n</sub>A<sub>n</sub>u<sub>n+1</sub> &rArr; u<sub>1</sub>x<sub>1</sub>u<sub>2</sub>x<sub>2</sub>...u<sub>n</sub>x<sub>n</sub>u<sub>n+1</sub> = w [(A<sub>1</sub>, ..., A<sub>n</sub>) &rarr; (x<sub>1</sub>, ..., x<sub>n</sub>)].
The ''context-free simulation'' of this step by ''core(G)'' is denoted by ''cf(v &rArr; w)'' and defined as ''core(G)'''s derivation of the form 
''u<sub>1</sub>A<sub>1</sub>u<sub>2</sub>A<sub>2</sub>...u<sub>n</sub>A<sub>n</sub>u<sub>n+1</sub>
&rArr; u<sub>1</sub>x<sub>1</sub>u<sub>2</sub>A<sub>2</sub>...u<sub>n</sub>A<sub>n</sub>u<sub>n+1</sub>  &rArr;<sup>n-1</sup> u<sub>1</sub>x<sub>1</sub>u<sub>2</sub>x<sub>2</sub>...u<sub>n</sub>x<sub>n</sub>u<sub>n+1</sub>''.
Let ''v = v<sub>1</sub> &rArr;<sup>*</sup> v<sub>n</sub> = w'' be of the form ''v<sub>1</sub> &rArr; v<sub>2</sub> &rArr; v<sub>3</sub> &rArr; ... &rArr; v<sub>n</sub>''. The context-free simulation of ''v &rArr;<sup>*</sup> w'' by ''core(G)'' is denoted by ''cf(v &rArr;<sup>*</sup> w)'' and defined as 
''v<sub>1</sub> &rArr;<sup>*</sup> v<sub>2</sub> &rArr;<sup>*</sup> v<sub>3</sub> &rArr;<sup>*</sup>...&rArr;<sup>*</sup> v<sub>n</sub>''
such that for all ''1 &le; i &le; n-1'', ''v<sub>i</sub> &rArr;<sup>*</sup> v<sub>i+1</sub>'' is the context-free simulation of ''v<sub>i</sub> &rArr; v<sub>i+1</sub>''. 

Let ''S &rArr;<sup>*</sup> x'' be of the form ''S &rArr;<sup>*</sup> uAv &rArr;<sup>*</sup> x''. Let ''cf(S &rArr;<sup>*</sup> x)'' be the context-free simulation of ''S &rArr;<sup>*</sup> x''. Let ''t'' be the derivation tree corresponding to ''S &rArr;<sup>*</sup> x''. Consider a subtree rooted at ''A'' in ''t''. If the frontier of this subtree is ''&epsilon;'', then ''G'' ''erases'' ''A'' in ''S &rArr;<sup>*</sup> uAv &rArr;<sup>*</sup> x'', symbolically written as ''&Agrave;'', and if this frontier differs from ''&epsilon;'', then ''G'' ''does not erase'' ''A'' during this derivation, symbolically written as ''&Aacute;''. If ''o = &Aacute;<sub>1</sub>...&Aacute;<sub>n</sub>'' or ''o = &Agrave;<sub>1</sub>...&Agrave;<sub>n</sub>'', we write ''&oacute;'' or ''&ograve;'', respectively. 

Let ''G = (V, T, P, S)'' be a scattered context grammar and let ''k &ge; 0''. ''G'' ''erases nonterminals in a generalized k-limited way in S &rArr;<sup>*</sup> y'', where ''y &isin; L(G)'', if every sentential form ''x'' occurring in ''S &rArr;<sup>*</sup> y'' satisfies the following two properties:
# every ''x = uAeEa'', ''&Aacute;'', ''&Eacute;'', ''&egrave;'', satisfies ''|e| &le; k'';
# every ''x = uAa'', ''&Aacute;'', satisfies: if ''&ugrave;'' or ''&agrave;'', then ''|u| &le; k'' or ''|a| &le; k'', respectively. 
Set

<math>
\begin{array}{ll}
  L_k(G) = \{x \in T^* : & S \Rightarrow^* x, \mbox{ and } G \mbox{ erases nonterminals} \\
                              & \mbox{in a generalized } k\mbox{-limited way in } S \Rightarrow^* x \}.
\end{array}
</math>

A scattered context grammar ''G'' ''erases its nonterminals in a generalized k-limited way'' if ''L(G) = L<sub>k</sub>(G)''. The family of languages generated by scattered context grammars which erase their nonterminals in a generalized ''k''-limited way is denoted by 

<math>\mathcal{L}(SC, k).</math>

'''Results'''

'''Theorem'''
For each ''k &ge; 0'' and every scattered context grammar ''G'', there is a propagating scattered context grammar ''G''' such that ''L<sub>k</sub>(G) = L(G')''.

'''Theorem'''
For every scattered context grammar ''G'' which erases its nonterminals in a generalized ''k''-limited way, there exists a propagating scattered context grammar ''G''' such that ''L(G) = L(G')''.

'''Theorem'''

<math>\mathcal{L}(PSC) = \mathcal{L}(SC, i)</math>

for any positive integer ''i''.

==== Scattered Context Grammars with Non-Context-Free Components ====

'''Based on'''

{{cite | 
   authors = J. Techet|
   title = A Note on Scattered Context Grammars with Non-Context-Free Components|
   pages = 225-232|
   journal = MEMICS 2007 Proceedings|
   year = 2007|
   address = Znojmo|
   url = http://www.memics.cz
}}

'''Definitions'''

A ''linear scattered context grammar'' is a scattered context grammar ''G = (V, T, P, S)'', where ''P'' is a finite set of productions of the following two forms:
# ''(S) &rarr; (x<sub>1</sub>A<sub>1</sub>...x<sub>k</sub>A<sub>k</sub>x<sub>k+1</sub>)'', where ''A<sub>i</sub> &isin; (V - T) - {S}'', ''x<sub>i</sub> &isin; T<sup>*</sup>'' for all ''1 &le; i &le; k'', for some ''k &ge; 1'',
# ''(A<sub>1</sub>, ..., A<sub>k</sub>) &rarr; (z<sub>1</sub>, ..., z<sub>k</sub>)'', where ''A<sub>i</sub> &isin; (V-T) - {S}'', and either ''z<sub>i</sub> = x<sub>i</sub>B<sub>i</sub>y<sub>i</sub>'', where ''x<sub>i</sub>, y<sub>i</sub> &isin; T<sup>*</sup>'', ''B<sub>i</sub> &isin; (V-T) - {S}'', or ''z<sub>i</sub> &isin; T<sup>*</sup>'' for all ''1 &le; i &le; k'', for some ''k &ge; 1''.
A linear scattered context grammar is ''of degree n'' if ''(S) &rarr; (x<sub>1</sub>A<sub>1</sub>...x<sub>n</sub>A<sub>n</sub>x<sub>n+1</sub>) &isin; P'' is a production satisfying ''n &ge; m'' for all ''(S) &rarr; (y<sub>1</sub>A<sub>1</sub>...y<sub>m</sub>A<sub>m</sub>y<sub>m+1</sub>) &isin; P'' and, in addition, for each ''p &isin; P'', ''len(p)'' is constant for every grammar (in other words, ''len(p)'' does not depend on the degree). The family of languages generated by linear scattered context grammars of degree ''n'' is denoted by 

<math>\mathcal{L}(SC, LIN, n),</math>

and 

<math>\mathcal{L}(SC, LIN) = \bigcup_{n = 1}^{\infty} \mathcal{L}(SC, LIN, n).</math>

A ''right-linear scattered context grammar'' is a linear scattered context grammar ''G = (V, T, P, S)'', where ''P'' is a finite set of productions of the following two forms:
# ''(S) &rarr; (x<sub>1</sub>A<sub>1</sub>...x<sub>k</sub>A<sub>k</sub>)'', where ''A<sub>i</sub> &isin; (V - T) - {S}'', ''x<sub>i</sub> &isin; T<sup>*</sup>'' for all ''1 &le; i &le; k'', for some ''k &ge; 1'',
# ''(A<sub>1</sub>, ..., A<sub>k</sub>) &rarr; (z<sub>1</sub>, ..., z<sub>k</sub>)'', where ''A<sub>i</sub> &isin; (V-T) - {S}'', and either ''z<sub>i</sub> = x<sub>i</sub>B<sub>i</sub>'', where ''x<sub>i</sub> &isin; T<sup>*</sup>'', ''B<sub>i</sub> &isin; (V-T) - {S}'', or ''z<sub>i</sub> &isin; T<sup>*</sup>'' for all ''1 &le; i &le; k'', for some ''k &ge; 1''.
The family of languages generated by right-linear scattered context grammars of degree ''n'' is denoted by 

<math>\mathcal{L}(SC, RLIN, n),</math>

and 

<math>\mathcal{L}(SC, RLIN) = \bigcup_{n = 1}^{\infty} \mathcal{L}(SC, RLIN, n).</math>

'''Results'''

'''Theorem'''
For each ''n &ge; 1'', 

<math>\mathcal{L}(SC, LIN, n) = \mathcal{L}(SM, LIN, n).</math>

<math>\mathcal{L}(SC, LIN) = \mathcal{L}(SM, LIN).</math>

'''Theorem'''
For each ''n &ge; 1'',
 
<math>\mathcal{L}(SC, RLIN, n) = \mathcal{L}(SM, RLIN, n).</math>

<math>\mathcal{L}(SC, RLIN)    = \mathcal{L}(SM, RLIN).</math>

'''Theorem'''
For each ''n &ge; 1'',

<math>\mathcal{L}(SC, LIN, n)  \subset \mathcal{L}(SC, LIN, n+1),</math>

<math>\mathcal{L}(SC, RLIN, n) \subset \mathcal{L}(SC, RLIN, n+1),</math>

<math>\mathcal{L}(SC, RLIN, n) \subset \mathcal{L}(SC, LIN, n).</math>

'''Theorem'''

<math>\mathcal{L}(SC, LIN) \subset \mathcal{L}(PSC) \mbox{, } \mathcal{L}(CF) - \mathcal{L}(SC, LIN)  \neq \emptyset,</math>

<math>\mathcal{L}(SC, RLIN) \subset \mathcal{L}(PSC) \mbox{, } \mathcal{L}(CF) - \mathcal{L}(SC, RLIN) \neq \emptyset,</math>

<math>\mathcal{L}(SC, RLIN) \subset \mathcal{L}(SC, LIN).</math>

'''Theorem (Positive Closure Properties)'''
Each family 

<math>\mathcal{L}(SC, LIN, n) \mbox{ and } \mathcal{L}(SC, RLIN, n),</math>

where ''n &ge; 1'', is closed under union, reversal, homomorphism, inverse homomorphism, substitution with regular languages, concatenation with regular languages, intersection with regular languages, left and right quotient by regular languages. 

<math>\mathcal{L}(SC, LIN) \mbox{ and } \mathcal{L}(SC, RLIN)</math>

are closed under concatenation.

'''Theorem (Negative Closure Properties)'''
Each family 

<math>\mathcal{L}(SC, LIN, n),</math>

where ''n &ge; 1'', is not closed under concatenation with linear languages. Each family 

<math>\mathcal{L}(SC, RLIN, n),</math>

where ''n &ge; 1'', is not closed under concatenation with 

<math>\mathcal{L}(SC, RLIN, 2).</math>

<math>\mathcal{L}(SC, LIN) \mbox{ and } \mathcal{L}(SC, LIN)</math>

are not closed under intersection, complement and Kleene star. 

<math>\mathcal{L}(SC, LIN)</math>

is not closed under substitution with linear languages. 

<math>\mathcal{L}(SC, RLIN)</math>

is not closed under substitution with 

<math>\mathcal{L}(SC, RLIN, 2).</math>

'''References'''

{{cite | 
  authors    = O. Ibarra|
  title     = Simple Matrix Languages|
  journal   = Information and Control|
  volume    = 17|
  number    = 4|
  year      = 1970|
  pages     = 359-394|
  url = http://www.elsevier.com/wps/find/journaldescription.cws_home/622844/description#description
}}

{{cite | 
  authors    = G. Paun|
  title     = Linear Simple Matrix Languages|
  journal   = Elektronische Informationsverarbeitung und Kybernetik|
  volume    = 14|
  number    = 7/8|
  year      = 1978|
  pages     = 377-384|
  url = http://www.jalc.de/
}}

==== Maximal and Minimal Rewriting ====

'''Based on'''

{{cite | 
   authors = A. Meduna, J. Techet|
   title = Maximal and Minimal Scattered Context Rewriting|
   pages = 412-423|
   journal = FCT 2007 Proceedings|
   number = 4639|
   year = 2007|
   address = Budapest|
   url = http://www.conferences.hu/fct2007/
}}

'''Definitions'''

Let ''G = (V, T, P, S)'' be a scattered context grammar. Define a ''maximal derivation step'', ''<sub>max</sub>&rArr;'', as ''u <sub>max</sub>&rArr; v [p]'', ''p &isin; P'' if and only if ''u &rArr; v [p]'' and there is no ''r &isin; P'', ''len(r) > len(p)'', such that ''u &rArr; w [r]''. Similarly, define a ''minimal derivation step'', ''<sub>min</sub>&rArr;'', as ''u <sub>min</sub>&rArr; v [p]'', ''p &isin; P'' if and only if ''u &rArr; v [p]'' and there is no ''r &isin; P'', ''len(r) < len(p)'', such that ''u &rArr; w [r]''. Define the transitive and transitive-reflexive closure of maximal and minimal derivation steps in the standard way.
The ''language of G which uses maximal'' and ''minimal derivations'' is denoted by ''L<sub>max</sub>(G)'' and ''L<sub>min</sub>(G)'' and defined as 

<math>L_{max}(G) = \{x \in T^* : S \; {}_{max}\!\!\Rightarrow^* x\}</math>

and 

<math>L_{min}(G) = \{x \in T^* : S \; {}_{min}\!\!\Rightarrow^* x\},</math>

respectively. The corresponding language families are denoted by 

<math>\mathcal{L}(PSC, max) \mbox{ and } \mathcal{L}(PSC, min).</math>

'''Results'''

'''Theorem'''

<math>\mathcal{L}(CS) = \mathcal{L}(PSC, max).</math>

'''Theorem'''

<math>\mathcal{L}(CS) = \mathcal{L}(PSC, min).</math>

'''References'''

{{cite | 
  authors    = Takumi Kasai|
  title     = An Hierarchy Between Context-Free and Context-Sensitive Languages|
  journal   = Journal of Computer and System Sciences|
  volume    = 4|
  number    = 5|
  year      = 1970|
  pages     = 492-508|
  url = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

==== n-Limited Derivations ====

'''Definitions'''

If ''u = u<sub>1</sub>A<sub>1</sub>...u<sub>k</sub>A<sub>k</sub>u<sub>k+1</sub> &rArr; u<sub>1</sub>x<sub>1</sub>...u<sub>k</sub>x<sub>k</sub>u<sub>k+1</sub> = v'' and ''|u<sub>1</sub>A<sub>1</sub>...u<sub>k</sub>A<sub>k</sub>|<sub>V-T</sub> &le; n'', then the derivation step is ''n-limited'' and we write ''u <sup>n</sup>&rArr; v''. An ''n-limited derivation'', denoted by ''x <sup>n</sup>&rArr;<sup>*</sup> y'', is a derivation in which every derivation step ''u <sup>j</sup>&rArr; v'' satisfies ''j &le; n''. Define the ''language of degree n'' generated by ''G'' as ''L(G,n) = {x &isin; T<sup>*</sup> : S <sup>n</sup>&rArr;<sup>*</sup> x}''. The family of languages of degree ''n'' generated by propagating scattered context grammars is denoted by 

<math>\mathcal{L}(PSC, n),</math>

and

<math>\mathcal{L}(PSC, \infty) = \bigcup_{i=1}^{\infty}\mathcal{L}(PSC, i).</math>

'''Results'''

'''Theorem'''

<math>\mathcal{L}(PSC, n) = \mathcal{L}(ST, n).</math>

'''Theorem'''

<math>\mathcal{L}(CF) = \mathcal{L}(PSC, 1) \subset \mathcal{L}(PSC, 2) \subset \ldots \subset \mathcal{L}(PSC, \infty) \subset \mathcal{L}(CS).</math>

'''Theorem'''
Every 

<math>\mathcal{L}(PSC, n),</math>

where ''n &ge; 1'', is an abstract family of languages.

'''References'''

{{cite | 
  authors    = Takumi Kasai|
  title     = An Hierarchy Between Context-Free and Context-Sensitive Languages|
  journal   = Journal of Computer and System Sciences|
  volume    = 4|
  number    = 5|
  year      = 1970|
  pages     = 492-508|
  url = http://www.elsevier.com/wps/find/journaldescription.cws_home/622867/description#description
}}

== Related Literature ==

{{cite | 
  authors   = Armin B. Cremers |
  title     = Normal Forms for Context-Sensitive Grammars |
  journal   = Acta Informatica |
  volume    = 3 |
  year      = 1973 |
  pages     = 59-73 |
  url       = http://www.springerlink.com/content/100460/
}}

{{cite | 
  authors    = H. Fernau |
  title     = Scattered Context Grammars with Regulation |
  journal   = Annals of Bucharest University, Mathematics-Informatics Series |
  volume    = 45 |
  number    = 1 |
  year      = 1996 | 
  pages     = 41-49 |
  url       = http://unknown
}}

{{cite | 
  authors    = D. Milgram, A Rosenfeld|
  title     = A Note on Scattered Context Grammars|
  journal   = Information Processing Letters|
  volume    = 1|
  year      = 1971|
  pages     = 47-50|
  url       = http://www.elsevier.com/wps/find/journaldescription.cws_home/505612/description#description
}}

{{cite | 
   authors = J. Techet |
   title = Částečně paralelní generování jazyků|
   pages = 55|
   year = 2005|
   address = Brno|
   journal= Faculty of Information Technology BUT|
   note = master's thesis|
   url = http://www.fit.vutbr.cz/
}}

== Contact Information ==
* Address: Jiří Techet, [http://www.fit.vutbr.cz Faculty of Information Technology], Brno University of Technology, Božetěchova 2, Brno 61266, Czech Republic
* Email: [mailto:techet@fit.vutbr.cz techet@fit.vutbr.cz]
* Web Page: [http://www.fit.vutbr.cz/~techet/ www.fit.vutbr.cz/~techet]
 
[[User:Jiri|Jiri]] 23:55, 4 January 2008 (CET)