Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

State Complexity of Prefix Distance of Subregular Languages

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

Cited literature [16 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, November 13, 2017 - 3:32:18 PM
Last modification on : Monday, December 7, 2020 - 9:44:02 AM
Long-term archiving on: : Wednesday, February 14, 2018 - 3:08:24 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads