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.
Domains
Computer Science [cs]Origin | Files produced by the author(s) |
---|