Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01656995
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:43:28 AM
Last modification on : Monday, December 7, 2020 - 9:44:02 AM

File

440206_1_En_23_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

93

Files downloads

135