Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
![]() |
![]() ![]() |
Ultima descărcare din IBN: 2016-12-16 13:11 |
Căutarea după subiecte similare conform CZU |
512.54+519.7 (4) |
Algebra (413) |
Mathematical cybernetics (95) |
![]() CHOBAN, Mitrofan, BUDANAEV, Ivan. About Applications of Distances on Monoids of Strings. In: Computer Science Journal of Moldova, 2016, nr. 3(72), pp. 335-356. ISSN 1561-4042. |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Computer Science Journal of Moldova | |||||||
Numărul 3(72) / 2016 / ISSN 1561-4042 /ISSNe 2587-4330 | |||||||
|
|||||||
CZU: 512.54+519.7 | |||||||
Pag. 335-356 | |||||||
|
|||||||
![]() |
|||||||
Rezumat | |||||||
In this article we show that there are invariant distances on the monoid L(A) of all strings closely related to Levenshtein’s distance. We will use a distinct definition of the distance on L(A), based on the Markov - Graev method, proposed by him for free groups. As result we will show that for any quasimetric d on alphabet A in union with the empty string there exists a maximal invariant extension d_ on the free monoid L(A). This new approach allows the introduction of parallel and semiparallel decompositions of two strings. In virtue of Theorem 3.1, they offer various applications of distances on monoids of strings in solving problems from distinct scientific fields. The discussion covers topics in fuzzy strings, string pattern search, DNA sequence matching etc. |
|||||||
Cuvinte-cheie String pattern matching, parallel decomposition, semiparallel decomposition, Levenshtein distance, proper similarity, free monoid, invariant distance, quasimetric, Hamming distance |
|||||||
|
DataCite XML Export
<?xml version='1.0' encoding='utf-8'?> <resource xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xmlns='http://datacite.org/schema/kernel-3' xsi:schemaLocation='http://datacite.org/schema/kernel-3 http://schema.datacite.org/meta/kernel-3/metadata.xsd'> <creators> <creator> <creatorName>Cioban, M.M.</creatorName> <affiliation>Universitatea de Stat din Tiraspol, Moldova, Republica</affiliation> </creator> <creator> <creatorName>Budanaev, I.A.</creatorName> <affiliation>Institutul de Matematică şi Informatică al AŞM, Moldova, Republica</affiliation> </creator> </creators> <titles> <title xml:lang='en'>About Applications of Distances on Monoids of Strings</title> </titles> <publisher>Instrumentul Bibliometric National</publisher> <publicationYear>2016</publicationYear> <relatedIdentifier relatedIdentifierType='ISSN' relationType='IsPartOf'>1561-4042</relatedIdentifier> <subjects> <subject>String pattern matching</subject> <subject>parallel decomposition</subject> <subject>semiparallel decomposition</subject> <subject>free monoid</subject> <subject>invariant distance</subject> <subject>quasimetric</subject> <subject>Levenshtein distance</subject> <subject>Hamming distance</subject> <subject>proper similarity</subject> <subject schemeURI='http://udcdata.info/' subjectScheme='UDC'>512.54+519.7</subject> </subjects> <dates> <date dateType='Issued'>2016-10-11</date> </dates> <resourceType resourceTypeGeneral='Text'>Journal article</resourceType> <descriptions> <description xml:lang='en' descriptionType='Abstract'>In this article we show that there are invariant distances on the monoid L(A) of all strings closely related to Levenshtein’s distance. We will use a distinct definition of the distance on L(A), based on the Markov - Graev method, proposed by him for free groups. As result we will show that for any quasimetric d on alphabet A in union with the empty string there exists a maximal invariant extension d_ on the free monoid L(A). This new approach allows the introduction of parallel and semiparallel decompositions of two strings. In virtue of Theorem 3.1, they offer various applications of distances on monoids of strings in solving problems from distinct scientific fields. The discussion covers topics in fuzzy strings, string pattern search, DNA sequence matching etc. </description> </descriptions> <formats> <format>application/pdf</format> </formats> </resource>