State Complexity of Neighbourhoods and Approximate Pattern Matching

dc.contributor.authorNg, Timothyen
dc.contributor.authorRappaport, Daviden
dc.contributor.authorSalomaa, Kaien
dc.date.accessioned2018-05-09T14:39:27Z
dc.date.available2018-05-09T14:39:27Z
dc.date.issued2018-02
dc.description.abstractThe neighbourhood of a language L with respect to an additive distance consists of all strings that have distance at most the given radius from some string of L. We show that the worst case deterministic state complexity of a radius r neighbourhood of a language recognized by an n state nondeterministic finite automaton A is (r+2)n - 1. In the case where A is deterministic we get the same lower bound for the state complexity of the neighbourhood if we use an additive quasi-distance. The lower bound constructions use an alphabet of size linear in n. We show that the worst case state complexity of the set of strings that contain a substring within distance $r$ from a string recognized by A is (r+2){n-2} + 1.en
dc.identifier.citationTimothy Ng, David Rappaport, and Kai Salomaa, Int. J. Found. Comput. Sci. 29, 315 (2018).en
dc.identifier.urihttp://hdl.handle.net/1974/24211
dc.language.isoenen
dc.publisherWorld Scientificen
dc.subjectRegular Languagesen
dc.subjectState Complexityen
dc.subjectLower Boundsen
dc.titleState Complexity of Neighbourhoods and Approximate Pattern Matchingen
dc.typejournal articleen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
neighbourhoods.pdf
Size:
363.02 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
3.77 KB
Format:
Item-specific license agreed upon to submission
Description: