State Complexity of Prefix Distance of Subregular Languages

Abstract : The neighbourhood of a regular language of constant radius with respect to the prefix distance is always regular. We give upper bounds and matching lower bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius k prefix distance neighbourhood of an n state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined over a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.
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.192-204, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_15〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01633944
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:18
Dernière modification le : lundi 13 novembre 2017 - 15:35:38
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:08:24

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

David Rappaport, Kai Salomaa, Timothy Ng. State Complexity of Prefix Distance of Subregular Languages. 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.192-204, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_15〉. 〈hal-01633944〉

Partager

Métriques

Consultations de la notice

27