On some algorithmic problems regarding the hairpin completion |
| |
Authors: | Florin Manea |
| |
Institution: | a Faculty of Mathematic and Computer Science, University of Bucharest, Str. Academiei 14, 010014, Bucharest, Romania b Research Group in Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tarraco 1, 43005, Tarragona, Spain |
| |
Abstract: | We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n2f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us. |
| |
Keywords: | Hairpin completion Iterated hairpin completion Membership problem Hairpin completion distance |
本文献已被 ScienceDirect 等数据库收录! |
|