pith. sign in

arxiv: 1511.08642 · v1 · pith:YYXFGOC5new · submitted 2015-11-27 · 💻 cs.FL

Two Results on Discontinuous Input Processing

classification 💻 cs.FL
keywords automataacceptanswersaskedbinaryclearingclosecontexts
0
0 comments X
read the original 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 \v{C}erno and Mr\'{a}z in 2010 by proving that clearing restarting automata using contexts of size two can accept binary non-context-free languages.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.