Jumping Computation

Chapter 3Jumping One-Head Automata

As computational models, finite automata are conceptualized so simply and naturally that they definitely belong to the most intensively investigated and, perhaps even more importantly, applied automata in computer science as a whole. Recently, the theory of computation has introduced their jumping versions (see Meduna and Zemek [2012] introducing jumping finite automata) as the very first jumping mechanism in this theory. As their name suggests, these automata jump across their input strings in a discontinuous way while keeping the simple concept of their classical counterparts unchanged. The fundamental reason for this introduction was that the jumping versions properly reflect and formalize discontinuous ...