Fixed point theorems in generalized metric spaces with applications to computer science

Fixexd point theory and applications

Oscar Valero¹  Naseer Shahzad²  Maryam A Alghamdi³ 

[1] Departamento de Ciencias MatemáDepartment of Mathematics, King Abdulaziz University, Jeddah, Saudi Arabia;Department of Mathematics, Sciences Faculty for Girls, King Abdulaziz University, Jeddah, Saudi Arabia;tica, Universidad de las Islas Baleares, Palma de Mallorca, Spain;ticas e Informá

关键词: partial metric;    fixed point;    asymptotic complexity analysis;    recurrence equation;    running time of computing;   

DOI  :  10.1186/1687-1812-2013-118

学科分类：数学（综合）

来源: SpringerOpen

【 摘 要 】

In 1994, Matthews introduced the notion of a partial metric space in order to obtain a suitable mathematical tool for program verification (Matthews in Ann. N.Y. Acad. Sci. 728:183-197, 1994). He gave an application of this new structure to formulate a suitable test for lazy data flow deadlock in Kahn’s model of parallel computation by means of a partial metric version of the celebrated Banach fixed point theorem (Matthews in Theor. Comput. Sci. 151:195-205, 1995). In this paper, motivated by the utility of partial metrics in computer science, we discuss whether they are a suitable tool for asymptotic complexity analysis of algorithms. Concretely, we show that the Matthews fixed point theorem does not constitute, in principle, an appropriate implement for the aforementioned purpose. Inspired by the preceding fact, we prove two fixed point theorems which provide the mathematical basis for a new technique to carry out asymptotic complexity analysis of algorithms via partial metrics. Furthermore, in order to illustrate and to validate the developed theory, we apply our results to analyze the asymptotic complexity of two celebrated recursive algorithms. MSC:47H10, 54E50, 54F05, 68Q25, 68W40.

【 授权许可】

CC BY