Result: Implementing approximate regularities
Title:
Implementing approximate regularities
Authors:
Source:
International conference of computational methods in sciences and engineering 2003 (ICCMSE 2003)Mathematical and computer modelling. 42(7-8):855-866
Publisher Information:
Oxford: Elsevier Science, 2005.
Publication Year:
2005
Physical Description:
print, 7 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Méthodes de calcul scientifique (y compris calcul symbolique, calcul algébrique), Methods of scientific computing (including symbolic computation, algebraic computation), Algorithme, Algorithm, Algoritmo, Approximation numérique, Numerical approximation, Aproximación numérica, Calcul scientifique, Scientific computation, Computación científica, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Complexité temps, Time complexity, Complejidad tiempo, Distance Hamming, Hamming distance, Distancia Hamming, Implémentation, Implementation, Implementación, Mathématiques appliquées, Applied mathematics, Matemáticas aplicadas, Modèle mathématique, Mathematical model, Modelo matemático, Polynôme, Polynomial, Polinomio, Résultat expérimental, Experimental result, Resultado experimental, Similitude, Similarity, Similitud, Temps polynomial, Polynomial time, Tiempo polinomial, Edit distance, Période approchée, Approximate period, Recouvrement approché, Approximate cover, Régularité approchée, Approximate regularity, Approximate regularities, Approximate seed, Restricted smallest distance approximation, Smallest distance approximation, Weighted edit distance
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, King's College, London, United Kingdom
School of Computer Science and Engineering, Seoul National University, Korea, Republic of
School of Computer Science and Engineering, Inha University, Korea, Republic of
School of Computer Science and Engineering, Seoul National University, Korea, Republic of
School of Computer Science and Engineering, Inha University, Korea, Republic of
ISSN:
0895-7177
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.17286656
Database:
PASCAL Archive
Further Information
In this paper, we study approximate regularities of strings, that is, approximate periods, approximate covers, and approximate seeds. We explore their similarities and differences and we implement algorithms for solving the smallest distance approximate period/cover/seed problem and the restricted smallest approximate period/cover/seed/ problem in polynomial time, under a variety of distance rules (the Hamming distance, the edit distance, and the weighted edit distance). Then, we analyse our experimental results to find out the time complexity of the algorithms in practice.