अपवादों की उपस्थिति में जावा के पॉइंट-टू विश्लेषण की जटिलता

प्रत्येक प्रोग्राम पॉइंट पर, स्थैतिक प्रकार के वस्तु-उमुख प्रोग्रामिंग भाषाओं (जैसे, जावा, सी++) के लिए पॉइंट-टू विश्लेषण उन ऑब्जेक्ट्स को निर्धारित करता है जिनके लिए एक संदर्भ का संदर्भित होना (या एक पॉइंटर का इशारा करना) निष्पादन के दौरान संभव है। ऑब्जेक्ट-उमुख प्रणालियों के लिए किसी भी अर्थ द्वारा आधारित सॉफ़्टवेयर उपकरण के लिए पॉइंट-टू विश्लेषण आवश्यक है। हमारे नए जटिलता परिणाम पॉइंट-टू विश्लेषण के अंदर-प्रक्रियात्मक और बीच-प्रक्रियात्मक विश्लेषण की कठिनाई को निर्धारित करते हैं जो एकल-स्तरीय प्रकारों (यानी, केवल प्राइमेटिव प्रकार के डेटा सदस्यों वाले प्रकार), उप-प्रकार के साथ या बिना अपवादों और गतिशील डिस्पैच के संयोजनों वाले भाषाओं के लिए हैं। हमारे परिणामों में शामिल हैं: 1) अपवादों की उपस्थिति में पॉइंट-टू विश्लेषण के लिए पहला बहुपद-समय एल्गोरिदम जो बिना थ्रेड्स के जावा के एक मजबुत उपसमुच्चय को संभालता है और को C++ पर लागू किया जा सकता है; 2) प्रमाण कि उपरोक्त एल्गोरिदम सामान्यतः सुरक्षित है और प्राइमेटिव प्रकार और उप-प्रकार के बिना अपवादों वाले कार्यक्रमों में सिद्ध रूप से सटीक है, लेकिन गतिशील डिस्पैच नहीं, इस प्रकार, यह मामला P में है; 3) प्रमाण कि एक बीच-प्रक्रियात्मक पॉइंट-टू विश्लेषण समस्या जो एकल-स्तरीय प्रकार और उप-प्रकार के साथ अपवादों के साथ, लेकिन गतिशील डिस्पैच के बिना है, PSPACE-हार्ड है, जबकि अंदर-प्रक्रियात्मक समस्या PSPACE-संपूर्ण है। बिना अपवादों वाले कार्यक्रमों में पॉइंट-टू विश्लेषण के अन्य जटिलता वर्णन प्रस्तुत किए गए हैं, जिनमें O(n/sup 5/) का सबसे खराब-केस बाउंड के साथ एक एल्गोरिदम शामिल है, जो पहले के दृष्टिकोणों T. Reps आदि (1995) और W.A. Landi और B.G. Ryder (1991) से O(n/sup 7/) के सबसे खराब-केस बाउंड को बेहतर बनाता है।