[FM] A. Meduna, Z. Křivka: Jumping Pure Grammars

The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.

Author: Alexander Meduna (FIT, BUT) and Zbyněk Křivka (FIT, BUT)
Title: Jumping Pure Grammars
Abstract: This talk will introduce jumping pure grammars, which are conceptualized just like classical pure grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. We will compare the generative power of jumping pure grammars with that of classical pure grammars while distinguishing between their versions with and without erasing productions. Apart from sequential versions, we will present an analogical study in terms of parallel versions of jumping pure grammars represented by 0L grammars. During the talk, several open problems will be introduced to suggest the future investigation of jumping pure grammars.