This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
lectures:books:scg [2009/09/01 14:18] – krivka | lectures:books:scg [2018/01/31 14:31] (current) – krivka | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Scattered Context Grammars and their Applications ====== | ====== Scattered Context Grammars and their Applications ====== | ||
- | |Authors: | + | |Authors: |
|Title: | |Title: | ||
|Publisher: | |Publisher: | ||
|ISBN: | |ISBN: | ||
- | |Publication Date:|2009| | + | |Publication Date:|2010| |
|Details: | |Details: | ||
- | ===== Authors' Bio ===== | + | ===== Authors ===== |
**Alexander Meduna**, Full Professor of Computer Science at the Brno University of Technology, received his PhD from this university in 1988. He has taught theoretical computer science at various European, Asian, and American universities, | **Alexander Meduna**, Full Professor of Computer Science at the Brno University of Technology, received his PhD from this university in 1988. He has taught theoretical computer science at various European, Asian, and American universities, | ||
Line 24: | Line 24: | ||
* [[http:// | * [[http:// | ||
- | * [[http:// | + | |
+ | | ||
Line 62: | Line 63: | ||
* Fernau, H. & Meduna, A., A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. Information Processing Letters, 86, pp. 235–240, 2003. | * Fernau, H. & Meduna, A., A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. Information Processing Letters, 86, pp. 235–240, 2003. | ||
* Masopust, T. & Meduna, A., On descriptional complexity of partially parallel grammars. Fundamenta Informaticae, | * Masopust, T. & Meduna, A., On descriptional complexity of partially parallel grammars. Fundamenta Informaticae, | ||
+ | * Masopust, T. & Techet, J., Leftmost derivations of propagating scattered context grammars: A new proof. Discrete Mathematics and Theoretical Computer Science, 10(2), pp. 39–46, 2008. | ||
* Meduna, A., A trivial method of characterizing the family of recursively enumerable languages by scattered context grammars. EATCS Bulletin, 56, pp. 104–106, 1995. | * Meduna, A., A trivial method of characterizing the family of recursively enumerable languages by scattered context grammars. EATCS Bulletin, 56, pp. 104–106, 1995. | ||
* Meduna, A., Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages. International Journal of Computer Mathematics, | * Meduna, A., Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages. International Journal of Computer Mathematics, | ||
Line 75: | Line 77: | ||
* Meduna, A. & Techet, J., Reduction of scattered context generators of sentences preceded by their leftmost parses. DCFS 2007 Proceedings, | * Meduna, A. & Techet, J., Reduction of scattered context generators of sentences preceded by their leftmost parses. DCFS 2007 Proceedings, | ||
* Meduna, A. & Techet, J., Scattered context grammars that erase nonterminals in a generalized k-limited way. Acta Informatica, | * Meduna, A. & Techet, J., Scattered context grammars that erase nonterminals in a generalized k-limited way. Acta Informatica, | ||
- | * Meduna, A. & Techet, J., An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations. Theoretical Computer Science, | + | * Meduna, A. & Techet, J., An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations. Theoretical Computer Science, |
* Techet, J., A note on scattered context grammars with non-context-free components. MEMICS 2007 Proceedings, | * Techet, J., A note on scattered context grammars with non-context-free components. MEMICS 2007 Proceedings, | ||
* Techet, J., Scattered Context in Formal Languages. Ph.D. thesis, Brno University of Technology, Faculty of Information Technology, 2008. | * Techet, J., Scattered Context in Formal Languages. Ph.D. thesis, Brno University of Technology, Faculty of Information Technology, 2008. | ||
Line 85: | Line 87: | ||
* Milgram, D. & Rosenfeld, A., A note on scattered context grammars. Information Processing Letters, 1, pp. 47–50, 1971. | * Milgram, D. & Rosenfeld, A., A note on scattered context grammars. Information Processing Letters, 1, pp. 47–50, 1971. | ||
* Paun, G., On simple matrix languages versus scattered context languages. Informatique Théorique et Applications, | * Paun, G., On simple matrix languages versus scattered context languages. Informatique Théorique et Applications, | ||
- | * Masopust, T. & Techet, J., Leftmost derivations of propagating scattered context grammars: A new proof. Discrete Mathematics and Theoretical Computer Science, 10(2), pp. 39–46, 2008. | ||
* Mayer, O., Some restrictive devices for context-free grammars. Information and Control, 20, pp. 69–92, 1972. | * Mayer, O., Some restrictive devices for context-free grammars. Information and Control, 20, pp. 69–92, 1972. | ||
* Fernau, H., Scattered context grammars with regulation. Annals of Bucharest University, Mathematics-Informatics Series, 45(1), pp. 41–49, 1996. | * Fernau, H., Scattered context grammars with regulation. Annals of Bucharest University, Mathematics-Informatics Series, 45(1), pp. 41–49, 1996. | ||
Line 94: | Line 95: | ||
* Masopust, T., On the descriptional complexity of scattered context grammars. Theoretical Computer Science, 410(1), pp. 108–112, 2009. | * Masopust, T., On the descriptional complexity of scattered context grammars. Theoretical Computer Science, 410(1), pp. 108–112, 2009. | ||
+ | ===== Errata ===== | ||
+ | |||
+ | * Ordered by appearance in the text. | ||
+ | * Last updated on 2018-01-18. | ||
+ | * Please, send additional errors and comments to: [[meduna@fit.vutbr.cz? | ||
+ | |||
+ | ==== List of Errors ==== | ||
+ | |||
+ | * Page 26, Chapter 2 (Definitions), | ||
+ | * In Definition 2.45, instead of "// | ||
+ | * Reported 2018-01-18 by Zbyněk Křivka of Brno University of Technology. | ||
+ | |||
+ | ---- | ||
+ | |||
+ | The authors' | ||
===== WIT Press Website ===== | ===== WIT Press Website ===== |