2015/11/27 by Vorel, Vojtěch
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1511.08642
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.