Revision as of 12:42, 23 November 2007

Introduction

Basic Definitions

Scattered Context Grammars

Results

Known Results

Normal Forms of Propagating Scattered Context Grammars

Closure Properties of Propagating Scattered Context Grammars

Extended Propagating Scattered Context Grammars

Propagating Scattered Context Grammars Using Leftmost Derivations

Power of Scattered Context Grammars

Reduction of Scattered Context Grammars

Own Research

Generation of Sentences with Their Parses

k-Limited Erasing

Scattered Context Grammars with Non-Context-Free Components

Maximal and Minimal Rewriting

n-Limited Derivations

Bibliography

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

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

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

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

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

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

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

(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. A Note on Scattered Context Grammars with Non-Context-Free Components. MEMICS 2007 Proceedings, 2007, pp. 225--232.

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

(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) 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.

(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. Částečně paralelní generování jazyků. Faculty of Information Technology BUT, 2005, pp. 55.

(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. 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) Takumi Kasai. [http://missing.pdf An Hierarchy Between Context-Free and Context-Sensitive

              Languages]. Journal of Computer and System Sciences, 1970, pp. 492-508.

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

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

(pdf) O. Ibarra. Simple Matrix Languages. Information and Control, 1970, pp. 359-394.

(pdf) A. Salomaa. Formal Languages. {{{journal}}}, 1973, pp. {{{pages}}}.

(pdf) G. Rozenberg and A. Salomaa. Handbook of Formal Languages. {{{journal}}}, 1997, pp. {{{pages}}}.

(pdf) A. Meduna. Automata and Languages: Theory and Applications. {{{journal}}}, 2000, pp. {{{pages}}}.

Jiri 12:35, 23 November 2007 (CET)