State Complexity of Suffix Distance

Abstract : The neighbourhood of a regular language with respect to the prefix, suffix and subword distance is always regular and a tight bound for the state complexity of prefix distance neighbourhoods is known. We give upper bounds for the state complexity of the neighbourhood of radius k of an n state DFA (deterministic finite automaton) language with respect to the suffix distance and the subword distance, respectively. For restricted values of k and n we give a matching lower bound for the state complexity of suffix distance neighbourhoods.
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.287-298, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_23〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01656995
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:43:28
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

Timothy Ng, David Rappaport, Kai Salomaa. State Complexity of Suffix Distance. 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.287-298, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_23〉. 〈hal-01656995〉

Partager

Métriques

Consultations de la notice

14