The notion of speedup has been extensibly used in performance analysis of parallel program executions by multi-processor systems. In this paper, based on this notion, a definition of parallel degree is proposed to theoretically evaluate the parallelism of data-flow program nets, and its computation method is given. Further the fitness of the definition for the parallelism is discussed, and finally an application is suggested to estimate the number of processors required to run a given program net with a reasonable speedup.

A timed Petri net, an extended model of an ordinary Petri net with introduction of discrete time delay in firing activity, is practically useful in performance evaluation of real-time systems and so on. Unfortunately though, it is often too difficult to solve (efficiently) even most basic problems in timed Petri net theory. This motivates us to do research on analyzing complexity of Petri net problems and on designing efficient and/or heuristic algorithms. The minimum initial marking problem of timed Petri nets (TPMIM) is defined as follows: “Given a timed Petri net, a firing count vector X and a nonnegative integer π, find a minimum initial marking (an initial marking with the minimum total token number) among those initial ones M each of which satisfies that there is a firing scheduling which is legal on M with respect to X and whose completion time is no more than π, and, if any, find such a firing scheduling.” In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as TPMIM. The subject of the paper is to propose two pseudo-polynomial time algorithms TPM and TMDLO for TPMIM, and to evaluate them by means of computer experiment. Each of the two algorithms finds an initial marking and a firing sequence by means of algorithms for MIM (the initial marking problem for non-timed Petri nets), and then converts it to a firing scheduling of a given timed Petri net. It is shown through our computer experiments that TPM has highest capability among our implemented algorithms including TPM and TMDLO.

The subject of the paper is to analyze time complexity of the minimum modification problem in the Horn clause propositional logic. Given a set H of Horn clauses and a query Q in propositional logic, we say that Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens among clauses of H. Suppose that Q is not provable over H, and we are going to modify H and Q into H and Q , respectively, such that Q is provable over H . The problem of making such modification by minimum variable deletion (MVD), by minimum clause addition (MCA) or by their combination (MVDCA) is considered. Each problem is shown to be NP-complete, and some approximation algorithms with their experimental evaluation are given.

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

Petri nets with inhibitor arcs are referred to as inhibitor-arc Petri nets. It is shown that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines. The subject of this paper is the legal firing sequence problem (INLFS) for inhibitor-arc Petri nets: given an inhibitor-arc Petri net IN, an initial marking M0 and a firing count vector X, find a firing sequence δ such that its firing starts from M0 and each transition t appears in δ exactly X(t) times as prescribed by X. The paper is the first step of research for time complexity analysis and designing algorithms of INLFS, one of the most fundamental problems for inhibitor-arc Petri nets having more modeling capability than ordinary Peri nets. The recognition version of INLFS, denoted as RINLFS, means a decision problem, asking a "yes" or "no" answer on the existence of a solution δ to INLFS. The main results are the following (1) and (2). (1) Proving (1-1) and (1-2) when the underlying Petri net of IN is an unweighted state machine: (1-1) INLFS can be solved in pseudo-polynomial (O(|X|)) time for IN of non-adjacent type having only one special place called a rivet; (1-2) RINLFS is NP-hard for IN with at least three rivets; (2) Proving that RINLFS for IN whose underlying Petri net is unweighted and forward conflict-free is NP-hard. Heuristic algorithms for solving INLFS are going to be proposed in separate papers.

This paper deals with the firing activities of a data-flow program net, which is extended from conventional data-flow graph by allowing edge thresholds α and β to be any positive integer number, while a conventional data-flow graph has αβ1. For a switchless program net, a necessary and sufficient condition of structural termination is shown and an algorithm for verifying structural termination is provided. For a program net with switches that change their states only once during whole program execution, a sufficient condition for the uniqueness of maximum firing numbers is given.

If π is a monotone property on graphs (that is, π is attainable by adding edges to a given graph), then the graph augmentation problem with respect to π is defined by: "Given a graph G=(V, E) and nonnegative weights w(u, v) for all pairs {u, v} VV (uv), find an edge set Eof minimum total weight such that the graph G=(V, EE) satisfies π, where we assume that w(u, v)=0 for every edge (u, v) E". The subject of the paper is to give an overview of the graph augmentation problems where π is concerned with vertex-or edge-connectivity of graphs. Also presented are basic ideas used in solving this problem.

