A Tentative Research on Complexity of Automatic Programming

In this paper, based on the following theoretical framework: Evolutionary Algorithms + Program Structures = Automatic Programming , some results on complexity of automatic programming for function modeling is given, which show that the complexity of automatic programming is an exponential function of the problem dimension N , the size of operator set ｜F｜ and the height of the program parse tree H . Following this results, the difficulties of automatic programming are discussed. Some function models discovered automatically from database by evolutionary modeling method are given, too.

PROGRAM COMPLEX(GRAD)FOR COMPUTER AIDED DESIGN,DEVELOPMENT AND SERVICE OPERATION OF GAS TURBINE ENGINES

This paper considers problems of the mathematical simulation of gas turbine engines and power plants.A program complex is presented which is capable of automatizing solutions of many problems concerning the theromo-gas-dynamic calculation of the engine flow passage at the stages of design,development and service.A universal mathematical model is provided which real- izes all calculation for engines of different structure schemes (including test-bench) under different regimes.This program complex includes modules WHICGBH.It can solve problems of optimiza- tion,identification and diagnostics.Software is realized on the computer ES and PC(IBM PC). Kazan Aviation Institute K.Marx Str.10 Kazan 420111 Elousi,USSR

On the Complexities of Non-Horn Clause Logic Programming

There have been active work to extend the Prolog style Horn Clause logic programming to non-Horn clauses.In this paper,we will analyze the complexities of several such extensions.The purpose is to understand the computational complexity of these inference systems.The analyses do not prove that any one system is better than the others all the time.But they do suggest that one system may be better than the others for some particular problems.We also discuss the effect of caching.

Complexity Measure Based on ProgramSlicing and Its Validation

The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, in this paper, we propose a complexity measure based on program slicing（CMBPS）. CMPBS not only can evaluate factors which affect program complexity such as the length of the program, control flow, data flow and data types of output variables, but also can give expression of the interactive relation between programs. And we also prove that CMBPS satisfies all of Weyuker properties. Compared with the popular complexity measures, CMBPS is a well-structured complexity measure.

Robust Solutions of Uncertain Complex-valued Quadratically Constrained Programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.

Measuring Class Cohesion Based on Dependence Analysis

Classes are the basic modules in object-oriented (OO) software, which consist of attributes and methods. Thus, in OO environment, the cohesion is mainly about the tightness of the attributes and methods of classes. This paper discusses the relationships between attributes and attributes, attributes and methods, methods and methods of a class based on dependence analysis. Then the paper presents methods to compute these dependencies. Based on these, the paper proposes a method to measure the class cohesion, which satisfies the properties that a good measurement should have. The approach overcomes the limitations of previous class cohesion measures, which consider only one or two of the three relationships in a class. Keywords cohesion - object-orientation - class - program complexity - dependence analysis Supported by the National Natural Science Foundation of China under Grant No.60073012; the National Basic Research 973 Program of China under Grant No.2002CB312000; the Program for Cross-Century Outstanding Teachers of the Ministry of Education; the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.20020286004; the Natural Science Foundation of Jiangsu, China, under Grant No.BK2001004; the Jiangsu Key Science and Technology Project under Grant No.BE2001025; the Opening Foundation of State Key Laboratory of Software Engineering in Wuhan University; the Opening Foundation of Jiangsu Key Laboratory of Computer Information Processing Technology in Soochow University.Zheng-Qiang Chen was born in 1976. He received the M.S. and Ph.D. degrees in computer science in 2000 and 2003, respectively. His current research interests include program analysis, understanding and testing as well as other topics related to reverse engineering. He has published more than 30 technical papers.Bao-Wen Xu was born in 1961. He received the M.S. and Ph.D. degrees in computer science in 1984 and 2002, respectively. He is a professor in the Computer Science & Engineering Department of Southeast University, Nanjing, China. His current research interests include programming language, program analysis, understanding, metrics and testing, Web search engine, and other topics related to reverse engineering. He has published more than 200 technical papers and 10 books. He is General Chairs of IEEE FTDCS'2004 and ICYCS'99, PC Chairs of WISA'2004 and WEBSA'2003, PC Members of IEEE COMPSAC'2003,'2002 and '2001, IEEE ICTAI'2003 and IEEE IRI'2003, and Session Chairs of IEEE ICTAI'2003 and COMPSAC'2002.Yu-Ming Zhou was born in 1974. He received the M.S. and Ph.D. degrees in computer science in 1999 and 2003, respectively. His current research interests include program analysis and metrics. He has published more than 20 technical papers.

Parameter Ecology for Feedback Vertex Set

This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.