Skip to Main content Skip to Navigation
Conference papers

Two Results on Discontinuous Input Processing

Abstract : First, we show that universality and other properties of general jumping finite automata are undecidable, which answers questions asked by Meduna and Zemek in 2012 [12]. Second, we close a study started by Černo and Mráz in 2010 [3] by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01633950
Contributor : Hal Ifip <>
Submitted on : Monday, November 13, 2017 - 3:32:37 PM
Last modification on : Monday, November 13, 2017 - 3:35:35 PM
Long-term archiving on: : Wednesday, February 14, 2018 - 4:05:04 PM

File

416473_1_En_16_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Vojtěch Vorel. Two Results on Discontinuous Input Processing. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.205-216, ⟨10.1007/978-3-319-41114-9_16⟩. ⟨hal-01633950⟩

Share

Metrics

Record views

84

Files downloads

157