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 13:45] – 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: | ||
- | This website is in preparation. | + | ===== Authors ===== |
- | + | ||
- | ===== Authors' Bio ===== | + | |
**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 25: | Line 24: | ||
* [[http:// | * [[http:// | ||
- | * [[http:// | + | |
+ | | ||
Line 42: | Line 42: | ||
==== Features ==== | ==== Features ==== | ||
- | - up-to-date coverage of the knowledge concerning scattered context grammars | + | * up-to-date coverage of the knowledge concerning scattered context grammars |
- | - self-contained explanation without assumption of any previous knowledge | + | |
- | - clear definitions and exact proofs preceded by their intuitive explanation | + | |
- | - numerous useful and easy-to-implement grammatical transformations | + | |
- | - applications with the focus on linguistics | + | |
- | - comprehensive bibliography | + | |
- | | + | ==== Samples ==== |
+ | | ||
+ | * {{: | ||
+ | * {{: | ||
+ | * {{: | ||
+ | ==== Important Journal Publications Underlying this Book ==== | ||
+ | * **by the Authors:** | ||
+ | * Meduna, A., Syntactic complexity of scattered context grammars. Acta Informatica, | ||
+ | * Meduna, A., Canonical scattered rewriting. International Journal of Computer Mathematics, | ||
+ | * Fernau, H. & Meduna, A., On the degree of scattered context-sensitivity. Theoretical Computer Science, 290, pp. 2121–2124, | ||
+ | * 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. & 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., Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages. International Journal of Computer Mathematics, | ||
+ | * Meduna, A., Economical transformations of phrase-structure grammars to scattered context grammars. Acta Cybernetica, | ||
+ | * Meduna, A., Generative power of three-nonterminal scattered context grammars. Theoretical Computer Science, 246, pp. 276–284, 2000. | ||
+ | * Meduna, A., Terminating left-hand sides of scattered context productions. Theoretical Computer Science, 237, pp. 423–427, 2000. | ||
+ | * Meduna, A., Uniform generation of languages by scattered context grammars. Fundamenta Informaticae, | ||
+ | * Meduna, A., Coincidental extension of scattered context languages. Acta Informatica, | ||
+ | * Meduna, A. & Švec, M., Grammars with Context Conditions and Their Applications. Wiley, 2005. | ||
+ | * Meduna, A. & Techet, J., Generation of sentences with their parses: the case of propagating scattered context grammars. Acta Cybernetica, | ||
+ | * Meduna, A. & Techet, J., Canonical scattered context generators of sentences with their parses. Theoretical Computer Science, 389, pp. 73–81, 2007. | ||
+ | * Meduna, A. & Techet, J., Maximal and minimal scattered context rewriting. FCT 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., An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations. Theoretical Computer Science, 410, pp. 1961-1969, 2009. | ||
+ | * 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. | ||
+ | * **by others:** | ||
+ | * Greibach, S. & Hopcroft, J., Scattered context grammars. Journal of Computer and System Sciences, 3, pp. 233–247, 1969. | ||
+ | * Virkkunen, V., On scattered context grammars. Acta Universitatis Ouluensis, 20(6), pp. 75–82, 1973. | ||
+ | * Cremers, A.B., Normal forms for context-sensitive grammars. Acta Informatica, | ||
+ | * Masopust, T., Scattered context grammars can generate the powers of 2. EEICT 2007 Proceedings, | ||
+ | * 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, | ||
+ | * 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. | ||
+ | * Gonczarowski, | ||
+ | * Vaszil, G., On the descriptional complexity of some rewriting mechanisms regulated by context conditions. Theoretical Computer Science, 330, pp. 361–373, 2005. | ||
+ | * Ehrenfeucht, | ||
+ | * Král, J., On multiple grammars. Kybernetika, | ||
+ | * Masopust, T., On the descriptional complexity of scattered context grammars. Theoretical Computer Science, 410(1), pp. 108–112, 2009. | ||
- | ===== Publications & Links ===== | + | ===== Errata |
- | * Author' | + | |
- | * [[lectures: | + | |
- | * Alexander Meduna: Automata and Languages, Springer, London, 2000 | + | |
- | * Alexander Meduna and Martin Švec: Grammars with Context Conditions and Their Applications, | + | |
- | * [[eocd_journal|Author' | + | |
- | + | ||
- | * [[eocd_publications# | + | |
- | * [[eocd_publications# | + | * Ordered by appearance in the text. |
+ | * Last updated on 2018-01-18. | ||
+ | * Please, send additional errors and comments to: [[meduna@fit.vutbr.cz? | ||
- | * [[eocd_publications# | + | ==== List of Errors ==== |
- | ===== Samples ===== | + | |
- | | + | * In Definition 2.45, instead of "// |
- | * {{: | + | * Reported 2018-01-18 by Zbyněk Křivka of Brno University of Technology. |
- | * {{: | + | |
- | * {{: | + | |
- | * {{: | + | |
- | + | ||
- | ===== Acknowledgements ===== | + | |
- | + | ||
- | * [[scg_acknowledgements|Acknowledgements]] | + | |
+ | ---- | ||
+ | The authors' | ||
- | ===== WIT press Website ===== | + | ===== WIT Press Website ===== |
To buy the book, [[http:// | To buy the book, [[http:// | ||