Applications of the complexity space to the General Probabilistic Divide and Conquer Algorithms |
| |
Authors: | LM García-Raffi S Romaguera MP Schellekens |
| |
Institution: | a Instituto Universitario de Matemática Pura y Aplicada, Universidad Politécnica de Valencia, 46071 Valencia, Spain b Centre of Efficiency-Oriented Languages, Department of Computer Science, National University of Ireland, Western Road, Cork, Ireland |
| |
Abstract: | Schellekens M. Schellekens, The Smyth completion: A common foundation for denotational semantics and complexity analysis, in: Proc. MFPS 11, in: Electron. Notes Theor. Comput. Sci., vol. 1, 1995, pp. 535-556], and Romaguera and Schellekens S. Romaguera, M. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311-322] introduced a topological foundation to obtain complexity results through the application of Semantic techniques to Divide and Conquer Algorithms. This involved the fact that the complexity (quasi-metric) space is Smyth complete and the use of a version of the Banach fixed point theorem and improver functionals. To further bridge the gap between Semantics and Complexity, we show here that these techniques of analysis, based on the theory of complexity spaces, extend to General Probabilistic Divide and Conquer schema discussed by Flajolet P. Flajolet, Analytic analysis of algorithms, in: W. Kuich (Ed.), 19th Internat. Colloq. ICALP'92, Vienna, July 1992; Automata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 623, 1992, pp. 186-210]. In particular, we obtain a general method which is useful to show that for several recurrence equations based on the recursive structure of General Probabilistic Divide and Conquer Algorithms, the associated functionals have a unique fixed point which is the solution for the corresponding recurrence equation. |
| |
Keywords: | Complexity quasi-metric space Smyth complete Fixed point Improver Recurrence Probabilistic Divide and Conquer Algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|