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
Liste complète des métadonnées
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:43:28 AM
Last modification on : Wednesday, December 6, 2017 - 1:46:24 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2020-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Timothy Ng, David Rappaport, Kai Salomaa. State Complexity of Suffix Distance. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.287-298, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_23〉. 〈hal-01656995〉



Record views