The complexity space of partial functions: a connection between complexity analysis and denotational semantics

References

• de Bakker , J. W. and de Vink , E. P. 1996 . Control Flow Semantics , MA : The MIT Press .
   Google Scholar
• de Bakker , J. W. and de Vink , E. P. 1998 . Denotational models for programming languages: Applications of Banach's fixed point theorem . Topol. Appl. , 85 : 35 – 52 .
   Web of Science ®Google Scholar
• Davey , B. A. and Priestley , H. A. 1990 . Introduction to Lattices and Order , New York : Cambridge University Press .
   Google Scholar
• Emerson , A. C. and Jutla , C. S. 1999 . The complexity of tree automata and logic of programs . SIAM J. Comput. , 29 : 132 – 158 .
   Web of Science ®Google Scholar
• Flajolet , P. and Golin , M. J. 1994 . Mellin transforms and asymptotics: The mergesort recurrence . Acta Inform. , 31 : 673 – 696 .
   Web of Science ®Google Scholar
• Fletcher , P. and Lindgren , W. F. 1982 . Quasi-Uniform Spaces , New York : Marcel Dekker .
   Google Scholar
• Fuchssteiner , B. and Lusky , W. 1981 . Convex Cones , Amsterdam : North Holland .
   Google Scholar
• 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 .
   Web of Science ®Google Scholar
• García-Raffi , L. M. , Romaguera , S. and Sánchez-Pérez , E. A. 2003 . The supremum asymmetric norm on sequence algebras: A general framework to measure complexity distances . Electronic Notes Theoret. Comput. Sci. , 74 : 39 – 50 .
   Google Scholar
• García-Raffi , L. M. , Romaguera , S. , Sánchez-Pérez , E. A. and Valero , O. Normed Semialgebras: A Mathematical Model for the Complexity Analysis of Programs and Algorithms . Proceedings of The 7th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2003), Orlando, Florida, USA . Edited by: Callaos , N. , Di Sciullo , A. M. , Ohta , T. and Liu , T.-K. Vol. II , pp. 55 – 58 . Orlando, FL : International Institute of Informatics and Systemics .
   Google Scholar
• Gunter , C. A. and Scott , D. S. 1990 . “ Semantic domains ” . In Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics , Edited by: van Leeuwen , J. 633 – 674 . Cambridge : Elsevier Science Publishers .
   Google Scholar
• Hartog , J. I. , de Bakker , J. W. and De Vink , E. P. 2001 . Metric semantics and full abstractness for action refinement and probabilistic choice . Electronic Notes Theoret. Comput. Sci. , 40 : 72 – 99 .
   Google Scholar
• Kelley , J. L. 1955 . General Topology , New York : Springer-Verlag .
   Google Scholar
• 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 Academic Publishers .
   Google Scholar
• Medina , J. , Ojeda-Aciego , M. and Ruiz-Calviño , J. A fixed point theorem for multi-valued functions with an application to multilattice-based logic programming . Applications of Fuzzy Sets Theory: 7th International Workshop on Fuzzy Logic and Applications, WILF 2007, Camogli, Italy, July 7–10, 2007, Proceedings . Edited by: Masulli , F. , Mitra , S. and Pasi , G. Vol. 4578 , pp. 37 – 44 . Berlin : Springer-Verlag . Notes in Artificial Intelligence
   Google Scholar
• O'Keeffe , M. , Romaguera , S. and Schellekens , M. 2003 . Norm-weightable Riesz spaces and the dual complexity space . Electronic Notes Theoret. Comput. Sci. , 74 : 105 – 121 .
   Google Scholar
• Rodríguez-López , J. 2004 . A new approach to epiconvergence and some applications . Southeast Asian Bull. Math. , 28 : 685 – 701 .
   Google Scholar
• Rodríguez-López , J. , Romaguera , S. and Valero , O. 2006 . Asymptotic complexity of algorithms via the nonsymmetric Hausdorff distance . Comput. Lett. , 2 : 155 – 161 .
   Google Scholar
• 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 .
   Web of Science ®Google Scholar
• Romaguera , S. and Schellekens , M. 1999 . Quasi-metric properties of complexity spaces . Topol. Appl. , 98 : 311 – 322 .
   Web of Science ®Google Scholar
• Romaguera , S. and Schellekens , M. 2000 . The quasi-metric of complexity convergence . Quaestiones Math. , 23 : 359 – 374 .
   Google Scholar
• Romaguera , S. and Schellekens , M. 2002 . Duality and quasi-normability for complexity spaces . Appl. Gen. Topol. , 3 : 91 – 112 .
   Google Scholar
• Romaguera , S. and Valero , O. 2008 . On the structure of the space of complexity partial functions . Int. J. Comput. Math. , 85 : 631 – 640 .
   Web of Science ®Google Scholar
• Romaguera , S. , Sánchez-Pérez , E. A. and Valero , O. 2003 . The complexity space of a valued linearly ordered set . Electronic Notes Theoret. Comput. Sci. , 74 : 158 – 171 .
   Google Scholar
• Romaguera , S. , Sánchez-Pérez , E. A. and Valero , O. 2003 . Computing complexity distances between algorithms . Kybernetika , 39 : 569 – 582 .
   Web of Science ®Google Scholar
• Schellekens , M. 1995 . The Smyth completion: A common foundation for denotational semantics and complexity analysis . Electronic Notes Theoret. Comput. Sci. , 1 : 535 – 556 .
   Google Scholar
• Schellekens , M. 1995 . “ The smyth completion: A common topological foundation for denotational semantics and complexity analysis ” . Pittsburgh : Carnegie Mellon University . Ph.D. thesis
   Google Scholar
• Seda , A. K. and Hitzler , P. 2010 . Generalized distance functions in the theory of computation . Comput. J. , 53 ( 4 ) : 443 – 464 . doi:10.1093/comjnl/bxm108
   Web of Science ®Google Scholar
• Straccia , U. , Ojeda-Aciego , M. and Damásio , C. V. 2009 . On fixed-points of multi-valued functions on complete lattices and their application to generalized logic programs . SIAM J. Comput. , 38 : 1881 – 1911 .
   Web of Science ®Google Scholar
• Tennent , R. D. 1976 . The denotational semantics of programming languages . Comm. ACM , 19 : 437 – 453 .
   Web of Science ®Google Scholar
• Tix , R. , Keimel , K. and Plotkin , G. 2005 . Semantic domains for combining probability and non-determinism . Electronic Notes Theoret. Comput. Sci. , 129 : 1 – 104 .
   Google Scholar