A formal graph system (FGS for short) is a logic program consisting of definite clauses whose arguments are graph patterns instead of first-order terms. The definite clauses are referred to as graph rewriting rules. An FGS is shown to be a useful unifying framework for learning graph languages. In this paper, we show the polynomial-time PAC learnability of a subclass of FGS languages defined by parameterized hereditary FGSs with bounded degree, from the viewpoint of computational learning theory. That is, we consider VH-FGSLk,Δ(m, s, t, r, w, d) as the class of FGS languages consisting of graphs of treewidth at most k and of maximum degree at most Δ which is defined by variable-hereditary FGSs consisting of m graph rewriting rules having TGP patterns as arguments. The parameters s, t, and r denote the maximum numbers of variables, atoms in the body, and arguments of each predicate symbol of each graph rewriting rule in an FGS, respectively. The parameters w and d denote the maximum number of vertices of each hyperedge and the maximum degree of each vertex of TGP patterns in each graph rewriting rule in an FGS, respectively. VH-FGSLk,Δ(m, s, t, r, w, d) has infinitely many languages even if all the parameters are bounded by constants. Then we prove that the class VH-FGSLk,Δ(m, s, t, r, w, d) is polynomial-time PAC learnable if all m, s, t, r, w, d, Δ are constants except for k.

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ESUM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.

In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.

Many actual systems, e.g. computer programs, can be modeled as a subclass of Petri nets, called bridge-less workflow nets. For bridge-less workflow nets, we revealed the following properties: (i) any acyclic bridge-less workflow net is free choice; (ii) an acyclic bridge-less workflow net is sound iff it is well-structured; and (iii) any sound bridge-less workflow net is well-structured. We also proposed a necessary and sufficient condition to decide whether a given workflow net is bridge-less, and then constructed a polynomial-time procedure for it.

A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.

The linear Piece In Hand (PH, for short) matrix method with random variables was proposed in our former work. It is a general prescription which can be applicable to any type of multivariate public-key cryptosystems for the purpose of enhancing their security. Actually, we showed, in an experimental manner, that the linear PH matrix method with random variables can certainly enhance the security of HFE against the Grobner basis attack, where HFE is one of the major variants of multivariate public-key cryptosystems. In 1998 Patarin, Goubin, and Courtois introduced the plus method as a general prescription which aims to enhance the security of any given MPKC, just like the linear PH matrix method with random variables. In this paper we prove the equivalence between the plus method and the primitive linear PH matrix method, which is introduced by our previous work to explain the notion of the PH matrix method in general in an illustrative manner and not for a practical use to enhance the security of any given MPKC. Based on this equivalence, we show that the linear PH matrix method with random variables has the substantial advantage over the plus method with respect to the security enhancement. In the linear PH matrix method with random variables, the three matrices, including the PH matrix, play a central role in the secret-key and public-key. In this paper, we clarify how to generate these matrices and thus present two probabilistic polynomial-time algorithms to generate these matrices. In particular, the second one has a concise form, and is obtained as a byproduct of the proof of the equivalence between the plus method and the primitive linear PH matrix method.

Given a graph G=(V,E), a set of vertices S ⊆ V covers v ∈ V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + nlog n)-time algorithm for k=2, where n=|V| and m=|E|. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k-1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.

This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective function is introduced. A novel decision making model is constructed based on possibility theory and on a stochastic programming model. It is shown that the problem including both randomness and fuzziness is reduced to a deterministic equivalent problem. Finally, a polynomial-time algorithm is provided to solve the problem.

A siphon-trap of a Petri net N is defined as a place set S with S = S, where S = { u| N has an edge from u to a vertex of S} and S = { v| N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: (1) FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net; (2) FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. (3) STFM_T (STFM_Ti, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.

In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.

We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.

A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.

A subclass of context-free languages, called pure context-free languages, which is generated by context-free grammar with only one type of symbol (i.e., terminals and nonterminals are not distinguished), is introduced and the problem of identifying from positive data a restricted class of monogenic pure context-free languages (mono-PCF languages, in short) is investigated. The class of mono-PCF languages is incomparable to the class of regular languages. In this paper we show that the class of mono-PCF languages is polynomial time identifiable from positive data. That is, there is an algorithm that, given a mono-PCF language L, identifies from positive data, a grammar generating L, called a monogenic pure context-free grammar (mono-PCF grammar, in short) satisfying the property that the time for updating a conjecture is bounded by O(N3), where N is the sum of lengths of all positive data provided. This is in contrast with another result in this paper that the class of PCF languages is not identifiable in the limit from positive data.

A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

This paper concerns a subclass of regular languages, called strictly regular languages, and studies the problem of identifying the class of strictly regular languages in the limit from positive data. We show that the class of strictly regular languages (SRLs) is polynomial time identifiable in the limit from positive data. That is, there is an algorithm that, for any strictly regular language L, identifies a finite automaton accepting L, called a strictly deterministic finite automaton (SDFA) in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(mN2), where m is the cardinality of the alphabet for L and N is the sum of lengths of all positive data provided. This is in contrast with the fact that the class of regular languages is not identifiable in the limit from positive data.