Efficient Identification of k-Closed Strings

Hayam Alamro; Mai Alzamel; Costas S. Iliopoulos; Solon P. Pissis; Steven Watts; Wing-Kin Sung

doi:10.1007/978-3-319-65172-9_49

Efficient Identification of k-Closed Strings

Hayam Alamro, Mai Alzamel, Costas S. Iliopoulos, Solon P. Pissis, Steven Watts, Wing-Kin Sung

Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution › peer-review

2 Citations (Scopus)

Abstract

A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying whether or not a given string of length n over an integer alphabet is k-closed and additionally specifying the border resulting in the string being k-closed. Specifically, we present an O(kn)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.

Original language	English
Title of host publication	Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings
Editors	Giacomo Boracchi, Lazaros Iliadis, Chrisina Jayne, Aristidis Likas
Place of Publication	Cham
Publisher	Springer International Publishing Switzerland
Pages	583-595
Number of pages	13
Volume	744
ISBN (Electronic)	978-3-319-65172-9
ISBN (Print)	978-3-319-65171-2
DOIs	https://doi.org/10.1007/978-3-319-65172-9_49
Publication status	E-pub ahead of print - 2 Aug 2017

Access to Document

10.1007/978-3-319-65172-9_49

Cite this

Alamro, H., Alzamel, M., Iliopoulos, C. S., Pissis, S. P., Watts, S., & Sung, W.-K. (2017). Efficient Identification of k-Closed Strings. In G. Boracchi, L. Iliadis, C. Jayne, & A. Likas (Eds.), Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings (Vol. 744, pp. 583-595). Springer International Publishing Switzerland. Advance online publication. https://doi.org/10.1007/978-3-319-65172-9_49

Alamro, Hayam ; Alzamel, Mai ; Iliopoulos, Costas S. et al. / Efficient Identification of k-Closed Strings. Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. editor / Giacomo Boracchi ; Lazaros Iliadis ; Chrisina Jayne ; Aristidis Likas. Vol. 744 Cham : Springer International Publishing Switzerland, 2017. pp. 583-595

@inbook{58931e5cfeba44559177d4562c33b452,

title = "Efficient Identification of k-Closed Strings",

abstract = "A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying whether or not a given string of length n over an integer alphabet is k-closed and additionally specifying the border resulting in the string being k-closed. Specifically, we present an O(kn)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.",

author = "Hayam Alamro and Mai Alzamel and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Steven Watts and Wing-Kin Sung",

year = "2017",

month = aug,

day = "2",

doi = "10.1007/978-3-319-65172-9_49",

language = "English",

isbn = "978-3-319-65171-2",

volume = "744",

pages = "583--595",

editor = "Giacomo Boracchi and Lazaros Iliadis and Chrisina Jayne and Aristidis Likas",

booktitle = "Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings",

publisher = "Springer International Publishing Switzerland",

}

Alamro, H , Alzamel, M , Iliopoulos, CS , Pissis, SP , Watts, S & Sung, W-K 2017, Efficient Identification of k-Closed Strings. in G Boracchi, L Iliadis, C Jayne & A Likas (eds), Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. vol. 744, Springer International Publishing Switzerland, Cham, pp. 583-595. https://doi.org/10.1007/978-3-319-65172-9_49

Efficient Identification of k-Closed Strings. / Alamro, Hayam ; Alzamel, Mai ; Iliopoulos, Costas S. et al.
Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. ed. / Giacomo Boracchi; Lazaros Iliadis; Chrisina Jayne; Aristidis Likas. Vol. 744 Cham: Springer International Publishing Switzerland, 2017. p. 583-595.

Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution › peer-review

TY - CHAP

T1 - Efficient Identification of k-Closed Strings

AU - Alamro, Hayam

AU - Alzamel, Mai

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Watts, Steven

AU - Sung, Wing-Kin

PY - 2017/8/2

Y1 - 2017/8/2

N2 - A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying whether or not a given string of length n over an integer alphabet is k-closed and additionally specifying the border resulting in the string being k-closed. Specifically, we present an O(kn)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.

AB - A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying whether or not a given string of length n over an integer alphabet is k-closed and additionally specifying the border resulting in the string being k-closed. Specifically, we present an O(kn)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.

U2 - 10.1007/978-3-319-65172-9_49

DO - 10.1007/978-3-319-65172-9_49

M3 - Other chapter contribution

SN - 978-3-319-65171-2

VL - 744

SP - 583

EP - 595

BT - Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings

A2 - Boracchi, Giacomo

A2 - Iliadis, Lazaros

A2 - Jayne, Chrisina

A2 - Likas, Aristidis

PB - Springer International Publishing Switzerland

CY - Cham

ER -

Alamro H , Alzamel M , Iliopoulos CS , Pissis SP , Watts S, Sung WK. Efficient Identification of k-Closed Strings. In Boracchi G, Iliadis L, Jayne C, Likas A, editors, Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. Vol. 744. Cham: Springer International Publishing Switzerland. 2017. p. 583-595 Epub 2017 Aug 2. doi: 10.1007/978-3-319-65172-9_49

Efficient Identification of k-Closed Strings

Abstract

Access to Document

Fingerprint

Cite this