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

Postato il

ScienzeENonSolo

logo_Unipa_title_blu_1

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.

2015-07-09_Meduna

Info ulteriori

Words and Automata Research Group

Gabriele Fici (091/238 91130, gabriele.fici@unipa.it)

Annunci

Rispondi

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

Logo WordPress.com

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

Google photo

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

Foto Twitter

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

Foto di Facebook

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

Connessione a %s...

This site uses Akismet to reduce spam. Learn how your comment data is processed.