Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Difference between revisions of "Scattered Context Grammars research"
Line 1: Line 1:
 
<font color="#ff0000">'''''!!! WORK IN PROGRESS - Please do not read :-) !!!'''''</font>
 
<font color="#ff0000">'''''!!! WORK IN PROGRESS - Please do not read :-) !!!'''''</font>
  
−
= Introduction =
+
== 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  
 
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  
  
Line 28: Line 28:
 
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 context-sensitive grammars.
 
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 context-sensitive grammars.
  
−
= Basic Definitions =
+
== Basic Definitions ==
  
−
== Formal Languages ==
+
=== Formal Languages ===
 
The reader is expected to be familiar with the basics of formal language theory. This section is meant to describe the used terminology rather than to explain the basics of formal language theory.
 
The reader is expected to be familiar with the basics of formal language theory. This section is meant to describe the used terminology rather than to explain the basics of formal language theory.
  
Line 64: Line 64:
 
   url = http://missing.pdf
 
   url = http://missing.pdf
 
}}
 
}}
−
== Scattered Context Grammars ==
+
=== Scattered Context Grammars ===
 
{{cite |  
 
{{cite |  
 
   authors    = S. Greibach, J. Hopcroft |
 
   authors    = S. Greibach, J. Hopcroft |
Line 74: Line 74:
 
   url      = http://missing.pdf
 
   url      = http://missing.pdf
 
}}
 
}}
−
= Results =
+
== Results ==
  
−
== Known Results ==
+
=== Known Results ===
  
−
=== Normal Forms of Propagating Scattered Context Grammars ===
+
==== Normal Forms of Propagating Scattered Context Grammars ====
 
{{cite |  
 
{{cite |  
 
   authors    = S. Greibach, J. Hopcroft |
 
   authors    = S. Greibach, J. Hopcroft |
Line 88: Line 88:
 
   url      = http://missing.pdf
 
   url      = http://missing.pdf
 
}}
 
}}
−
=== Closure Properties of Propagating Scattered Context Grammars ===
+
==== Closure Properties of Propagating Scattered Context Grammars ====
 
{{cite |  
 
{{cite |  
 
   authors    = S. Greibach, J. Hopcroft |
 
   authors    = S. Greibach, J. Hopcroft |
Line 98: Line 98:
 
   url      = http://missing.pdf
 
   url      = http://missing.pdf
 
}}
 
}}
−
=== Extended Propagating Scattered Context Grammars ===
+
==== Extended Propagating Scattered Context Grammars ====
 
{{cite |  
 
{{cite |  
 
   authors    = J. Gonczarowski, M. K. Warmuth |
 
   authors    = J. Gonczarowski, M. K. Warmuth |
Line 109: Line 109:
 
}}
 
}}
  
−
=== Propagating Scattered Context Grammars Using Leftmost Derivations ===
+
==== Propagating Scattered Context Grammars Using Leftmost Derivations ====
 
{{cite |  
 
{{cite |  
 
   authors    = V. Virkkunen |  
 
   authors    = V. Virkkunen |  
Line 120: Line 120:
 
}}
 
}}
  
−
=== Power of Scattered Context Grammars ===
+
==== Power of Scattered Context Grammars ====
 
{{cite |  
 
{{cite |  
 
   authors    = V. Virkkunen |  
 
   authors    = V. Virkkunen |  
Line 131: Line 131:
 
}}
 
}}
  
−
=== Reduction of Scattered Context Grammars ===
+
==== Reduction of Scattered Context Grammars ====
 
{{cite |  
 
{{cite |  
 
   authors = A. Meduna|
 
   authors = A. Meduna|
Line 161: Line 161:
 
   url      = http://missing.pdf
 
   url      = http://missing.pdf
 
}}
 
}}
−
== Own Research ==
+
=== Own Research ===
  
−
=== Generation of Sentences with Their Parses ===
+
==== Generation of Sentences with Their Parses ====
 
{{cite |  
 
{{cite |  
 
   authors = A. Meduna, J. Techet|
 
   authors = A. Meduna, J. Techet|
Line 214: Line 214:
 
}}
 
}}
  
−
=== k-Limited Erasing ===
+
==== k-Limited Erasing ====
  
 
{{cite |  
 
{{cite |  
Line 226: Line 226:
 
}}
 
}}
  
