Differences

This shows you the differences between two versions of the page.

--- lectures:books:scg [2009/09/01 13:41] – krivka
+++ lectures:books:scg [2018/01/31 14:31] (current) – krivka
@@ Line 1: / Line 1: @@
 ====== Scattered Context Grammars and their Applications ======
-|Authors:|**[[#authors_bio|Meduna, Alexander]]** and **[[#authors_bio|Techet, Jiří]]**|
+|Authors:|**[[#authors|Meduna, Alexander]]** and **[[#authors|Techet, Jiří]]**|
 |Title:|//Scattered Context Grammars and their Applications//|
-|Publisher:|[[http://www.witpress.com/978-1-84564-426-0.html|WITpress]]|
+|Publisher:|[[http://www.witpress.com/978-1-84564-426-0.html|WIT Press]], Ashurst Lodge, Southampton, SO40 7AA, UK|
 |ISBN:|978-1-84564-426-0|
-|Publication Date:|2009|
+|Publication Date:|2010|
+|Details:|Hardcover, 212 pages|
-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, including the University of Missouri, where he spent a decade teaching advanced topics of the formal language theory. He is the author of the books entitled //[[http://www.springer.com/computer/artificial/book/978-1-85233-074-3|Automata and Languages]]// (Springer, 2000) and //[[http://www.fit.vutbr.cz/~meduna/books/eocd|Elements of Compiler Design]]// (Taylor and Francis, 2008). Along with Martin Švec, his former PhD student, he is also the co-author of //[[http://www.fit.vutbr.cz/~meduna/books/gwcc|Grammars with Context Conditions and Their Applications]]// (Wiley, 2005).  He has published over seventy papers related to the subject of this book.
@@ Line 25: / Line 24: @@
   * [[http://www.fit.vutbr.cz/~techet/curriculum.php.en|Vita]]
-  * [[http://www.fit.vutbr.cz/~techet/pubs.php.en|Publications]]
+  * [[http://www.fit.vutbr.cz/~techet/index.php.en|Website]]
+  * [[http://www.fit.vutbr.cz/~techet/pubs.php.en|Scientific Work]]
 ===== Book =====
-  * [[scg_summary|Summary]]
-  * [[scg_summary#features|Features]]
-  * [[scg_errata|Errata]]
+==== Summary ====
-===== Publications & Links =====
+This advanced computer science book systematically and compactly summarizes the current knowledge about scattered context grammars—an important area of the formal language theory at present. Primarily, the book covers the theoretical properties of these grammars, such as generative power, closure properties, simplification, and reduction.  Secondarily, it sketches their linguistically oriented applications. In its conclusion, the book formulates new investigation areas, sketches further applications, and gives a comprehensive biography related to the scattered context grammars.
-  * Author's Related Publications:
-    * [[lectures:books:books|Books]]:
-      * Alexander Meduna: Automata and Languages, Springer, London, 2000
-      * Alexander Meduna and Martin Švec: Grammars with Context Conditions and Their Applications, Wiley, Hoboken, New Jersey, 2005
-    * [[eocd_journal|Author's Journal Articles]]
-  * [[eocd_publications#recommended_textbooks|Recommended Textbooks]]
-  * [[eocd_publications#other_related_publications|Other Related Publications]]
+==== Audiance ====
-  * [[eocd_publications#relevant_links|Relevant Links]]
+This book is relevant to advanced students and specialists in theoretical computer science and related areas, such as computational linguistics or discrete mathematics.
-===== Samples =====
+==== Features ====
-  * {{:lectures:books:1_eocd_contents_sample.pdf|Contents}}
-  * {{:lectures:books:2_eocd_preface_sample.pdf|Preface}}
-  * {{:lectures:books:3_eocd_section1.2-1.3.pdf|Sections 1.2-1.3}} (1.2 Compilation, 1.3 Rewriting Systems)
-  * {{:lectures:books:4_eocd_chapter4_sample.pdf|Chapter 4}}  Deterministic Top-Down Parsing
+  * 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
-===== Acknowledgements =====
+==== Samples ====
+  * {{:lectures:books:1_scg_contents_sample.pdf|Contents}}
+  * {{:lectures:books:2_scg_introduction_sample.pdf|Introduction}}
+  * {{:lectures:books:3_scg_restrictions_sample.pdf|Restrictions and Extensions}}
+  * {{:lectures:books:4_scg_applications_sample.pdf|Applications in Linguistics}}
-  * [[scg_acknowledgements|Acknowledgements]]
+==== Important Journal Publications Underlying this Book ====
+  * **by the Authors:**
+    * Meduna, A., Syntactic complexity of scattered context grammars. Acta Informatica, 32, pp. 285–298, 1995.
+    * Meduna, A., Canonical scattered rewriting. International Journal of Computer Mathematics, 51, pp. 122–129, 1993.
+    * Fernau, H. & Meduna, A., On the degree of scattered context-sensitivity. Theoretical Computer Science, 290, pp. 2121–2124, 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, 87(3), pp. 407–415, 2008.
+    * 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, 63, pp. 67–83, 1997.
+    * Meduna, A., Economical transformations of phrase-structure grammars to scattered context grammars. Acta Cybernetica, 13, pp. 225–242, 1998.
+    * 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, 44, pp. 231–235, 2001.
+    * Meduna, A., Coincidental extension of scattered context languages. Acta Informatica, 39, pp. 307–314, 2003.
+    * 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, 17, pp. 11–20, 2005.
+    * 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, Budapest, pp. 412–423, 2007.
+    * Meduna, A. & Techet, J., Reduction of scattered context generators of sentences preceded by their leftmost parses. DCFS 2007 Proceedings, High Tatras, pp. 178–185, 2007.
+    * Meduna, A. & Techet, J., Scattered context grammars that erase nonterminals in a generalized k-limited way. Acta Informatica, 45(7), pp. 593–608, 2008.
+    * 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, Znojmo, pp. 225–232, 2007.
+    * 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, 3, pp. 59–73, 1973.
+    * Masopust, T., Scattered context grammars can generate the powers of 2. EEICT 2007 Proceedings, Brno, pp. 401–404, 2007.
+    * 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, 16(3), pp. 245–253, 1982.
+    * 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, J. & Warmuth, M.K., Scattered versus context-sensitive rewriting. Acta Informatica, 27, pp. 81–95, 1989.
+    * Vaszil, G., On the descriptional complexity of some rewriting mechanisms regulated by context conditions. Theoretical Computer Science, 330, pp. 361–373, 2005.
+    * Ehrenfeucht, A. & Rozenberg, G., An observation on scattered grammars. Information Processing Letters, 9(2), pp. 84–85, 1979.
+    * Král, J., On multiple grammars. Kybernetika, 1, pp. 60–85, 1969.
+    * 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?Subject=SCGA: Error report|meduna@fit.vutbr.cz]]
+==== List of Errors ====
+  * Page 26, Chapter 2 (Definitions), Section 2.3 (Scattered context grammars)
+  * In Definition 2.45, instead of "//lhs(p) ≥ 2//", there should be "//len(p) ≥ 2//" in the definition of dcs(//G//).
+  * Reported 2018-01-18 by Zbyněk Křivka of Brno University of Technology.
+----
+The authors' thanks go to the readers who pointed out the errors.
-===== WIT press Website =====
+===== WIT Press Website =====
 To buy the book, [[http://www.witpress.com/978-1-84564-426-0.html|visit this website]].