Reset Complexity of Ideal Languages Over a Binary Alphabet

Abstract : We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet.
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.262-273, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_21〉
Liste complète des métadonnées

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

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

Marina Maslennikova. Reset Complexity of Ideal Languages Over a Binary Alphabet. 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.262-273, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_21〉. 〈hal-01656997〉

Partager

Métriques

Consultations de la notice

24