%------------------------------------------------------------------------------
% File     : PUZ164-1 : TPTP v9.3.1. Released v9.3.0.
% Domain   : Puzzles
% Problem  : Verify the existence of a loop from 0 to 0.
% Version  : Especial
% English  : The predicate reach(X, Y, G, empty) is true if there is a path
%            from X to Y in the directed graph G.

% Refs     : [AG00]  Arts & Giesl (2000), Termination of Term Rewriting usi
%          : [AG01]  Arts & Giesl (1991), A Collection of Examples for Term
%          : [Sai24] Saito (2024), Email to Geoff Sutcliffe
% Source   : [Sai24]
% Names    : Example 3.13 [AG01]
%          : graph_loop.p [Sai24]

% Status   : Unsatisfiable
% Rating   : 0.56 v9.3.0
% Syntax   : Number of clauses     :   16 (  16 unt;   0 nHn;   3 RR)
%            Number of literals    :   16 (  16 equ;   1 neg)
%            Maximal clause size   :    1 (   1 avg)
%            Maximal term depth    :    8 (   2 avg)
%            Number of predicates  :    1 (   0 usr;   0 prp; 2-2 aty)
%            Number of functors    :   13 (  13 usr;   5 con; 0-5 aty)
%            Number of variables   :   44 (  13 sgn)
% SPC      : CNF_UNS_RFO_PEQ_UEQ

% Comments : The rules are of TRS_Standard/AG01/#3.13.ari from TPDB.
%------------------------------------------------------------------------------
cnf(rule1,axiom,
    eq(zero,zero) = true ).

cnf(rule2,axiom,
    eq(zero,s(X)) = false ).

cnf(rule3,axiom,
    eq(s(X),zero) = false ).

cnf(rule4,axiom,
    eq(s(X),s(Y)) = eq(X,Y) ).

cnf(rule5,axiom,
    or(true,Y) = true ).

cnf(rule6,axiom,
    or(false,Y) = Y ).

cnf(rule7,axiom,
    union(empty,H) = H ).

cnf(rule8,axiom,
    union(edge(X,Y,I),H) = edge(X,Y,union(I,H)) ).

cnf(rule9,axiom,
    reach(X,Y,empty,H) = false ).

cnf(rule10,axiom,
    reach(X,Y,edge(U,V,I),H) = if_reach_1(eq(X,U),X,Y,edge(U,V,I),H) ).

cnf(rule11,axiom,
    if_reach_1(true,X,Y,edge(U,V,I),H) = if_reach_2(eq(Y,V),X,Y,edge(U,V,I),H) ).

cnf(rule12,axiom,
    if_reach_2(true,X,Y,edge(U,V,I),H) = true ).

cnf(rule13,axiom,
    if_reach_2(false,X,Y,edge(U,V,I),H) = or(reach(X,Y,I,H),reach(V,Y,union(I,H),empty)) ).

cnf(rule14,axiom,
    if_reach_1(false,X,Y,edge(U,V,I),H) = reach(X,Y,I,edge(U,V,H)) ).

cnf(graph,axiom,
    g = edge(zero,s(zero),edge(s(zero),s(s(zero)),edge(s(s(zero)),s(s(s(zero))),edge(s(s(s(zero))),zero,empty)))) ).

cnf(goal,negated_conjecture,
    reach(zero,zero,g,empty) != true ).

%------------------------------------------------------------------------------