Search

Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H , where a hyperarc is a pair < S , v > , S non empty subset of V and v ∈ V . DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and–or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided. [ABSTRACT FROM AUTHOR]

Abstract: We introduce the notion of a -path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between -paths and firable sequences of transitions. Let us consider a Petri net  and the set of places with a positive marking in , i.e., . If we regard the net as a directed graph, the existence of a simple path from any place in to a transition is, of course, a necessary condition for the potential firability of . This is sufficient only if the net is a state machine, where for all . In this paper we show that the existence of a -path from any subset of to a transition is a more restrictive condition and is, again, a necessary condition for the potential firability of . But, in this case: (a) if  is a conflict-free Petri net, this is also a sufficient condition, (b) if  is a general Petri net, is potentially firable by increasing the number of tokens in . For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of coverable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i.e., , for a net . Previous results for this class of networks are given by Howell et al. (1987) , providing algorithms for solving problems in conflict-free nets in time and space. Given a Petri net and a marking , the well-known coverability problem consists in finding a reachable marking such that ; this problem is known to be EXPSPACE hard (Rackoff (1978)). For general Petri nets we provide a partial answer to this problem. is coverable by augmentation if it is coverable from an augmented marking of the initial marking : and, for all , if . We solve this problem in linear time. The algorithms for computing -paths are incremental: it is possible to modify the network (adding new places, transitions, arcs, tokens), and update the set of potentially firable transitions and coverable places without recomputing them from scratch. This feature is meaningful when used during the interactive design of a system. [Copyright &y& Elsevier]