Software testing is an important problem to design a large software system and it is difficult to be solved due to its computational complexity. We try to use program nets to approach this problem. As the first step towards solving software testing problem, this paper provides a technique to generate subnets of a program net and applies this technique to software testing. Firstly, definitions and properties of program nets are introduced based on our previous works, and the explanation of software testing problem is given. Secondly, polynomial algorithms are proposed to generate subnets that can cover all the given program net. Finally, a case study is presented to show how to find subnets covering a given program net by using the proposed algorithms, as well as to show the input test data of the program net for software testing.

This paper deals with computation of parallel degree, PARAdeg, for (dataflow) program nets with SWITCH-nodes. Ge et al. have given the definition of PARAdeg and an algorithm of computing PARAdeg for program nets with no SWITCH-nodes. However, for program nets with SWITCH-nodes, any algorithm of computing PARAdeg has not been proposed. We first show that it is intractable to compute PARAdeg for program nets with SWITCH-nodes. To do this, we define a subclass of program nets with SWITCH-nodes, named structured program nets, and then show that the decision problem related to compute PARAdeg for acyclic structured program nets is NP-complete. Next, we give a heuristic algorithm to compute PARAdeg for acyclic structured program nets. Finally, we do experiments to evaluate our heuristic algorithm for 200 acyclic structured program nets. We can say that the heuristic algorithm is reasonable, because its accuracy is more than 96% and the computation time can be greatly reduced.

In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.

This paper investigates the usefulness of a new priority list for two-processor scheduling problem of program nets. Firstly, we discuss the weakness of a previously proposed priority list and then introduce a new priority list. Through simulation experiment we show that the new priority list is better than the previous one and can generate the same length of schedules as GA scheduling, which implies the new priority list can generate approximately optimal schedules.

This paper provides a list-scheduling method for program nets executed with two processors. The program nets dealt with in this paper are acyclic and SWITCH-less, and the priority list proposed in this paper consists of both dynamic and static lists. First, we point out the weakness of a previously proposed priority list and propose a new priority list. Then we give properties of the new priority list and further prove this new priority list can generate optimal schedules for the program nets whose AND-nodes possess at most single input edge. Finally, we compare the new priority list with the previous one to show the new priority list can generate shorter schedules than the previous for the nets whose AND-nodes may have two input edges.

This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.

This paper aims at improving effectiveness of previously proposed hybrid priority lists, {L*i=LdLsi}, that are applied in nonpreemptive 2-processor scheduling of general acyclic SWITCH-less program nets, where Ld and Lsi are dynamic and static priority lists respectively. Firstly, we investigate the effectiveness of Ld through experiments. According to the experimental results, we reconstruct Ld to propose its improved list L1d. Then analyzing the construction methodology of the static priority lists {Lsi}, we propose a substituted list L2d by taking into account of the factor: remaining firing numbers of nodes. Finally, we combine a part of L1d and L2d to propose a new priority list L**. Through scheduling simulation on 400 program nets, we find the new priority list L** can generate shorter schedules, close to ones of GA (Genetic Algorithm) scheduling that has been shown exceedingly effective but costing much computation time.

PARAdeg has been defined to try to measure parallelism inherent in a program net. Studies on computation of PARAdeg have been done, but the quantitative evaluation, on how much PARAdeg fits parallelism of program nets, has not been studied. In this paper, we do the evaluation by applying genetic algorithm to measure firing completion times when PARAdeg processors, and less and more processors are provided for 400 program nets. Our experimental results show that the firing completion times decrease rapidly with increase of processors till PARAdeg and slowly when processors are increased to more than PARAdeg, which implies PARAdeg is a reasonable standard to measure parallelism of program nets.

This paper deals with two-processor scheduling for general acyclic SWITCH-less program nets with random node firing times. First, we introduce a hybrid priority list L* that has been shown to generate optimal schedules for the acyclic SWITCH-less program nets with unity node firing times, of which AND-nodes possess at most single input edge. Then considering the factors of existence of the AND-nodes with two input edges as well as random node firing times, we extend L* to design a new dynamic priority list Ld and four static priority lists {Lsii=1,2,3,4}; and then combining Ld and Lsi (i=1,2,3,4) we propose four hybrid priority lists {L*ii=1,2,3,4}. Finally, we apply genetic algorithm to evaluate the schedules generated by the four lists through simulations on 400 program nets. Our simulation results show two of the four lists can generate reasonably good schedules.

This paper deals with two-processor scheduling for a class of program nets, that are acyclic and SWITCH-less, and of which each node has unity node firing time. Firstly, we introduce a hybrid priority list L* that generates optimal schedules for the nets whose AND-nodes possess at most single input edge. Then we extend L* to suit for general program nets to give a new priority list L**. Finally, we use genetic algorithm to do the performance evaluation for the schedules generated by L** and show these schedules are quite close to optimal ones.

A data-flow program net is a graph representation of data-flow programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Minimum firing (completion) time T of a program net is an important element in computing parallel degree PARAdeg residing in a data-flow program and is defined as the minimum time when the program net is executed by enough many processors. In this paper, we propose algorithms to efficiently compute T by contracting AND-nodes generally for self-cleaning SWITCH-less program nets with arbitrary node firing time and give the experimental results of the algorithms to show the efficiency.

A data-flow program net is a graph representation of data-flow programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Token self-cleanness is an important property of a data-flow program and is such that if date-flow programs satisfy the property then a date-flow computer can efficiently withdraw copies from given programs during executions. In this paper, we classify program nets into SWITCH-less, OR-less and general nets, and analyse structures of data-flow program nets to propose verification methods of token self-cleanness by investigating token numbers appearing on the edges. As a result, a necessary and sufficient condition is proposed for SWITCH-less data-flow program nets and sufficient conditions are given for OR-less and general data-flow program nets.