Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Interdisciplinary Nature of Information Processing Special Issue Dedicated to Giancarlo Mauri on the Occasion of His 70th Birthday
Guest editors: Alberto Dennunzio, Gheorghe Păun, Grzegorz Rozenberg and Claudio Zandron
Article type: Research Article
Authors: Castiglione, Giuseppa; * | Mantaci, Sabrina | Restivo, Antonio
Affiliations: Dipartimento di Matematica e Informatica, Universitá di Palermo, Via Archirafi 34, 90123 Palermo, Italy. giuseppa.castiglione@unipa.it, sabrina.mantaci@unipa.it, antonio.restivo@unipa.it
Correspondence: [*] Address for correspondence: Dipartimento di Matematica e Informatica, Universitá di Palermo, Via Archirafi 34, 90123 Palermo, Italy
Abstract: In this paper we investigate similarity measures based on minimal absent words, introduced by Chairungsee and Crochemore in [1]. They make use of a length-weighted index on a sample set corresponding to the symmetric difference M(x)ΔM(y) of the minimal absent words M(x) and M(y) of two sequences x and y, respectively. We first propose a variant of this measure by choosing as a sample set a proper subset 𝒟(x, y) of M(x)ΔM(y), which appears to be more appropriate for distinguishing x and y. From the algebraic point of view, we prove that 𝒟(x, y) is the base of the ideal generated by M(x)ΔM(y). We then remark that such measures are able to recognize whether the sequences x and y share a common structure, but they are not able to detect the difference on the number of occurrences of such a structure in the two sequences. In order to take into account such a multiplicity, we introduce the notion of multifactor, and define a new measure that uses both absent words and multifactors. Surprisingly, we prove that this similarity measure coincides with a distance on sequences introduced by Ehrenfeucht and Haussler in [2], in the context of block-moves strategies. In this way, our result creates a non trivial bridge between similarity measures based on absent words and those based on the block-moves approach.
Keywords: Minimal absent words, similarity measures, sequence comparison
DOI: 10.3233/FI-2020-1874
Journal: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 97-112, 2020
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl