State Complexity of Prefix Distance of Subregular Languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

State Complexity of Prefix Distance of Subregular Languages

David Rappaport
  • Fonction : Auteur
  • PersonId : 1022714
Kai Salomaa
  • Fonction : Auteur
  • PersonId : 1022715
Timothy Ng
  • Fonction : Auteur
  • PersonId : 1022716

Résumé

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.
Fichier principal
Vignette du fichier
416473_1_En_15_Chapter.pdf (286.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01633944 , version 1 (13-11-2017)

Licence

Paternité

Identifiants

Citer

David Rappaport, Kai Salomaa, Timothy Ng. State Complexity of Prefix Distance of Subregular Languages. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.192-204, ⟨10.1007/978-3-319-41114-9_15⟩. ⟨hal-01633944⟩
32 Consultations
111 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More