Seminario del Words and Automata Research Group
Alexander Meduna (Brno University of Technology)
Giovedì 9 Luglio dalle ore 15.00 , Dip. di Matematica e Informatica , Aula 7, Via Archiraﬁ 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 speciﬁcally, 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 ﬁnite 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.
Gabriele Fici (091/238 91130, gabriele.ﬁci@unipa.it)