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
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:43:28 AM
Last modification on : Monday, December 7, 2020 - 9:44:02 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads