Advanced search
Publication Cover
International Journal of Computer Mathematics Volume 89, 2012 - Issue 13-14: COMPUTATIONAL AND MATHEMATICAL METHODS IN SCIENCE AND ENGINEERING
Submit an article Journal homepage
149
Views
19
CrossRef citations to date
0
Altmetric
Section A

New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces

S. Romaguera Instituto Universitario de Matemática Pura y Aplicada, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain
,
P. Tirado Instituto Universitario de Matemática Pura y Aplicada, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain
&
O. Valero Departamento de Ciencias Matemáticas e Informática, Universidad de las Islas Baleares, Carretera de Valldemossa Km. 7.5, 07122, Palma de Mallorca, SpainCorrespondence[email protected]
Pages 1728-1741 | Received 03 Jul 2011, Accepted 17 Jan 2012, Published online: 23 Feb 2012

References

  • Brassard , G. and Bratley , P. 1988 . Algorithms: Theory and Practice , Englewood Cliffs , NJ : Prentice-Hall .
  • Cerdà-Uguet , M. A. , Schellekens , M. P. and Valero , O. 2012 . The Baire partial quasi-metric space: A mathematical tool for the asymptotic complexity analysis in Computer Science . Theory Comput. Syst. , 50 : 387 – 399 .
  • Cull , P. , Flahive , M. and Robson , R. 2005 . Difference Equations: From Rabbits to Chaos , New York : Springer .
  • Ecklund , E. F. Jr and Cull , P. 1985 . Towers of Hanoi and analysis of Algorithms . Amer. Math. Monthly , 92 : 407 – 420 .
  • García-Raffi , L. M. , Romaguera , S. and Sánchez-Pérez , E. A. 2002 . Sequence spaces and asymmetric norms in the theory of computational complexity . Math. Comput. Model. , 36 : 1 – 11 .
  • García-Raffi , L. M. , Romaguera , S. and Schellekens , M. P. 2008 . Applications of the complexity space to the general probabilistic divide and conquer algorithms . J. Math. Anal. Appl. , 348 : 346 – 355 .
  • Künzi , H. P.A. 2001 . “ Nonsymmetric distances and their associated topologies: About the origins of basic ideas in the area of asymmetric topology ” . In Handbook of the History of General Topology , Edited by: Aull , C. E. and Lowen , R. Vol. 3 , 853 – 968 . Dordrecht : Kluwer .
  • Rodríguez-López , J. , Romaguera , S. and Valero , O. 2008 . Denotational semantics for programming languages, balanced quasi-metrics and fixed points . Int. J. Comput. Math. , 85 : 623 – 630 .
  • Rodríguez-López , J. , Schellekens , M. P. and Valero , O. 2009 . An extension of the dual complexity space and an application to computer science . Topology Appl. , 156 : 3052 – 3061 .
  • Romaguera , S. and Schellekens , M. P. 1999 . Quasi-metric properties of complexity spaces . Topology Appl. , 98 : 311 – 322 .
  • Romaguera , S. and Valero , O. 2008 . On the structure of the space of complexity partial functions . Int. J. Comput. Math. , 85 : 631 – 640 .
  • Romaguera , S. , Sánchez-Pérez , E. A. and Valero , O. 2003 . Computing complexity distances between algorithms . Kybernetika , 39 : 569 – 582 .
  • Romaguera , S. , Schellekens , M. P. and Valero , O. 2011 . The complexity space of partial functions: A connection between complexity analysis and denotational semantics . Int. J. Comput. Math. , 88 : 1819 – 1829 .
  • Schellekens , M. P. 1995 . The Smyth completion: A common foundation for denotational semantics and complexity analysis . Electron. Notes Theor. Comput. Sci. , 1 : 211 – 232 .
  • Scott , D. S. 1970 . Outline of a mathematical theory of computation . Proceedings of the 4th Annual Princeton Conference on Information Sciences and Systems . March 26–27 1970 , Princeton , NJ . pp. 169 – 176 .
  • Scott , D. S. 1982 . “ Domains for Denotational Semantics ” . In Lecture Notes in Computer Science , Vol. 140 , 577 – 613 . Berlin : Springer .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.