The set of parameterized k-covers problem / Gorbenko A. A.,Popov V. Yu. // THEORETICAL COMPUTER SCIENCE. - 2012. - V. 423, l. . - P. 19-24.

ISSN/EISSN:

0304-3975 / нет данных

Type:

Article

Abstract:

The problem of the set of k-covers is a distance measure for strings. Another well-studied string comparison measure is that of parameterized matching. We consider the problem of the set of parameterized k-covers (k-SPC) which combines k-cover measure with parameterized matching. We prove that k-SPC is NP-complete. We describe an approach to solve k-SPC. This approach is based on constructing a logical model for k-SPC. (C) 2011 Elsevier B.V. All rights reserved.

Author keywords:

Parameterized pattern matching; Set of k-covers; NP-complete; Logical models STRINGS

DOI:

10.1016/j.tcs.2011.12.052

Web of Science ID:

ISI:000300964200003

Соавторы в МНС:

Другие поля

Поле	Значение
Month	MAR 16
Publisher	ELSEVIER SCIENCE BV
Address	PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
Language	English
Keywords-Plus	STRINGS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	gorbenko.aa@gmail.com Vladimir.Popov@usu.ru
ResearcherID-Numbers	Popov, Vladimir/C-9868-2015 Popov, Vladimir/J-1440-2012 Gorbenko, Anna/M-6421-2016
ORCID-Numbers	Popov, Vladimir/0000-0001-9671-681X Gorbenko, Anna/0000-0001-9777-7294
Funding-Acknowledgement	Analytical Departmental Program ``Developing the scientific potential of high school{''} {[}2.1.1/14055]
Funding-Text	The work was partially supported by Analytical Departmental Program ``Developing the scientific potential of high school{''} 2.1.1/14055.
Number-of-Cited-References	25
Usage-Count-Last-180-days	2
Usage-Count-Since-2013	35
Journal-ISO	Theor. Comput. Sci.
Doc-Delivery-Number	901JW