We discuss the problem of non-intrusive concurrent error detection (CED) for random logic. We analyze the optimal solution model and we point out the limitations that prevent logic synthesis from yielding a minimal cost implementation. We explain how duplication-based CED exploits decomposition to alleviate these limitations for the unrestricted error model. We then examine a compaction-based CED method, which employs a similar decomposition principle to alleviate synthesis limitations for restricted error models. We demonstrate the cost reduction achieved by the decomposed method through experimental results and we discuss the points where optimality is lost, possible remedies, and extension to finite state machines (FSMs).