−
=== Scattered Context Grammars with Non-Context-Free Components ===
+
==== Scattered Context Grammars with Non-Context-Free Components ====
  
 
{{cite |  
 
{{cite |  
Line 260: Line 260:
  
  
−
=== Maximal and Minimal Rewriting ===
+
==== Maximal and Minimal Rewriting ====
  
 
{{cite |  
 
{{cite |  
Line 285: Line 285:
  
  
−
=== n-Limited Derivations ===
+
==== n-Limited Derivations ====
  
  
Line 300: Line 300:
  
  
−
= Related Literature =
+
== Related Literature ==
  
 
{{cite |  
 
{{cite |  

Revision as of 11:46, 26 November 2007

!!! WORK IN PROGRESS - Please do not read :-) !!!

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

(A, B, C) \rightarrow (a, b, c)

which consists of three context-free productions,

A \rightarrow aA, B \rightarrow bB, C \rightarrow cC,

is applicable to the sentential form aAbBcC, so

aAbBcC \Rightarrow aaAbbBccC.

It is easy to see that by adding productions

S \rightarrow ABC

and

(A, B, C) \rightarrow (a, b, c),

where S is the start symbol of the grammar, we can easily describe the non-context-free language

\{a^nb^nc^n : n \geq 1 \}.

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 context-sensitive grammars.

Basic Definitions

Formal Languages

The reader is expected to be familiar with the basics of formal language theory. This section is meant to describe the used terminology rather than to explain the basics of formal language theory.


(pdf) A. Salomaa. Formal Languages. Academic Press, 1973, pp. 322.

(pdf) G. Rozenberg and A. Salomaa. Handbook of Formal Languages. Springer, 1997, pp. 2051.

(pdf) A. Meduna. Automata and Languages: Theory and Applications. Springer, 2000, pp. 920.

Scattered Context Grammars

(pdf) S. Greibach, J. Hopcroft. Scattered Context Grammars. Journal of Computer and System Sciences, 1969, pp. 233-247.

Results

Known Results

Normal Forms of Propagating Scattered Context Grammars

(pdf) S. Greibach, J. Hopcroft. Scattered Context Grammars. Journal of Computer and System Sciences, 1969, pp. 233-247.

Closure Properties of Propagating Scattered Context Grammars

(pdf) S. Greibach, J. Hopcroft. Scattered Context Grammars. Journal of Computer and System Sciences, 1969, pp. 233-247.

Extended Propagating Scattered Context Grammars

(pdf) J. Gonczarowski, M. K. Warmuth. Scattered Versus Context-Sensitive Rewriting. Acta Informatica, 1989, pp. 81-95.

Propagating Scattered Context Grammars Using Leftmost Derivations

(pdf) V. Virkkunen. On Scattered Context Grammars. Acta Universitatis Ouluensis, 1973, pp. 75-82.

Power of Scattered Context Grammars

(pdf) V. Virkkunen. On Scattered Context Grammars. Acta Universitatis Ouluensis, 1973, pp. 75-82.

Reduction of Scattered Context Grammars

(pdf) A. Meduna. Generative Power of Three-Nonterminal Scattered Context Grammars. Theoretical Computer Science, 2000, pp. 625-631.

(pdf) A. Meduna. Economical Transformations of Scattered Context Grammars to Phrase-Structure Grammars. Acta Cybernetica, 1998, pp. 225-242.

(pdf) G. Vaszil. On the Descriptional Complexity of Some Rewriting Mechanisms Regulated by Context Conditions. Theoretical Computer Science, 2005, pp. 361-373.

Own Research

Generation of Sentences with Their Parses

(pdf) A. Meduna, J. Techet. Generation of Sentences with Their Parses: the Case of Propagating Scattered Context Grammars. Acta Cybernetica, 2005, pp. 11-20.

(pdf) J. Techet. Scattered Context Generators of Sentences with Their Parses. Pre-proceedings of the 1st Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, 2005, pp. 68-77. (pdf) A. Meduna, J. Techet. Canonical Scattered Context Generators of Sentences with Their Parses (to appear). Theoretical Computer Science, 2007/8, pp. ???-???. (pdf) A. Meduna, J. Techet. Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses. Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems, 2007, pp. 178-185.

(pdf) H. C. M. Kleijn and G. Rozenberg. On the Generative Power of Regular Pattern Grammars. Acta Informatica, 1983, pp. 391-411.

k-Limited Erasing

(pdf) J. Techet. k-Limited Erasing Performed by Scattered Context Grammars. Proceedings of the 2nd International Workshop on Formal Models WFM '07, 2007, pp. 227-234.

Scattered Context Grammars with Non-Context-Free Components

(pdf) J. Techet. A Note on Scattered Context Grammars with Non-Context-Free Components. MEMICS 2007 Proceedings, 2007, pp. 225-232. (pdf) O. Ibarra. Simple Matrix Languages. Information and Control, 1970, pp. 359-394.

(pdf) G. Paun. Linear Simple Matrix Languages. Elektronische Informationsverarbeitung und Kybernetik, 1978, pp. 377-384.


Maximal and Minimal Rewriting

(pdf) A. Meduna, J. Techet. Maximal and Minimal Scattered Context Rewriting. FCT 2007 Proceedings, 2007, pp. 412-423.

(pdf) Takumi Kasai. An Hierarchy Between Context-Free and Context-Sensitive Languages. Journal of Computer and System Sciences, 1970, pp. 492-508.


n-Limited Derivations

(pdf) Takumi Kasai. An Hierarchy Between Context-Free and Context-Sensitive Languages. Journal of Computer and System Sciences, 1970, pp. 492-508.


Related Literature

(pdf) H. Fernau. Scattered Context Grammars with Regulation. Annals of Bucharest University, Mathematics-Informatics Series, 1996, pp. 41-49.

(pdf) D. Milgram, A Rosenfeld. A Note on Scattered Context Grammars. Information Processing Letters, 1971, pp. 47-50.

(pdf) Armin B. Cremers. Normal Forms for Context-Sensitive Grammars. Acta Informatica, 1973, pp. 59-73.

(pdf) J. Techet. Částečně paralelní generování jazyků. Faculty of Information Technology BUT, 2005, pp. 55.


Jiri 11:06, 26 November 2007 (CET)

Retrieved from "https://labraj.feri.um.si/en/index.php?title=Scattered_Context_Grammars_research&oldid=2609"