Conflict Reduction of Acyclic Flow Event Structures

摘要

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