Jumping Finite Automata

Corelab, SoftLab, ECE NTUA
Alexander Meduna
26-02-2020, 13:00
Αίθουσα Συνεδριάσεων ΣΗΜΜΥ (νέο κτήριο)

This talk proposes a new investigation area in automata theory — jumping finite automata. These automata work like classical finite automata except that they read input words discontinuously — that is, after reading a symbol, they can jump over some symbols within the words and continue their computation from there. The talk gives several results concerning jumping finite automata in terms of commonly investigated areas of automata theory, such as closure properties. Most importantly, it achieves several results that demonstrate differences between jumping finite automata and classical finite automata. In its conclusion, the talk  formulates several open problems and suggests future investigation areas.