%------------------------------------------------------------------------------
% File     : PUZ164-2 : TPTP v9.3.1. Released v9.3.0.
% Domain   : Puzzles
% Problem  : Find a loop in the DAG 0 -> 1 -> 2 -> 3 -> 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_exist.p [Sai24]

% Status   : Unsatisfiable
% Rating   : 0.61 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   :   45 (  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('0','0') = true ).

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

cnf(rule3,axiom,
    eq(s(X),'0') = 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('0',s('0'),edge(s('0'),s(s('0')),edge(s(s('0')),s(s(s('0'))),edge(s(s(s('0'))),'0',empty)))) ).

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

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