Scattered Context Grammars and their Applications

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 Automata and Languages (Springer, 2000) and Elements of Compiler Design (Taylor and Francis, 2008). Along with Martin Švec, his former PhD student, he is also the co-author of Grammars with Context Conditions and Their Applications (Wiley, 2005). He has published over seventy papers related to the subject of this book.

• Vita
• Website
• Scientific Work

Jiří Techet received his PhD from the Brno University of Technology in 2008 under the supervision of Alexander Meduna. He has published several studies on scattered context grammars in such distinguished computer science journals as Acta Informatica and Theoretical Computer Science.

• Vita
• Website
• Scientific Work

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.

This book is relevant to advanced students and specialists in theoretical computer science and related areas, such as computational linguistics or discrete mathematics.

• 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

• Contents
• Introduction
• Restrictions and Extensions
• Applications in Linguistics

• 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.

• Ordered by appearance in the text.
• Last updated on 2018-01-18.
• Please, send additional errors and comments to: meduna@fit.vutbr.cz

• 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.

To buy the book, visit this website.

• Research concerning Scattered Context Grammars