Scattered Context Grammars research
!!! WORK IN PROGRESS - Please do not read - and I'm serious about it :-) !!!
Contents
- 1 Introduction
- 2 Basic Definitions
- 3 Results
- 3.1 Known Results
- 3.1.1 Normal Forms of Propagating Scattered Context Grammars
- 3.1.2 Closure Properties of Propagating Scattered Context Grammars
- 3.1.3 Extended Propagating Scattered Context Grammars
- 3.1.4 Propagating Scattered Context Grammars Using Leftmost Derivations
- 3.1.5 Power of Scattered Context Grammars
- 3.1.6 Reduction of Scattered Context Grammars
- 3.2 Own Research
- 3.1 Known Results
- 4 Related Literature
- 5 Contact Information
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
which consists of three context-free productions,
,
is applicable to the sentential form , so
.
It is easy to see that by adding productions
and
,
where is the start symbol of the grammar, we can easily describe the non-context-free language
.
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.
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, is referred to as the empty string. The length of a string , denoted by |x|, is the number of elements in x. For , denotes the number of occurrences of elements from U in a string x. By , we denote the set of all strings over V; . Any subset is a language over T. By we denote the set of all symbols occurring in a string x. Set
For all the ith power of x, denoted by , is recursively defined as (1) and (2) for . The reversal of x, denoted by , is x written in the reverse order. The right quotient of with respect to , denoted by , is defined as
;
similarly, the left quotient of with respect to , denoted by , is defined as
We also use a special type of the right and the left quotient. The exhaustive right quotient of with respect to , denoted by , is defined as
;
similarly, the exhaustive left quotient of with respect to , denoted by , is defined as
References
(pdf) A. Meduna. Automata and Languages: Theory and Applications. Springer, 2000, pp. 920.
(pdf) G. Rozenberg and A. Salomaa. Handbook of Formal Languages. Springer, 1997, pp. 2051.
(pdf) A. Salomaa. Formal Languages. Academic Press, 1973, pp. 322.
Scattered Context Grammars
References
(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
Based on
(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
Based on
(pdf) S. Greibach, J. Hopcroft. Scattered Context Grammars. Journal of Computer and System Sciences, 1969, pp. 233-247.
Extended Propagating Scattered Context Grammars
Based on
(pdf) J. Gonczarowski, M. K. Warmuth. Scattered Versus Context-Sensitive Rewriting. Acta Informatica, 1989, pp. 81-95.
Propagating Scattered Context Grammars Using Leftmost Derivations
Based on
(pdf) V. Virkkunen. On Scattered Context Grammars. Acta Universitatis Ouluensis, 1973, pp. 75-82.
Power of Scattered Context Grammars
Based on
(pdf) V. Virkkunen. On Scattered Context Grammars. Acta Universitatis Ouluensis, 1973, pp. 75-82.
Reduction of Scattered Context Grammars
Based on
(pdf) A. Meduna. Economical Transformations of Scattered Context Grammars to Phrase-Structure Grammars. Acta Cybernetica, 1998, pp. 225-242.
(pdf) A. Meduna. Generative Power of Three-Nonterminal Scattered Context Grammars. Theoretical Computer Science, 2000, pp. 625-631.
(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
Based on
(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) A. Meduna, J. Techet. Canonical Scattered Context Generators of Sentences with Their Parses (to appear). Theoretical Computer Science, 2007/8, pp. ???-???.
(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. 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.
References
(pdf) V. Geffert. Context-Free-Like Forms for the Phrase-Structure Grammars. Proceedings of the Mathematical Foundations of Computer Science 1988, 1988, pp. 309-317.
(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
Based on
(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
Based on
(pdf) J. Techet. A Note on Scattered Context Grammars with Non-Context-Free Components. MEMICS 2007 Proceedings, 2007, pp. 225-232.
References
(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
Based on
(pdf) A. Meduna, J. Techet. Maximal and Minimal Scattered Context Rewriting. FCT 2007 Proceedings, 2007, pp. 412-423.
References
(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
References
(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.
Contact Information
- Email: mailto:techet@fit.vutbr.cz techet@fit.vutbr.cz
- Web Page: www.fit.vutbr.cz/~techet
Jiri 11:06, 26 November 2007 (CET)