Event structures are a well-known modeling formalism for concurrent systems with causality and conflict relations. The flow event structure (FES) is a variant of event structures, which is a generalization of the prime event structure. In an FES, two events may be in conflict even though they are not syntactically in conflict; this is called a semantic conflict. The existence of semantic conflict in an FES motivates reducing conflict relations (i.e., conflict reduction) to obtain a simpler structure. In this paper, we study conflict reduction in acyclic FESs. A necessary and sufficient condition for conflict reduction is given; algorithms to compute semantic conflict, local configurations, and conflict reduction are proposed. A great time reduction was observed in computational experiments when comparing the proposed with the naive method.

The choreography realization problem is a design challenge for systems based on service-oriented architecture. In our previous studies, we studied the problem on a case where choreography was given by one or two scenarios and was expressed by an acyclic relation of events; we introduced the notion of re-constructibility as a property of acyclic relations to be satisfied. However, when choreography is defined by multiple scenarios, the resulting behavior cannot be expressed by an acyclic relation. An event structure is composed of an acyclic relation and a conflict relation. Because event structures are a generalization of acyclic relations, a wider class of systems can be expressed by event structures. In this paper, we propose the use of event structures to express choreography, introduce the re-constructibility of event structures, and show a necessary condition for an event structure to be re-constructible.