Difference between revisions of "Scattered Context Grammars research"
Line 121: | Line 121: | ||
authors = J. Techet| | authors = J. Techet| | ||
title = A Note on Scattered Context Grammars with Non-Context-Free Components| | title = A Note on Scattered Context Grammars with Non-Context-Free Components| | ||
− | pages = 225 | + | pages = 225-232| |
journal = MEMICS 2007 Proceedings| | journal = MEMICS 2007 Proceedings| | ||
year = 2007| | year = 2007| | ||
Line 231: | Line 231: | ||
volume = 20| | volume = 20| | ||
year = 1983| | year = 1983| | ||
− | pages = 391 | + | pages = 391-411| |
url = http://missing.pdf | url = http://missing.pdf | ||
}} | }} | ||
Line 269: | Line 269: | ||
authors = G. Rozenberg and A. Salomaa| | authors = G. Rozenberg and A. Salomaa| | ||
title = Handbook of Formal Languages| | title = Handbook of Formal Languages| | ||
− | volume = 1 | + | volume = 1-3| |
publisher = Springer| | publisher = Springer| | ||
address = Berlin| | address = Berlin| |
Revision as of 12:44, 23 November 2007
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 Bibliography
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. 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)