Two Results on Discontinuous Input Processing

Abstract

First, we show that universality and other properties of general jumping finite automata are undecidable, which answers a question asked by Meduna and Zemek in 2012. Second, we close the study raised by Černo and Mráz in 2010 by proving that clearing restarting automata using contexts of size two can accept binary non-context-free languages.