The Taub Faculty of Computer Science Events and Talks

We introduce and study jumping automata over infinite words, a fascinating twist on traditional finite automata. These machines read their input in a non-consecutive manner, defying conventional word order. We explore three distinct semantics: one ensuring every letter is accounted for, another permitting word permutation within fixed windows, and a third allowing permutation within windows of an existentially-quantified bound. Our work covers expressiveness, closure properties, algorithmic characteristics of these models, and more.