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

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

Abstract

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, gabriele.fici@unipa.it)

Pubblicità