The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z+{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.

A siphon-trap(ST) of a Petri net N = (P,T,E,α,β) is defined as a set S of places such that, for any transition t, there is an edge from t to a place of S if and only if there is an edge from a place of S to t. A P-invariant is a |P|-dimensional vector Y with YtA = for the place-transition incidence matrix A of N. The Fourier-Motzkin method is well-known for computing all such invariants. This method, however, has a critical deficiency such that, even if a given Perti net N has any invariant, it is likely that no invariants are output because of memory overflow in storing intermediary vectors as candidates for invariants. In this paper, we propose an algorithm STFM_N for computing minimal-support nonnegative integer invariants: it tries to decrease the number of such candidate vectors in order to overcome this deficiency, by restricting computation of invariants to siphon-traps. It is shown, through experimental results, that STFM_N has high possibility of finding, if any, more minimal-support nonnegative integer invariants than any existing algorithm.

The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.

The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect M , X and PN (a sequence of transitions, with the first transition firable on M , such that every transition t can fire prescribed number X(t) of times). The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.

The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆V with |S|3 and a function g:V→Z+∪{∞}, find a smallest set E' of edges such that (V,E ∪E') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each v ∈V by the addition of E' to G is at most g(v), where Z+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.

A left identity type automation is defined as a finite automation whose transformation semigroup has a left identity. In this paper, we give a necessary and sufficient condition for a given automaton to be of left identity type in terms of the generators of its transformation semigroup.

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.

The subject of the paper is to propose a simple O(|V|+|E|) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V, E). An 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in the edge set KE(T).

The paper discusses computational complexity and approximation algorithms for the minimum initial marking problem MIM of a Petri net PN: Given PN and firing vector X, find a minimum initial marking M such that there is a firing sequence δ which is legal on M with respect to X". It is shown that MIM is NP-complete even if PN is a weakly connected marked graph with the unity edge weight and each transition having the in-degree and outdegree, at least 1 but at most 3. An O(|T|) algorithm for finding aminimum initial marking M, a solution to MIM for a state machine with the unity edge weight, and an O(|X|2) algorithm for finding a firing sequence that is legal on M with respect to X are given, where |T|, |P|and |X| denote the number of transitions, that of places, and the total sum of components of X, respectively. Some approximation algorithms for MIM are proposed, and their experimental results are presented.

Computational complexity aspect of the legal firing sequence problem (LFS) and some related problems of a Petri net PN is discussed. LFS is defined by Given a Petri net PN, a firing vector X and an initial marking M, determine whether or not there is a firing sequence δ which is legal on M with respect to X?" The related problems to be discussed in this paper are (a) the generalized submarking reachability problem (GSMR), (b) the submarking reachability problem (SMR) (c) the marking reachability problem (MR) (d) the generalized submarking reachability problem on a minimum initial submarking (MIS), (e) the lower and upper bounded submarking problem (LUS), (f) the optimum firing sequence problem (OFS) and (g) the minimum initial marking problem (MIM). Their NP-completeness and polynomial-time solvability are presented. They have applications to practical problems. For example, proofs of Horn-clause propositional logic and sequence control in factory automation are formulated as MIS and OFS, respectively.

Periodic schedules are seldom treated in the theory but abound in practice (air flight schedule, train schedule, manufacturing schedule, etc). This paper introduces a Petri Net based perspective to periodic schedules. These are classified, according to the time interpretation into single-server and multiple-server semantics and, according to transitions firing periodicity constraints, into strict and general periodic schedules. Using a net transformation rule, the computation of the general schedule class can be done through techniques for the strict subclass. Introducing truncation error terms ε for the floor functions, a necessary and sufficient condition for the feasibility of a strict periodic schedule is given in terms of a large size system of nonlinear inequalities containing ε terms. Moreover averaging this condition on subperiods allows to get a small size linear system of inequalities as necessary conditions for speeding up iterative computation processes. This paper aims to present qualitative analysis of periodic schedules for deterministically timed Petri net systems, as a precursor to quantitative analysis that requires large-scale computational experiments and hence will be dealt in later work.