Automated Proofs of Unique Normal Forms w.r.t. Conversion for Term Rewriting Systems.

The notion of normal forms is ubiquitous in various equivalent transformations. Confluence (CR), one of the central properties of term rewriting systems (TRSs), concerns uniqueness of normal forms. Yet another such property, which is weaker than confluence, is the property of unique normal forms w.r.t. conversion (UNC). Recently, automated confluence proof of TRSs has caught attentions; some powerful confluence tools integrating multiple methods for (dis)proving the CR property of TRSs have been developed. In contrast, there have been little efforts on (dis)proving the UNC property automatically yet. In this paper, we report on a UNC prover combining several methods for (dis)proving the UNC property. We present an equivalent transformation of TRSs preserving UNC, as well as some new criteria for (dis)proving UNC.