Confluence Competition

NFP Category

The NFP category is concerned with the normal form property (NFP) of first-order rewrite systems.

Format

The input is a first-order rewrite system without conditions, specified in the basic TRS format or the extended TRS format.

The question to be answered is whether the rewrite system has the property that every term which convertible to a normal form rewrites to that normal form. The first line of the output must be

In the first two cases, the output must be followed by justification that is understandable by a human expert.

Examples

  1. (VAR x)
    (RULES
      F(x,x) -> A
      G(x) -> F(x,G(x))
      C -> G(C)
    )
    
    The correct answer is NO and a possible output is
    NO
    
    The term G(A) and the normal form A are convertible, but G(A) does not
    rewrite to A.
    
  2. (RULES
      a -> b
      a -> c
      b -> b
      c -> c
    )
    
    The correct answer is YES and a possible output is
    YES
    
    There are no non-variable normal forms. Since the rules are
    non-collapsing, NFP holds trivially.
    

Problem Selection

Problems are selected among those in COPS with the 'trs' tag. Problems that were shown confluent by at least one participating tool in the CoCo 2018 full run are not considered.