A Pumping Lemma for Ordered Restarting Automata

Abstract : While stateless ordered restarting automata accept exactly the regular languages, it is known that ordered restarting automata with states accept some languages that are not even growing context-sensitive. In fact, the class of languages accepted by these automata is an abstract family of languages that is incomparable to the (deterministic) linear languages, the (deterministic) context-free languages, and the growing context-sensitive languages with respect to inclusion, and the emptiness problem is decidable for these automata. These results were derived using a Cut-and-Paste Lemma for ordered restarting automata that is based on Higman’s theorem. Here we extend the arguments used in that proof to actually derive a real Pumping Lemma for these automata. Based on this Pumping Lemma, we then prove that the finiteness problem is also decidable for these automata, and that the only unary languages these automata accept are the regular ones.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.226-237, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01656996
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:43:31
Dernière modification le : mercredi 6 décembre 2017 - 13:46:24

Fichier

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

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Kent Kwee, Friedrich Otto. A Pumping Lemma for Ordered Restarting Automata. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.226-237, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_18〉. 〈hal-01656996〉

Partager

Métriques

Consultations de la notice

29