State Complexity of Suffix Distance - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

State Complexity of Suffix Distance

Timothy Ng
  • Function : Author
  • PersonId : 1022716
David Rappaport
  • Function : Author
  • PersonId : 1022714
Kai Salomaa
  • Function : Author
  • PersonId : 1022715

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.
Fichier principal
Vignette du fichier
440206_1_En_23_Chapter.pdf (294.82 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01656995 , version 1 (06-12-2017)

Licence

Identifiers

Cite

Timothy Ng, David Rappaport, Kai Salomaa. State Complexity of Suffix Distance. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.287-298, ⟨10.1007/978-3-319-60252-3_23⟩. ⟨hal-01656995⟩
54 View
124 Download

Altmetric

Share

More