The problem of measuring the structural complexity of logic networks is examined. A complexity measure p(N) is proposed which is the total number of input-output paths in an acyclic network N. p(N) is easily computed ...
详细信息
The problem of measuring the structural complexity of logic networks is examined. A complexity measure p(N) is proposed which is the total number of input-output paths in an acyclic network N. p(N) is easily computed by representing network structure in matrix form. It is shown that simple upper bounds on the number of tests required by a combinational network N can be derived from p(N). These bounds are fairly tight when N contains little or no fan-out. The path complexity of combinational functions is defined and briefly discussed.
This paper presents METRINOME, a tool for performing automatic path complexity analysis of C functions. The path complexity of a function is an expression that describes the number of paths through the function up to ...
详细信息
ISBN:
(纸本)9781665412193
This paper presents METRINOME, a tool for performing automatic path complexity analysis of C functions. The path complexity of a function is an expression that describes the number of paths through the function up to a given execution depth. METRINOME constructs the control flow graph (CFG) of a C function using LLVM utilities, analyzes that CFG using algebraic graph theory and analytic combinatorics, and produces a closed-form expression for the path complexity as well as the asymptotic path complexity of the function. Our experiments show that path complexity predicts the growth rate of the number of execution paths that KLEE, a popular symbolic execution tool, is able to cover within a given exploration depth. Metrinome is open-source, available as a Docker image for immediate use, and all of our experiments and data are available in our repository and included in our Docker image.
Recent automated software testing techniques concentrate on achieving path coverage. We present a complexity measure that provides an upper bound for the number of paths in a program, and hence, can be used for assess...
详细信息
ISBN:
(纸本)9781450336758
Recent automated software testing techniques concentrate on achieving path coverage. We present a complexity measure that provides an upper bound for the number of paths in a program, and hence, can be used for assessing the difficulty of achieving path coverage for a given method. We define the path complexity of a program as a function that takes a depth bound as input and returns the number of paths in the control flow graph that are within that bound. We show how to automatically compute the path complexity function in closed form, and the asymptotic path complexity which identifies the dominant term in the path complexity function. Our results demonstrate that path complexity can be computed efficiently, and it is a better complexity measure for path coverage compared to cyclomatic complexity and Npath complexity.
A new methodology of measuring software complexity is proposed based on program decomposition mechanisms. The purpose of our research is to improve the quality and reliability of software by using a good measurement o...
详细信息
A new methodology of measuring software complexity is proposed based on program decomposition mechanisms. The purpose of our research is to improve the quality and reliability of software by using a good measurement of the complexity of the software. Thus software development cost can be reduced due to the fewer errors introduced. We present a complete survey of Various metrics in the literature. Six types of metrics or measurement techniques are discussed, including some earlier research results of the authors. We then propose a program decomposition mechanism based on the operational semantics of several languages constructs in most procedural languages. An algorithm along with some examples is also given to show the feasibility of our mechanism. Our approach, relies on the path complexity of a program, is more accurate and easier to be realized. The algorithm also points out that how many individual complete paths of a program need to be tested.
path selection is one of the fundamental problems in emergency logistics management. Two mathematical models for path selection in emergency logistics management are presented considering more actual factors in time o...
详细信息
path selection is one of the fundamental problems in emergency logistics management. Two mathematical models for path selection in emergency logistics management are presented considering more actual factors in time of disaster. First a single-objective path selection model is presented taking into account that the travel speed on each arc will be affected by disaster extension. The objective of the model is to minimize total travel time along a path. The travel speed on each arc is modeled as a continuous decrease function with respect to time. A modified Dijkstra algorithm is designed to solve the model. Based oil the first model, we further consider the chaos, panic and congestions in time of disaster. A multi-objective path selection model is presented to minimize the total travel time along a path and to minimize the path complexity. The complexity of the path is modeled as the total number of arcs included in the path. An ant colony optimization algorithm is proposed to solve the model. Simulation results show the effectiveness and feasibility of the models and algorithms presented in this paper. (C) 2008 Elsevier Ltd. All rights reserved.
Variant design is an effective mean to derive individual product rapidly. This paper focuses on the parameter transferring issue of assembly variant design, that is, to identify a parameter transferring path with mini...
详细信息
ISBN:
(纸本)9781424448692
Variant design is an effective mean to derive individual product rapidly. This paper focuses on the parameter transferring issue of assembly variant design, that is, to identify a parameter transferring path with minimum uncertainty. Parameter constraint network and uncertainty characteristic were presented. A measure of undefined parameter information was employed to describe the complexity of identifying a parameter value during variant design. Based on this, a modified path complexity of parameter transferring was formulated. By calculating path complexity of each potential transferring process, the parameter transferring path with minimum path complexity can be found. This analysis is convenient to make full use of customized information to design individual product so as to increase the rationality and efficiency of parameter valued. We illustrate our approach with examples.
作者：
Grasso, N.Verbree, E.Zlatanova, S.Piras, M.Politecnico di Torino
DIATI-Department of Environmental Land and Infrastructure Engineering C.so Duca degli Abruzzi 24 Torino10129 Italy Delft University of Technology
Faculty of Architecture and the Built Environment OTB-Research Institute for the Built Environment GIS Technology Julianalaan 134 BL Delft2628 Netherlands Delft University of Technology
Faculty of Architecture and the Built Environment Department of Urbanism 3D Geoinformation Julianalaan 134 BL Delft2628 Netherlands
Many research works have been oriented to the formulation of different algorithms for estimating the paths in indoor environments from three-dimensional representations of space. The architectural configuration, the a...
详细信息
暂无评论