Abstract:

Let $S$ be a finite set, and $R$ be a set of three element subsets of $S$. An element $r$ of $R$ is interpreted as a production rule which enables to derive one of the elements of $r$ from the others. A subset $X \subset S$ is conflicting if an element of $S$ can be derived from $X$ in two different ways. The problem of finding a largest non-conflicting subset is shown to be NP-complete.