• Computing complexity distances...

Treffer: Computing complexity distances between algorithms

Title:
Computing complexity distances between algorithms
Authors:
ROMAGUERA, S, SANCHEZ-PEREZ, E. A, VALERO, O
Source:
[Use of mathematical methods in computer science and the information society]Kybernetika. 39(5):569-582
Publisher Information:
Praha: Academia, 2003.
Publication Year:
2003
Physical Description:
print, 23 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Automatique théorique. Systèmes, Control theory. Systems, Généralités, General, Analyse algorithme, Algorithm analysis, Análisis algoritmo, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Complexité calcul, Computational complexity, Complejidad computación, Complexité espace, Space complexity, Complejidad espacio, Mesure distance, Distance measurement, Mot infini, Infinite word, Palabra infinita, Méthode diviser pour régner, Divide and conquer method, Método dividir para vencer, Métrique, Metric, Métrico, Point fixe, Fix point, Punto fijo, Théorème point fixe, Fixed point theorem, Teorema punto fijo, Topologie, Topology, Topología
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Escuela de Caminos, Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, 46071 Valencia, Spain
ISSN:
0023-5954
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15674715
Rights:
Copyright 2004 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:
Computer science; theoretical automation; systems
Accession Number:
edscal.15674715
Database:
PASCAL Archive

Weitere Informationen

We introduce a new (extended) quasi-metric on the so-called dual p-complexity space, which is suitable to give a quantitative measure of the improvement in complexity obtained when a complexity function is replaced by a more efficient complexity function on all inputs, and show that this distance function has the advantage of possessing rich topological and quasi-metric properties. In particular, its induced topology is Hausdorff and completely regular. Our approach is applied to the measurement of distances between infinite words over the decimal alphabet and some advantages of our computations with respect to the ones that provide the classical Baire metric are discussed. Finally, we show that the application of fixed point methods to the complexity analysis of Divide & Conquer algorithms, presented by M. Schellekens (Electronic Notes in Theoret. Comput. Sci. 1 (1995)), can be also given from our approach.