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.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.205-216, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_16〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01633950
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:37
Dernière modification le : lundi 13 novembre 2017 - 15:35:35
Document(s) archivé(s) le : mercredi 14 février 2018 - 16:05:04

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Vojtěch Vorel. Two Results on Discontinuous Input Processing. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.205-216, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_16〉. 〈hal-01633950〉

Partager

Métriques

Consultations de la notice

27