Seminario W.A.R.G. : “Jumping Grammars” – A. Meduna – 9Lug2015

Postato il



Seminario del Words and Automata Research Group

“Jumping Grammars

Alexander Meduna (Brno University of Technology) 

Giovedì 9 Luglio dalle ore 15.00 , Dip. di Matematica e Informatica , Aula 7, Via Archirafi 34, 90123 Palermo


This talk loosely continues with the discussion of jumping automata given by the author at this seminar on May 9, 2013.

 Indeed, it introduces and studies jumping grammars, which represent a grammatical counterpart to jumping automata. Jumping grammars are conceptualized just like classical grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. More precisely, a jumping grammar rewrites a string z according to a rule x -> y in such a way that it selects an occurrence of x in z, erases it, and inserts y anywhere in the rewritten string, so this insertion may occur at a different position than the erasure of x. The talk concentrates its attention on investigating the generative power of jumping grammars. More specifically, it compares this power with that of jumping automata and that of classical grammars. A special attention is paid to various context-free versions of jumping grammars, such as regular, right-linear, linear, and context-free grammars of finite index. We also demonstrate that the general versions of jumping grammars characterize the family of recursively enumerable languages. In its conclusion, the talk formulates several open problems and suggests future investigation areas.


Info ulteriori

Words and Automata Research Group

Gabriele Fici (091/238 91130,



Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di

Stai commentando usando il tuo account Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.