/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern ordered(g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) CutEliminatorProof [SOUND, 0 ms] (2) Prolog (3) PrologToPiTRSProof [SOUND, 26 ms] (4) PiTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [SOUND, 4 ms] (13) QDP (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PrologToPiTRSProof [SOUND, 22 ms] (18) PiTRS (19) DependencyPairsProof [EQUIVALENT, 27 ms] (20) PiDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) AND (23) PiDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) PiDP (26) PiDPToQDPProof [SOUND, 0 ms] (27) QDP (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PrologToDTProblemTransformerProof [SOUND, 62 ms] (32) TRIPLES (33) TriplesToPiDPProof [SOUND, 17 ms] (34) PiDP (35) DependencyGraphProof [EQUIVALENT, 0 ms] (36) AND (37) PiDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) PiDP (40) PiDPToQDPProof [EQUIVALENT, 0 ms] (41) QDP (42) NonTerminationLoopProof [COMPLETE, 0 ms] (43) NO (44) PiDP (45) UsableRulesProof [EQUIVALENT, 0 ms] (46) PiDP (47) PiDPToQDPProof [EQUIVALENT, 0 ms] (48) QDP (49) QDPSizeChangeProof [EQUIVALENT, 0 ms] (50) YES (51) PiDP (52) UsableRulesProof [EQUIVALENT, 0 ms] (53) PiDP (54) PiDPToQDPProof [EQUIVALENT, 0 ms] (55) QDP (56) QDPSizeChangeProof [EQUIVALENT, 0 ms] (57) YES (58) PiDP (59) PiDPToQDPProof [EQUIVALENT, 0 ms] (60) QDP (61) PrologToTRSTransformerProof [SOUND, 38 ms] (62) QTRS (63) Overlay + Local Confluence [EQUIVALENT, 0 ms] (64) QTRS (65) DependencyPairsProof [EQUIVALENT, 0 ms] (66) QDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) AND (69) QDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) QDP (72) QReductionProof [EQUIVALENT, 0 ms] (73) QDP (74) NonTerminationLoopProof [COMPLETE, 0 ms] (75) NO (76) QDP (77) UsableRulesProof [EQUIVALENT, 0 ms] (78) QDP (79) QReductionProof [EQUIVALENT, 0 ms] (80) QDP (81) QDPSizeChangeProof [EQUIVALENT, 0 ms] (82) YES (83) QDP (84) UsableRulesProof [EQUIVALENT, 0 ms] (85) QDP (86) QReductionProof [EQUIVALENT, 0 ms] (87) QDP (88) QDPSizeChangeProof [EQUIVALENT, 0 ms] (89) YES (90) QDP (91) UsableRulesProof [EQUIVALENT, 0 ms] (92) QDP (93) QReductionProof [EQUIVALENT, 0 ms] (94) QDP (95) QDPOrderProof [EQUIVALENT, 29 ms] (96) QDP (97) DependencyGraphProof [EQUIVALENT, 0 ms] (98) TRUE (99) PrologToIRSwTTransformerProof [SOUND, 60 ms] (100) AND (101) IRSwT (102) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (103) IRSwT (104) IntTRSCompressionProof [EQUIVALENT, 62 ms] (105) IRSwT (106) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (107) IRSwT (108) IRSwTTerminationDigraphProof [EQUIVALENT, 26 ms] (109) AND (110) IRSwT (111) IRSwT (112) IntTRSCompressionProof [EQUIVALENT, 0 ms] (113) IRSwT (114) IRSwT (115) IntTRSCompressionProof [EQUIVALENT, 0 ms] (116) IRSwT (117) IRSwT ---------------------------------------- (0) Obligation: Clauses: ordered([]) :- !. ordered(.(X1, [])) :- !. ordered(Xs) :- ','(head(Xs, X), ','(tail(Xs, Ys), ','(head(Ys, Y), ','(tail(Ys, Zs), ','(less(X, s(Y)), ordered(.(Y, Zs))))))). head([], X2). head(.(X, X3), X). tail([], []). tail(.(X4, Xs), Xs). less(0, s(X5)) :- !. less(X, Y) :- ','(p(X, Px), ','(p(Y, Py), less(Px, Py))). p(0, 0). p(s(X), X). Query: ordered(g) ---------------------------------------- (1) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (2) Obligation: Clauses: ordered([]). ordered(.(X1, [])). ordered(Xs) :- ','(head(Xs, X), ','(tail(Xs, Ys), ','(head(Ys, Y), ','(tail(Ys, Zs), ','(less(X, s(Y)), ordered(.(Y, Zs))))))). head([], X2). head(.(X, X3), X). tail([], []). tail(.(X4, Xs), Xs). less(0, s(X5)). less(X, Y) :- ','(p(X, Px), ','(p(Y, Py), less(Px, Py))). p(0, 0). p(s(X), X). Query: ordered(g) ---------------------------------------- (3) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: ordered_in_1: (b) (f) less_in_2: (f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (4) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: ORDERED_IN_G(Xs) -> U1_G(Xs, head_in_ga(Xs, X)) ORDERED_IN_G(Xs) -> HEAD_IN_GA(Xs, X) U1_G(Xs, head_out_ga(Xs, X)) -> U2_G(Xs, X, tail_in_ga(Xs, Ys)) U1_G(Xs, head_out_ga(Xs, X)) -> TAIL_IN_GA(Xs, Ys) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> U3_G(Xs, X, Ys, head_in_ga(Ys, Y)) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> HEAD_IN_GA(Ys, Y) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_G(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> TAIL_IN_GA(Ys, Zs) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_G(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) LESS_IN_AA(X, Y) -> P_IN_AA(X, Px) U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U7_AA(X, Y, p_out_aa(X, Px)) -> P_IN_AA(Y, Py) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> U9_AA(X, Y, Px, Py, less_in_aa(Px, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_G(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) ORDERED_IN_A(Xs) -> HEAD_IN_AA(Xs, X) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U1_A(Xs, head_out_aa(Xs, X)) -> TAIL_IN_AA(Xs, Ys) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> HEAD_IN_AA(Ys, Y) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> TAIL_IN_AA(Ys, Zs) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_A(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_G(x1, x2, x3) = U2_G(x1, x3) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_G(x1, x2, x3, x4) = U3_G(x1, x3, x4) U4_G(x1, x2, x3, x4, x5) = U4_G(x1, x5) U5_G(x1, x2, x3, x4, x5, x6) = U5_G(x1, x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) P_IN_AA(x1, x2) = P_IN_AA U8_AA(x1, x2, x3, x4) = U8_AA(x4) U9_AA(x1, x2, x3, x4, x5) = U9_AA(x5) U6_G(x1, x2, x3, x4, x5, x6) = U6_G(x1, x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U2_A(x1, x2, x3) = U2_A(x3) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) U6_A(x1, x2, x3, x4, x5, x6) = U6_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDERED_IN_G(Xs) -> U1_G(Xs, head_in_ga(Xs, X)) ORDERED_IN_G(Xs) -> HEAD_IN_GA(Xs, X) U1_G(Xs, head_out_ga(Xs, X)) -> U2_G(Xs, X, tail_in_ga(Xs, Ys)) U1_G(Xs, head_out_ga(Xs, X)) -> TAIL_IN_GA(Xs, Ys) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> U3_G(Xs, X, Ys, head_in_ga(Ys, Y)) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> HEAD_IN_GA(Ys, Y) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_G(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> TAIL_IN_GA(Ys, Zs) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_G(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) LESS_IN_AA(X, Y) -> P_IN_AA(X, Px) U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U7_AA(X, Y, p_out_aa(X, Px)) -> P_IN_AA(Y, Py) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> U9_AA(X, Y, Px, Py, less_in_aa(Px, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_G(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) ORDERED_IN_A(Xs) -> HEAD_IN_AA(Xs, X) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U1_A(Xs, head_out_aa(Xs, X)) -> TAIL_IN_AA(Xs, Ys) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> HEAD_IN_AA(Ys, Y) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> TAIL_IN_AA(Ys, Zs) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_A(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_G(x1, x2, x3) = U2_G(x1, x3) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_G(x1, x2, x3, x4) = U3_G(x1, x3, x4) U4_G(x1, x2, x3, x4, x5) = U4_G(x1, x5) U5_G(x1, x2, x3, x4, x5, x6) = U5_G(x1, x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) P_IN_AA(x1, x2) = P_IN_AA U8_AA(x1, x2, x3, x4) = U8_AA(x4) U9_AA(x1, x2, x3, x4, x5) = U9_AA(x5) U6_G(x1, x2, x3, x4, x5, x6) = U6_G(x1, x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U2_A(x1, x2, x3) = U2_A(x3) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) U6_A(x1, x2, x3, x4, x5, x6) = U6_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 21 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) U8_AA(x1, x2, x3, x4) = U8_AA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (11) Obligation: Pi DP problem: The TRS P consists of the following rules: U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) The TRS R consists of the following rules: p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) The argument filtering Pi contains the following mapping: p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) U8_AA(x1, x2, x3, x4) = U8_AA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: U7_AA(p_out_aa) -> U8_AA(p_in_aa) U8_AA(p_out_aa) -> LESS_IN_AA LESS_IN_AA -> U7_AA(p_in_aa) The TRS R consists of the following rules: p_in_aa -> p_out_aa The set Q consists of the following terms: p_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g(x1) .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U2_g(x1, x2, x3) = U2_g(x1, x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_g(x1, x2, x3, x4) = U3_g(x1, x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x1, x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x1, x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x1, x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) The TRS R consists of the following rules: less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: ordered_in_1: (b) (f) less_in_2: (f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (18) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ---------------------------------------- (19) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: ORDERED_IN_G(Xs) -> U1_G(Xs, head_in_ga(Xs, X)) ORDERED_IN_G(Xs) -> HEAD_IN_GA(Xs, X) U1_G(Xs, head_out_ga(Xs, X)) -> U2_G(Xs, X, tail_in_ga(Xs, Ys)) U1_G(Xs, head_out_ga(Xs, X)) -> TAIL_IN_GA(Xs, Ys) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> U3_G(Xs, X, Ys, head_in_ga(Ys, Y)) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> HEAD_IN_GA(Ys, Y) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_G(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> TAIL_IN_GA(Ys, Zs) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_G(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) LESS_IN_AA(X, Y) -> P_IN_AA(X, Px) U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U7_AA(X, Y, p_out_aa(X, Px)) -> P_IN_AA(Y, Py) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> U9_AA(X, Y, Px, Py, less_in_aa(Px, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_G(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) ORDERED_IN_A(Xs) -> HEAD_IN_AA(Xs, X) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U1_A(Xs, head_out_aa(Xs, X)) -> TAIL_IN_AA(Xs, Ys) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> HEAD_IN_AA(Ys, Y) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> TAIL_IN_AA(Ys, Zs) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_A(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_G(x1, x2, x3) = U2_G(x3) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_G(x1, x2, x3, x4) = U3_G(x3, x4) U4_G(x1, x2, x3, x4, x5) = U4_G(x5) U5_G(x1, x2, x3, x4, x5, x6) = U5_G(x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) P_IN_AA(x1, x2) = P_IN_AA U8_AA(x1, x2, x3, x4) = U8_AA(x4) U9_AA(x1, x2, x3, x4, x5) = U9_AA(x5) U6_G(x1, x2, x3, x4, x5, x6) = U6_G(x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U2_A(x1, x2, x3) = U2_A(x3) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) U6_A(x1, x2, x3, x4, x5, x6) = U6_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDERED_IN_G(Xs) -> U1_G(Xs, head_in_ga(Xs, X)) ORDERED_IN_G(Xs) -> HEAD_IN_GA(Xs, X) U1_G(Xs, head_out_ga(Xs, X)) -> U2_G(Xs, X, tail_in_ga(Xs, Ys)) U1_G(Xs, head_out_ga(Xs, X)) -> TAIL_IN_GA(Xs, Ys) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> U3_G(Xs, X, Ys, head_in_ga(Ys, Y)) U2_G(Xs, X, tail_out_ga(Xs, Ys)) -> HEAD_IN_GA(Ys, Y) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_G(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U3_G(Xs, X, Ys, head_out_ga(Ys, Y)) -> TAIL_IN_GA(Ys, Zs) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_G(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_G(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) LESS_IN_AA(X, Y) -> P_IN_AA(X, Px) U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U7_AA(X, Y, p_out_aa(X, Px)) -> P_IN_AA(Y, Py) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> U9_AA(X, Y, Px, Py, less_in_aa(Px, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_G(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_G(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) ORDERED_IN_A(Xs) -> HEAD_IN_AA(Xs, X) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U1_A(Xs, head_out_aa(Xs, X)) -> TAIL_IN_AA(Xs, Ys) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> HEAD_IN_AA(Ys, Y) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> TAIL_IN_AA(Ys, Zs) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> LESS_IN_AA(X, s(Y)) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_A(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U1_G(x1, x2) = U1_G(x1, x2) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_G(x1, x2, x3) = U2_G(x3) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_G(x1, x2, x3, x4) = U3_G(x3, x4) U4_G(x1, x2, x3, x4, x5) = U4_G(x5) U5_G(x1, x2, x3, x4, x5, x6) = U5_G(x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) P_IN_AA(x1, x2) = P_IN_AA U8_AA(x1, x2, x3, x4) = U8_AA(x4) U9_AA(x1, x2, x3, x4, x5) = U9_AA(x5) U6_G(x1, x2, x3, x4, x5, x6) = U6_G(x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U2_A(x1, x2, x3) = U2_A(x3) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) U6_A(x1, x2, x3, x4, x5, x6) = U6_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 21 less nodes. ---------------------------------------- (22) Complex Obligation (AND) ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) U8_AA(x1, x2, x3, x4) = U8_AA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: U7_AA(X, Y, p_out_aa(X, Px)) -> U8_AA(X, Y, Px, p_in_aa(Y, Py)) U8_AA(X, Y, Px, p_out_aa(Y, Py)) -> LESS_IN_AA(Px, Py) LESS_IN_AA(X, Y) -> U7_AA(X, Y, p_in_aa(X, Px)) The TRS R consists of the following rules: p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) The argument filtering Pi contains the following mapping: p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa LESS_IN_AA(x1, x2) = LESS_IN_AA U7_AA(x1, x2, x3) = U7_AA(x3) U8_AA(x1, x2, x3, x4) = U8_AA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U7_AA(p_out_aa) -> U8_AA(p_in_aa) U8_AA(p_out_aa) -> LESS_IN_AA LESS_IN_AA -> U7_AA(p_in_aa) The TRS R consists of the following rules: p_in_aa -> p_out_aa The set Q consists of the following terms: p_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) The TRS R consists of the following rules: ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(Xs) -> U1_g(Xs, head_in_ga(Xs, X)) head_in_ga([], X2) -> head_out_ga([], X2) head_in_ga(.(X, X3), X) -> head_out_ga(.(X, X3), X) U1_g(Xs, head_out_ga(Xs, X)) -> U2_g(Xs, X, tail_in_ga(Xs, Ys)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X4, Xs), Xs) -> tail_out_ga(.(X4, Xs), Xs) U2_g(Xs, X, tail_out_ga(Xs, Ys)) -> U3_g(Xs, X, Ys, head_in_ga(Ys, Y)) U3_g(Xs, X, Ys, head_out_ga(Ys, Y)) -> U4_g(Xs, X, Ys, Y, tail_in_ga(Ys, Zs)) U4_g(Xs, X, Ys, Y, tail_out_ga(Ys, Zs)) -> U5_g(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) U5_g(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_g(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) ordered_in_a([]) -> ordered_out_a([]) ordered_in_a(.(X1, [])) -> ordered_out_a(.(X1, [])) ordered_in_a(Xs) -> U1_a(Xs, head_in_aa(Xs, X)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) U1_a(Xs, head_out_aa(Xs, X)) -> U2_a(Xs, X, tail_in_aa(Xs, Ys)) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U2_a(Xs, X, tail_out_aa(Xs, Ys)) -> U3_a(Xs, X, Ys, head_in_aa(Ys, Y)) U3_a(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_a(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) U4_a(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_a(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_a(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> U6_a(Xs, X, Ys, Y, Zs, ordered_in_a(.(Y, Zs))) U6_a(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_a(Xs) U6_g(Xs, X, Ys, Y, Zs, ordered_out_a(.(Y, Zs))) -> ordered_out_g(Xs) The argument filtering Pi contains the following mapping: ordered_in_g(x1) = ordered_in_g(x1) [] = [] ordered_out_g(x1) = ordered_out_g .(x1, x2) = .(x1, x2) U1_g(x1, x2) = U1_g(x1, x2) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U2_g(x1, x2, x3) = U2_g(x3) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_g(x1, x2, x3, x4) = U3_g(x3, x4) U4_g(x1, x2, x3, x4, x5) = U4_g(x5) U5_g(x1, x2, x3, x4, x5, x6) = U5_g(x6) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) U6_g(x1, x2, x3, x4, x5, x6) = U6_g(x6) ordered_in_a(x1) = ordered_in_a ordered_out_a(x1) = ordered_out_a U1_a(x1, x2) = U1_a(x2) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U2_a(x1, x2, x3) = U2_a(x3) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U3_a(x1, x2, x3, x4) = U3_a(x4) U4_a(x1, x2, x3, x4, x5) = U4_a(x5) U5_a(x1, x2, x3, x4, x5, x6) = U5_a(x6) U6_a(x1, x2, x3, x4, x5, x6) = U6_a(x6) ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: U4_A(Xs, X, Ys, Y, tail_out_aa(Ys, Zs)) -> U5_A(Xs, X, Ys, Y, Zs, less_in_aa(X, s(Y))) U5_A(Xs, X, Ys, Y, Zs, less_out_aa(X, s(Y))) -> ORDERED_IN_A(.(Y, Zs)) ORDERED_IN_A(Xs) -> U1_A(Xs, head_in_aa(Xs, X)) U1_A(Xs, head_out_aa(Xs, X)) -> U2_A(Xs, X, tail_in_aa(Xs, Ys)) U2_A(Xs, X, tail_out_aa(Xs, Ys)) -> U3_A(Xs, X, Ys, head_in_aa(Ys, Y)) U3_A(Xs, X, Ys, head_out_aa(Ys, Y)) -> U4_A(Xs, X, Ys, Y, tail_in_aa(Ys, Zs)) The TRS R consists of the following rules: less_in_aa(0, s(X5)) -> less_out_aa(0, s(X5)) less_in_aa(X, Y) -> U7_aa(X, Y, p_in_aa(X, Px)) head_in_aa([], X2) -> head_out_aa([], X2) head_in_aa(.(X, X3), X) -> head_out_aa(.(X, X3), X) tail_in_aa([], []) -> tail_out_aa([], []) tail_in_aa(.(X4, Xs), Xs) -> tail_out_aa(.(X4, Xs), Xs) U7_aa(X, Y, p_out_aa(X, Px)) -> U8_aa(X, Y, Px, p_in_aa(Y, Py)) p_in_aa(0, 0) -> p_out_aa(0, 0) p_in_aa(s(X), X) -> p_out_aa(s(X), X) U8_aa(X, Y, Px, p_out_aa(Y, Py)) -> U9_aa(X, Y, Px, Py, less_in_aa(Px, Py)) U9_aa(X, Y, Px, Py, less_out_aa(Px, Py)) -> less_out_aa(X, Y) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) less_in_aa(x1, x2) = less_in_aa less_out_aa(x1, x2) = less_out_aa U7_aa(x1, x2, x3) = U7_aa(x3) p_in_aa(x1, x2) = p_in_aa p_out_aa(x1, x2) = p_out_aa U8_aa(x1, x2, x3, x4) = U8_aa(x4) U9_aa(x1, x2, x3, x4, x5) = U9_aa(x5) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa ORDERED_IN_A(x1) = ORDERED_IN_A U1_A(x1, x2) = U1_A(x2) U2_A(x1, x2, x3) = U2_A(x3) U3_A(x1, x2, x3, x4) = U3_A(x4) U4_A(x1, x2, x3, x4, x5) = U4_A(x5) U5_A(x1, x2, x3, x4, x5, x6) = U5_A(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(ordered ([]))", "(!)" ], [ "(ordered (. X1 ([])))", "(!)" ], [ "(ordered Xs)", "(',' (head Xs X) (',' (tail Xs Ys) (',' (head Ys Y) (',' (tail Ys Zs) (',' (less X (s Y)) (ordered (. Y Zs)))))))" ], [ "(head ([]) X2)", null ], [ "(head (. X X3) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 Xs) Xs)", null ], [ "(less (0) (s X5))", "(!)" ], [ "(less X Y)", "(',' (p X Px) (',' (p Y Py) (less Px Py)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ] ] }, "graph": { "nodes": { "709": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T63 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T63"], "free": [], "exprvars": [] } }, "46": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }, { "clause": 4, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" } ], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "47": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "48": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "49": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "276": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": 9, "scope": 10, "term": "(',' (p T58 X92) (',' (p T59 X93) (less X92 X93)))" }], "kb": { "nonunifying": [[ "(less T58 T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T59" ], "free": [ "X81", "X92", "X93" ], "exprvars": [] } }, "115": { "goal": [ { "clause": 7, "scope": 6, "term": "(less T16 (s T30))" }, { "clause": 8, "scope": 6, "term": "(less T16 (s T30))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": [], "exprvars": [] } }, "710": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "711": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T63 T66)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T63", "T66" ], "free": [], "exprvars": [] } }, "712": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_6)" }, { "clause": 8, "scope": 6, "term": "(less (0) (s T36))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [], "exprvars": [] } }, "50": { "goal": [ { "clause": 5, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }, { "clause": 6, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" } ], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "51": { "goal": [{ "clause": 6, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "518": { "goal": [{ "clause": 9, "scope": 11, "term": "(',' (p T59 X93) (less (0) X93))" }], "kb": { "nonunifying": [[ "(less (0) T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T59"], "free": [ "X81", "X93" ], "exprvars": [] } }, "10": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "98": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "11": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 2, "scope": 1, "term": "(ordered (. T3 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": 2, "scope": 1, "term": "(ordered T1)" }], "kb": { "nonunifying": [ [ "(ordered T1)", "(ordered ([]))" ], [ "(ordered T1)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X7"], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "363": { "goal": [{ "clause": 10, "scope": 10, "term": "(',' (p T58 X92) (',' (p T59 X93) (less X92 X93)))" }], "kb": { "nonunifying": [[ "(less T58 T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T59" ], "free": [ "X81", "X92", "X93" ], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": 8, "scope": 6, "term": "(less T16 (s T30))" }], "kb": { "nonunifying": [[ "(less T16 (s T30))", "(less (0) (s X54))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": ["X54"], "exprvars": [] } }, "167": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T45 T49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T49" ], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(ordered T1)" }, { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "522": { "goal": [{ "clause": 10, "scope": 11, "term": "(',' (p T59 X93) (less (0) X93))" }], "kb": { "nonunifying": [[ "(less (0) T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T59"], "free": [ "X81", "X93" ], "exprvars": [] } }, "7": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(ordered ([]))" }, { "clause": 2, "scope": 1, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [[ "(ordered T1)", "(ordered ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [ { "clause": 9, "scope": 10, "term": "(',' (p T58 X92) (',' (p T59 X93) (less X92 X93)))" }, { "clause": 10, "scope": 10, "term": "(',' (p T58 X92) (',' (p T59 X93) (less X92 X93)))" } ], "kb": { "nonunifying": [[ "(less T58 T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T59" ], "free": [ "X81", "X92", "X93" ], "exprvars": [] } }, "408": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T59 X93) (less (0) X93))" }], "kb": { "nonunifying": [[ "(less (0) T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T59"], "free": [ "X81", "X93" ], "exprvars": [] } }, "292": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T58 X92) (',' (p T59 X93) (less X92 X93)))" }], "kb": { "nonunifying": [[ "(less T58 T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T59" ], "free": [ "X81", "X92", "X93" ], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T41 X65) (',' (p (s T42) X66) (less X65 X66)))" }], "kb": { "nonunifying": [[ "(less T41 (s T42))", "(less (0) (s X54))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42" ], "free": [ "X54", "X65", "X66" ], "exprvars": [] } }, "495": { "goal": [ { "clause": 9, "scope": 11, "term": "(',' (p T59 X93) (less (0) X93))" }, { "clause": 10, "scope": 11, "term": "(',' (p T59 X93) (less (0) X93))" } ], "kb": { "nonunifying": [[ "(less (0) T59)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T59"], "free": [ "X81", "X93" ], "exprvars": [] } }, "254": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_9)" }, { "clause": 8, "scope": 9, "term": "(less (0) (s T53))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T53"], "free": [], "exprvars": [] } }, "134": { "goal": [ { "clause": 9, "scope": 7, "term": "(',' (p T41 X65) (',' (p (s T42) X66) (less X65 X66)))" }, { "clause": 10, "scope": 7, "term": "(',' (p T41 X65) (',' (p (s T42) X66) (less X65 X66)))" } ], "kb": { "nonunifying": [[ "(less T41 (s T42))", "(less (0) (s X54))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42" ], "free": [ "X54", "X65", "X66" ], "exprvars": [] } }, "530": { "goal": [{ "clause": -1, "scope": -1, "term": "(less (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "136": { "goal": [{ "clause": 10, "scope": 7, "term": "(',' (p T41 X65) (',' (p (s T42) X66) (less X65 X66)))" }], "kb": { "nonunifying": [[ "(less T41 (s T42))", "(less (0) (s X54))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42" ], "free": [ "X54", "X65", "X66" ], "exprvars": [] } }, "532": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } }, "419": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "617": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "74": { "goal": [ { "clause": 3, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }, { "clause": 4, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" } ], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } }, "75": { "goal": [{ "clause": 4, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } }, "140": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T42) X66) (less T45 X66))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T45" ], "free": ["X66"], "exprvars": [] } }, "142": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [ { "clause": 7, "scope": 9, "term": "(less T45 T49)" }, { "clause": 8, "scope": 9, "term": "(less T45 T49)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T49" ], "free": [], "exprvars": [] } }, "144": { "goal": [ { "clause": 9, "scope": 8, "term": "(',' (p (s T42) X66) (less T45 X66))" }, { "clause": 10, "scope": 8, "term": "(',' (p (s T42) X66) (less T45 X66))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T45" ], "free": ["X66"], "exprvars": [] } }, "102": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T16 (s T30)) (ordered (. T30 T31)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30", "T31" ], "free": [], "exprvars": [] } }, "146": { "goal": [{ "clause": 10, "scope": 8, "term": "(',' (p (s T42) X66) (less T45 X66))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T45" ], "free": ["X66"], "exprvars": [] } }, "268": { "goal": [{ "clause": 8, "scope": 9, "term": "(less T45 T49)" }], "kb": { "nonunifying": [[ "(less T45 T49)", "(less (0) (s X81))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T49" ], "free": ["X81"], "exprvars": [] } }, "106": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T16 (s T30))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": [], "exprvars": [] } }, "702": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T59 X93) (less T63 X93))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T63" ], "free": ["X93"], "exprvars": [] } }, "82": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T30 T31))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [], "exprvars": [] } }, "703": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "85": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "706": { "goal": [ { "clause": 9, "scope": 12, "term": "(',' (p T59 X93) (less T63 X93))" }, { "clause": 10, "scope": 12, "term": "(',' (p T59 X93) (less T63 X93))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T63" ], "free": ["X93"], "exprvars": [] } }, "86": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "707": { "goal": [{ "clause": 9, "scope": 12, "term": "(',' (p T59 X93) (less T63 X93))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T63" ], "free": ["X93"], "exprvars": [] } }, "708": { "goal": [{ "clause": 10, "scope": 12, "term": "(',' (p T59 X93) (less T63 X93))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T63" ], "free": ["X93"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "EVAL with clause\nordered([]) :- !_1.\nand substitutionT1 -> []" }, { "from": 4, "to": 8, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 9, "label": "CUT" }, { "from": 8, "to": 11, "label": "EVAL with clause\nordered(.(X7, [])) :- !_1.\nand substitutionX7 -> T3,\nT1 -> .(T3, [])" }, { "from": 8, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 10, "label": "SUCCESS" }, { "from": 11, "to": 13, "label": "CUT" }, { "from": 12, "to": 15, "label": "ONLY EVAL with clause\nordered(X9) :- ','(head(X9, X10), ','(tail(X9, X11), ','(head(X11, X12), ','(tail(X11, X13), ','(less(X10, s(X12)), ordered(.(X12, X13))))))).\nand substitutionT1 -> T5,\nX9 -> T5" }, { "from": 13, "to": 14, "label": "SUCCESS" }, { "from": 15, "to": 46, "label": "CASE" }, { "from": 46, "to": 47, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(T5), ordered([]))" }, { "from": 47, "to": 48, "label": "EVAL with clause\nhead(.(X20, X21), X20).\nand substitutionX20 -> T10,\nX21 -> T11,\nT5 -> .(T10, T11),\nX10 -> T10" }, { "from": 47, "to": 49, "label": "EVAL-BACKTRACK" }, { "from": 48, "to": 50, "label": "CASE" }, { "from": 50, "to": 51, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 51, "to": 73, "label": "ONLY EVAL with clause\ntail(.(X30, X31), X31).\nand substitutionT10 -> T16,\nX30 -> T16,\nT11 -> T17,\nX31 -> T17,\nX11 -> T17" }, { "from": 73, "to": 74, "label": "CASE" }, { "from": 74, "to": 75, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(.(T16, T17)), ordered(.(X7, [])))" }, { "from": 75, "to": 82, "label": "EVAL with clause\nhead(.(X40, X41), X40).\nand substitutionX40 -> T22,\nX41 -> T23,\nT17 -> .(T22, T23),\nX12 -> T22" }, { "from": 75, "to": 85, "label": "EVAL-BACKTRACK" }, { "from": 82, "to": 86, "label": "CASE" }, { "from": 86, "to": 98, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 98, "to": 102, "label": "ONLY EVAL with clause\ntail(.(X48, X49), X49).\nand substitutionT22 -> T30,\nX48 -> T30,\nT23 -> T31,\nX49 -> T31,\nX13 -> T31" }, { "from": 102, "to": 106, "label": "SPLIT 1" }, { "from": 102, "to": 109, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT30 is ground" }, { "from": 106, "to": 115, "label": "CASE" }, { "from": 109, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T30, T31)" }, { "from": 115, "to": 119, "label": "EVAL with clause\nless(0, s(X54)) :- !_6.\nand substitutionT16 -> 0,\nT30 -> T36,\nX54 -> T36" }, { "from": 115, "to": 122, "label": "EVAL-BACKTRACK" }, { "from": 119, "to": 124, "label": "CUT" }, { "from": 122, "to": 131, "label": "ONLY EVAL with clause\nless(X63, X64) :- ','(p(X63, X65), ','(p(X64, X66), less(X65, X66))).\nand substitutionT16 -> T41,\nX63 -> T41,\nT30 -> T42,\nX64 -> s(T42)" }, { "from": 124, "to": 126, "label": "SUCCESS" }, { "from": 131, "to": 134, "label": "CASE" }, { "from": 134, "to": 136, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (less(T41, s(T42)), less(0, s(X54)))" }, { "from": 136, "to": 140, "label": "EVAL with clause\np(s(X71), X71).\nand substitutionX71 -> T45,\nT41 -> s(T45),\nX65 -> T45" }, { "from": 136, "to": 142, "label": "EVAL-BACKTRACK" }, { "from": 140, "to": 144, "label": "CASE" }, { "from": 144, "to": 146, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 146, "to": 167, "label": "ONLY EVAL with clause\np(s(X77), X77).\nand substitutionT42 -> T49,\nX77 -> T49,\nX66 -> T49" }, { "from": 167, "to": 220, "label": "CASE" }, { "from": 220, "to": 254, "label": "EVAL with clause\nless(0, s(X81)) :- !_9.\nand substitutionT45 -> 0,\nX81 -> T53,\nT49 -> s(T53)" }, { "from": 220, "to": 268, "label": "EVAL-BACKTRACK" }, { "from": 254, "to": 276, "label": "CUT" }, { "from": 268, "to": 292, "label": "ONLY EVAL with clause\nless(X90, X91) :- ','(p(X90, X92), ','(p(X91, X93), less(X92, X93))).\nand substitutionT45 -> T58,\nX90 -> T58,\nT49 -> T59,\nX91 -> T59" }, { "from": 276, "to": 280, "label": "SUCCESS" }, { "from": 292, "to": 328, "label": "CASE" }, { "from": 328, "to": 353, "label": "PARALLEL" }, { "from": 328, "to": 363, "label": "PARALLEL" }, { "from": 353, "to": 408, "label": "EVAL with clause\np(0, 0).\nand substitutionT58 -> 0,\nX92 -> 0" }, { "from": 353, "to": 419, "label": "EVAL-BACKTRACK" }, { "from": 363, "to": 702, "label": "EVAL with clause\np(s(X102), X102).\nand substitutionX102 -> T63,\nT58 -> s(T63),\nX92 -> T63" }, { "from": 363, "to": 703, "label": "EVAL-BACKTRACK" }, { "from": 408, "to": 495, "label": "CASE" }, { "from": 495, "to": 518, "label": "PARALLEL" }, { "from": 495, "to": 522, "label": "PARALLEL" }, { "from": 518, "to": 530, "label": "EVAL with clause\np(0, 0).\nand substitutionT59 -> 0,\nX93 -> 0" }, { "from": 518, "to": 532, "label": "EVAL-BACKTRACK" }, { "from": 522, "to": 617, "label": "BACKTRACK\nfor clause: p(s(X), X)\nwith clash: (less(0, T59), less(0, s(X81)))" }, { "from": 530, "to": 167, "label": "INSTANCE with matching:\nT45 -> 0\nT49 -> 0" }, { "from": 702, "to": 706, "label": "CASE" }, { "from": 706, "to": 707, "label": "PARALLEL" }, { "from": 706, "to": 708, "label": "PARALLEL" }, { "from": 707, "to": 709, "label": "EVAL with clause\np(0, 0).\nand substitutionT59 -> 0,\nX93 -> 0" }, { "from": 707, "to": 710, "label": "EVAL-BACKTRACK" }, { "from": 708, "to": 711, "label": "EVAL with clause\np(s(X108), X108).\nand substitutionX108 -> T66,\nT59 -> s(T66),\nX93 -> T66" }, { "from": 708, "to": 712, "label": "EVAL-BACKTRACK" }, { "from": 709, "to": 167, "label": "INSTANCE with matching:\nT45 -> T63\nT49 -> 0" }, { "from": 711, "to": 167, "label": "INSTANCE with matching:\nT45 -> T63\nT49 -> T66" } ], "type": "Graph" } } ---------------------------------------- (32) Obligation: Triples: lessC(0, 0) :- lessC(0, 0). lessC(s(X1), 0) :- lessC(X1, 0). lessC(s(X1), s(X2)) :- lessC(X1, X2). orderedA(.(s(X1), .(X2, X3))) :- lessC(X1, X2). orderedA(.(X1, .(X2, X3))) :- ','(lesscB(X1, X2), orderedA(.(X2, X3))). Clauses: orderedcA([]). orderedcA(.(X1, [])). orderedcA(.(X1, .(X2, X3))) :- ','(lesscB(X1, X2), orderedcA(.(X2, X3))). lesscC(0, s(X1)). lesscC(0, 0) :- lesscC(0, 0). lesscC(s(X1), 0) :- lesscC(X1, 0). lesscC(s(X1), s(X2)) :- lesscC(X1, X2). lesscB(0, X1). lesscB(s(X1), X2) :- lesscC(X1, X2). Afs: orderedA(x1) = orderedA(x1) ---------------------------------------- (33) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: orderedA_in_1: (b) lessC_in_2: (b,b) lesscB_in_2: (b,b) lesscC_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> U4_G(X1, X2, X3, lessC_in_gg(X1, X2)) ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> LESSC_IN_GG(X1, X2) LESSC_IN_GG(0, 0) -> U1_GG(lessC_in_gg(0, 0)) LESSC_IN_GG(0, 0) -> LESSC_IN_GG(0, 0) LESSC_IN_GG(s(X1), 0) -> U2_GG(X1, lessC_in_gg(X1, 0)) LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) LESSC_IN_GG(s(X1), s(X2)) -> U3_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U5_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> U6_G(X1, X2, X3, orderedA_in_g(.(X2, X3))) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> U4_G(X1, X2, X3, lessC_in_gg(X1, X2)) ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> LESSC_IN_GG(X1, X2) LESSC_IN_GG(0, 0) -> U1_GG(lessC_in_gg(0, 0)) LESSC_IN_GG(0, 0) -> LESSC_IN_GG(0, 0) LESSC_IN_GG(s(X1), 0) -> U2_GG(X1, lessC_in_gg(X1, 0)) LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) LESSC_IN_GG(s(X1), s(X2)) -> U3_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U5_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> U6_G(X1, X2, X3, orderedA_in_g(.(X2, X3))) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 6 less nodes. ---------------------------------------- (36) Complex Obligation (AND) ---------------------------------------- (37) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(0, 0) -> LESSC_IN_GG(0, 0) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (38) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(0, 0) -> LESSC_IN_GG(0, 0) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(0, 0) -> LESSC_IN_GG(0, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (42) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = LESSC_IN_GG(0, 0) evaluates to t =LESSC_IN_GG(0, 0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from LESSC_IN_GG(0, 0) to LESSC_IN_GG(0, 0). ---------------------------------------- (43) NO ---------------------------------------- (44) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (45) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (49) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (50) YES ---------------------------------------- (51) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (52) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (53) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (54) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (56) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (57) YES ---------------------------------------- (58) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U5_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (59) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U5_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U5_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U13_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(0, 0) -> U10_gg(lesscC_in_gg(0, 0)) lesscC_in_gg(s(X1), 0) -> U11_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U12_gg(X1, X2, lesscC_in_gg(X1, X2)) U12_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U11_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U10_gg(lesscC_out_gg(0, 0)) -> lesscC_out_gg(0, 0) U13_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) The set Q consists of the following terms: lesscB_in_gg(x0, x1) lesscC_in_gg(x0, x1) U12_gg(x0, x1, x2) U11_gg(x0, x1) U10_gg(x0) U13_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 2, "program": { "directives": [], "clauses": [ [ "(ordered ([]))", "(!)" ], [ "(ordered (. X1 ([])))", "(!)" ], [ "(ordered Xs)", "(',' (head Xs X) (',' (tail Xs Ys) (',' (head Ys Y) (',' (tail Ys Zs) (',' (less X (s Y)) (ordered (. Y Zs)))))))" ], [ "(head ([]) X2)", null ], [ "(head (. X X3) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 Xs) Xs)", null ], [ "(less (0) (s X5))", "(!)" ], [ "(less X Y)", "(',' (p X Px) (',' (p Y Py) (less Px Py)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ] ] }, "graph": { "nodes": { "89": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } }, "type": "Nodes", "593": { "goal": [ { "clause": 9, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }, { "clause": 10, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "275": { "goal": [{ "clause": 8, "scope": 9, "term": "(less T47 T51)" }], "kb": { "nonunifying": [[ "(less T47 T51)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": ["X91"], "exprvars": [] } }, "473": { "goal": [{ "clause": -1, "scope": -1, "term": "(less (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "475": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [ { "clause": 7, "scope": 6, "term": "(less T18 (s T32))" }, { "clause": 8, "scope": 6, "term": "(less T18 (s T32))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": [], "exprvars": [] } }, "598": { "goal": [{ "clause": 9, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "599": { "goal": [{ "clause": 10, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "118": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_6)" }, { "clause": 8, "scope": 6, "term": "(less (0) (s T38))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "93": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "94": { "goal": [ { "clause": 5, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }, { "clause": 6, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" } ], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "95": { "goal": [{ "clause": 6, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "96": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "97": { "goal": [ { "clause": 3, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }, { "clause": 4, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" } ], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "99": { "goal": [{ "clause": 4, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "16": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(ordered ([]))" }, { "clause": 2, "scope": 1, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [ { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [[ "(ordered T1)", "(ordered ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 8, "scope": 6, "term": "(less T18 (s T32))" }], "kb": { "nonunifying": [[ "(less T18 (s T32))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": ["X64"], "exprvars": [] } }, "440": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(ordered T1)" }, { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "445": { "goal": [ { "clause": 9, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }, { "clause": 10, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" } ], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "446": { "goal": [{ "clause": 9, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "568": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "449": { "goal": [{ "clause": 10, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "605": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T65 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T65"], "free": [], "exprvars": [] } }, "20": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 2, "scope": 1, "term": "(ordered (. T4 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "608": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 2, "scope": 1, "term": "(ordered T1)" }], "kb": { "nonunifying": [ [ "(ordered T1)", "(ordered ([]))" ], [ "(ordered T1)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X8"], "exprvars": [] } }, "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } }, "175": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T47 T51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": [], "exprvars": [] } }, "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "135": { "goal": [ { "clause": 9, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }, { "clause": 10, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" } ], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "455": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "137": { "goal": [{ "clause": 10, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "458": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T44) X76) (less T47 X76))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "263": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_9)" }, { "clause": 8, "scope": 9, "term": "(less (0) (s T55))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": [], "exprvars": [] } }, "582": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "143": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "100": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "463": { "goal": [ { "clause": 9, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }, { "clause": 10, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" } ], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "101": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [ { "clause": 9, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" }, { "clause": 10, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "586": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "103": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "147": { "goal": [{ "clause": 10, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "224": { "goal": [ { "clause": 7, "scope": 9, "term": "(less T47 T51)" }, { "clause": 8, "scope": 9, "term": "(less T47 T51)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": [], "exprvars": [] } }, "466": { "goal": [{ "clause": 9, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "104": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "105": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T18 (s T32)) (ordered (. T32 T33)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32", "T33" ], "free": [], "exprvars": [] } }, "468": { "goal": [{ "clause": 10, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "107": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T18 (s T32))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": [], "exprvars": [] } }, "108": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T32 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": [], "exprvars": [] } }, "704": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T65 T68)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T65", "T68" ], "free": [], "exprvars": [] } }, "705": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "87": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }, { "clause": 4, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" } ], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 16, "label": "EVAL with clause\nordered([]) :- !_1.\nand substitutionT1 -> []" }, { "from": 5, "to": 17, "label": "EVAL-BACKTRACK" }, { "from": 16, "to": 18, "label": "CUT" }, { "from": 17, "to": 20, "label": "EVAL with clause\nordered(.(X8, [])) :- !_1.\nand substitutionX8 -> T4,\nT1 -> .(T4, [])" }, { "from": 17, "to": 21, "label": "EVAL-BACKTRACK" }, { "from": 18, "to": 19, "label": "SUCCESS" }, { "from": 20, "to": 22, "label": "CUT" }, { "from": 21, "to": 28, "label": "ONLY EVAL with clause\nordered(X17) :- ','(head(X17, X18), ','(tail(X17, X19), ','(head(X19, X20), ','(tail(X19, X21), ','(less(X18, s(X20)), ordered(.(X20, X21))))))).\nand substitutionT1 -> T7,\nX17 -> T7" }, { "from": 22, "to": 23, "label": "SUCCESS" }, { "from": 28, "to": 87, "label": "CASE" }, { "from": 87, "to": 89, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(T7), ordered([]))" }, { "from": 89, "to": 92, "label": "EVAL with clause\nhead(.(X30, X31), X30).\nand substitutionX30 -> T12,\nX31 -> T13,\nT7 -> .(T12, T13),\nX18 -> T12" }, { "from": 89, "to": 93, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 94, "label": "CASE" }, { "from": 94, "to": 95, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 95, "to": 96, "label": "ONLY EVAL with clause\ntail(.(X40, X41), X41).\nand substitutionT12 -> T18,\nX40 -> T18,\nT13 -> T19,\nX41 -> T19,\nX19 -> T19" }, { "from": 96, "to": 97, "label": "CASE" }, { "from": 97, "to": 99, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(.(T18, T19)), ordered(.(X8, [])))" }, { "from": 99, "to": 100, "label": "EVAL with clause\nhead(.(X50, X51), X50).\nand substitutionX50 -> T24,\nX51 -> T25,\nT19 -> .(T24, T25),\nX20 -> T24" }, { "from": 99, "to": 101, "label": "EVAL-BACKTRACK" }, { "from": 100, "to": 103, "label": "CASE" }, { "from": 103, "to": 104, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 104, "to": 105, "label": "ONLY EVAL with clause\ntail(.(X58, X59), X59).\nand substitutionT24 -> T32,\nX58 -> T32,\nT25 -> T33,\nX59 -> T33,\nX21 -> T33" }, { "from": 105, "to": 107, "label": "SPLIT 1" }, { "from": 105, "to": 108, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT32 is ground" }, { "from": 107, "to": 114, "label": "CASE" }, { "from": 108, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T32, T33)" }, { "from": 114, "to": 118, "label": "EVAL with clause\nless(0, s(X64)) :- !_6.\nand substitutionT18 -> 0,\nT32 -> T38,\nX64 -> T38" }, { "from": 114, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 118, "to": 123, "label": "CUT" }, { "from": 121, "to": 132, "label": "ONLY EVAL with clause\nless(X73, X74) :- ','(p(X73, X75), ','(p(X74, X76), less(X75, X76))).\nand substitutionT18 -> T43,\nX73 -> T43,\nT32 -> T44,\nX74 -> s(T44)" }, { "from": 123, "to": 125, "label": "SUCCESS" }, { "from": 132, "to": 135, "label": "CASE" }, { "from": 135, "to": 137, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (less(T43, s(T44)), less(0, s(X64)))" }, { "from": 137, "to": 141, "label": "EVAL with clause\np(s(X81), X81).\nand substitutionX81 -> T47,\nT43 -> s(T47),\nX75 -> T47" }, { "from": 137, "to": 143, "label": "EVAL-BACKTRACK" }, { "from": 141, "to": 145, "label": "CASE" }, { "from": 145, "to": 147, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 147, "to": 175, "label": "ONLY EVAL with clause\np(s(X87), X87).\nand substitutionT44 -> T51,\nX87 -> T51,\nX76 -> T51" }, { "from": 175, "to": 224, "label": "CASE" }, { "from": 224, "to": 263, "label": "EVAL with clause\nless(0, s(X91)) :- !_9.\nand substitutionT47 -> 0,\nX91 -> T55,\nT51 -> s(T55)" }, { "from": 224, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 263, "to": 282, "label": "CUT" }, { "from": 275, "to": 440, "label": "ONLY EVAL with clause\nless(X100, X101) :- ','(p(X100, X102), ','(p(X101, X103), less(X102, X103))).\nand substitutionT47 -> T60,\nX100 -> T60,\nT51 -> T61,\nX101 -> T61" }, { "from": 282, "to": 283, "label": "SUCCESS" }, { "from": 440, "to": 445, "label": "CASE" }, { "from": 445, "to": 446, "label": "PARALLEL" }, { "from": 445, "to": 449, "label": "PARALLEL" }, { "from": 446, "to": 455, "label": "EVAL with clause\np(0, 0).\nand substitutionT60 -> 0,\nX102 -> 0" }, { "from": 446, "to": 458, "label": "EVAL-BACKTRACK" }, { "from": 449, "to": 582, "label": "EVAL with clause\np(s(X112), X112).\nand substitutionX112 -> T65,\nT60 -> s(T65),\nX102 -> T65" }, { "from": 449, "to": 586, "label": "EVAL-BACKTRACK" }, { "from": 455, "to": 463, "label": "CASE" }, { "from": 463, "to": 466, "label": "PARALLEL" }, { "from": 463, "to": 468, "label": "PARALLEL" }, { "from": 466, "to": 473, "label": "EVAL with clause\np(0, 0).\nand substitutionT61 -> 0,\nX103 -> 0" }, { "from": 466, "to": 475, "label": "EVAL-BACKTRACK" }, { "from": 468, "to": 568, "label": "BACKTRACK\nfor clause: p(s(X), X)\nwith clash: (less(0, T61), less(0, s(X91)))" }, { "from": 473, "to": 175, "label": "INSTANCE with matching:\nT47 -> 0\nT51 -> 0" }, { "from": 582, "to": 593, "label": "CASE" }, { "from": 593, "to": 598, "label": "PARALLEL" }, { "from": 593, "to": 599, "label": "PARALLEL" }, { "from": 598, "to": 605, "label": "EVAL with clause\np(0, 0).\nand substitutionT61 -> 0,\nX103 -> 0" }, { "from": 598, "to": 608, "label": "EVAL-BACKTRACK" }, { "from": 599, "to": 704, "label": "EVAL with clause\np(s(X118), X118).\nand substitutionX118 -> T68,\nT61 -> s(T68),\nX103 -> T68" }, { "from": 599, "to": 705, "label": "EVAL-BACKTRACK" }, { "from": 605, "to": 175, "label": "INSTANCE with matching:\nT47 -> T65\nT51 -> 0" }, { "from": 704, "to": 175, "label": "INSTANCE with matching:\nT47 -> T65\nT51 -> T68" } ], "type": "Graph" } } ---------------------------------------- (62) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 Q is empty. ---------------------------------------- (63) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (64) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) ---------------------------------------- (65) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T18, .(T32, T33))) -> U1^1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) F2_IN(.(T18, .(T32, T33))) -> F105_IN(T18, T32, T33) F175_IN(0, 0) -> U2^1(f175_in(0, 0), 0, 0) F175_IN(0, 0) -> F175_IN(0, 0) F175_IN(s(T65), 0) -> U3^1(f175_in(T65, 0), s(T65), 0) F175_IN(s(T65), 0) -> F175_IN(T65, 0) F175_IN(s(T65), s(T68)) -> U4^1(f175_in(T65, T68), s(T65), s(T68)) F175_IN(s(T65), s(T68)) -> F175_IN(T65, T68) F107_IN(s(T47), T51) -> U5^1(f175_in(T47, T51), s(T47), T51) F107_IN(s(T47), T51) -> F175_IN(T47, T51) F105_IN(T18, T32, T33) -> U6^1(f107_in(T18, T32), T18, T32, T33) F105_IN(T18, T32, T33) -> F107_IN(T18, T32) U6^1(f107_out1, T18, T32, T33) -> U7^1(f2_in(.(T32, T33)), T18, T32, T33) U6^1(f107_out1, T18, T32, T33) -> F2_IN(.(T32, T33)) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 8 less nodes. ---------------------------------------- (68) Complex Obligation (AND) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(0, 0) -> F175_IN(0, 0) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(0, 0) -> F175_IN(0, 0) R is empty. The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(0, 0) -> F175_IN(0, 0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F175_IN(0, 0) evaluates to t =F175_IN(0, 0) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F175_IN(0, 0) to F175_IN(0, 0). ---------------------------------------- (75) NO ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), 0) -> F175_IN(T65, 0) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), 0) -> F175_IN(T65, 0) R is empty. The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), 0) -> F175_IN(T65, 0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F175_IN(s(T65), 0) -> F175_IN(T65, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (82) YES ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), s(T68)) -> F175_IN(T65, T68) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), s(T68)) -> F175_IN(T65, T68) R is empty. The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: F175_IN(s(T65), s(T68)) -> F175_IN(T65, T68) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F175_IN(s(T65), s(T68)) -> F175_IN(T65, T68) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (89) YES ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T18, .(T32, T33))) -> F105_IN(T18, T32, T33) F105_IN(T18, T32, T33) -> U6^1(f107_in(T18, T32), T18, T32, T33) U6^1(f107_out1, T18, T32, T33) -> F2_IN(.(T32, T33)) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T4, [])) -> f2_out1 f2_in(.(T18, .(T32, T33))) -> U1(f105_in(T18, T32, T33), .(T18, .(T32, T33))) U1(f105_out1, .(T18, .(T32, T33))) -> f2_out1 f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) U2(f175_out1, 0, 0) -> f175_out1 f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) U3(f175_out1, s(T65), 0) -> f175_out1 f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U4(f175_out1, s(T65), s(T68)) -> f175_out1 f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 f105_in(T18, T32, T33) -> U6(f107_in(T18, T32), T18, T32, T33) U6(f107_out1, T18, T32, T33) -> U7(f2_in(.(T32, T33)), T18, T32, T33) U7(f2_out1, T18, T32, T33) -> f105_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T18, .(T32, T33))) -> F105_IN(T18, T32, T33) F105_IN(T18, T32, T33) -> U6^1(f107_in(T18, T32), T18, T32, T33) U6^1(f107_out1, T18, T32, T33) -> F2_IN(.(T32, T33)) The TRS R consists of the following rules: f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U5(f175_out1, s(T47), T51) -> f107_out1 U4(f175_out1, s(T65), s(T68)) -> f175_out1 U3(f175_out1, s(T65), 0) -> f175_out1 U2(f175_out1, 0, 0) -> f175_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f2_in([]) f2_in(.(x0, [])) f2_in(.(x0, .(x1, x2))) U1(f105_out1, .(x0, .(x1, x2))) f105_in(x0, x1, x2) U6(f107_out1, x0, x1, x2) U7(f2_out1, x0, x1, x2) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T18, .(T32, T33))) -> F105_IN(T18, T32, T33) F105_IN(T18, T32, T33) -> U6^1(f107_in(T18, T32), T18, T32, T33) U6^1(f107_out1, T18, T32, T33) -> F2_IN(.(T32, T33)) The TRS R consists of the following rules: f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U5(f175_out1, s(T47), T51) -> f107_out1 U4(f175_out1, s(T65), s(T68)) -> f175_out1 U3(f175_out1, s(T65), 0) -> f175_out1 U2(f175_out1, 0, 0) -> f175_out1 The set Q consists of the following terms: f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U6^1(f107_out1, T18, T32, T33) -> F2_IN(.(T32, T33)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U6^1_4(x_1, ..., x_4) ) = max{0, 2x_1 + 2x_3 + x_4 - 1} POL( f107_in_2(x_1, x_2) ) = x_1 POL( 0 ) = 1 POL( f107_out1 ) = 1 POL( s_1(x_1) ) = 1 POL( U5_3(x_1, ..., x_3) ) = 1 POL( f175_in_2(x_1, x_2) ) = max{0, -2} POL( f175_out1 ) = 1 POL( U2_3(x_1, ..., x_3) ) = 1 POL( U3_3(x_1, ..., x_3) ) = max{0, -2} POL( U4_3(x_1, ..., x_3) ) = max{0, 2x_2 + 2x_3 - 2} POL( F2_IN_1(x_1) ) = max{0, x_1 - 2} POL( ._2(x_1, x_2) ) = 2x_1 + x_2 + 1 POL( F105_IN_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + x_3 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) U5(f175_out1, s(T47), T51) -> f107_out1 ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T18, .(T32, T33))) -> F105_IN(T18, T32, T33) F105_IN(T18, T32, T33) -> U6^1(f107_in(T18, T32), T18, T32, T33) The TRS R consists of the following rules: f107_in(0, T38) -> f107_out1 f107_in(s(T47), T51) -> U5(f175_in(T47, T51), s(T47), T51) f175_in(0, s(T55)) -> f175_out1 f175_in(0, 0) -> U2(f175_in(0, 0), 0, 0) f175_in(s(T65), 0) -> U3(f175_in(T65, 0), s(T65), 0) f175_in(s(T65), s(T68)) -> U4(f175_in(T65, T68), s(T65), s(T68)) U5(f175_out1, s(T47), T51) -> f107_out1 U4(f175_out1, s(T65), s(T68)) -> f175_out1 U3(f175_out1, s(T65), 0) -> f175_out1 U2(f175_out1, 0, 0) -> f175_out1 The set Q consists of the following terms: f175_in(0, s(x0)) f175_in(0, 0) U2(f175_out1, 0, 0) f175_in(s(x0), 0) U3(f175_out1, s(x0), 0) f175_in(s(x0), s(x1)) U4(f175_out1, s(x0), s(x1)) f107_in(0, x0) f107_in(s(x0), x1) U5(f175_out1, s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (98) TRUE ---------------------------------------- (99) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(ordered ([]))", "(!)" ], [ "(ordered (. X1 ([])))", "(!)" ], [ "(ordered Xs)", "(',' (head Xs X) (',' (tail Xs Ys) (',' (head Ys Y) (',' (tail Ys Zs) (',' (less X (s Y)) (ordered (. Y Zs)))))))" ], [ "(head ([]) X2)", null ], [ "(head (. X X3) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 Xs) Xs)", null ], [ "(less (0) (s X5))", "(!)" ], [ "(less X Y)", "(',' (p X Px) (',' (p Y Py) (less Px Py)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ] ] }, "graph": { "nodes": { "88": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } }, "type": "Nodes", "790": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "791": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "110": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "792": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "793": { "goal": [ { "clause": 9, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }, { "clause": 10, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "112": { "goal": [ { "clause": 5, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }, { "clause": 6, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" } ], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "794": { "goal": [{ "clause": 9, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "113": { "goal": [{ "clause": 6, "scope": 3, "term": "(',' (tail (. T12 T13) X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less T12 (s X20)) (ordered (. X20 X21))))))" }], "kb": { "nonunifying": [[ "(ordered (. T12 T13))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X8", "X19", "X20", "X21" ], "exprvars": [] } }, "795": { "goal": [{ "clause": 10, "scope": 12, "term": "(',' (p T61 X103) (less T65 X103))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T65" ], "free": ["X103"], "exprvars": [] } }, "796": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T65 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T65"], "free": [], "exprvars": [] } }, "797": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "116": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "798": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T65 T68)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T65", "T68" ], "free": [], "exprvars": [] } }, "90": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }, { "clause": 4, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" } ], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } }, "117": { "goal": [ { "clause": 3, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }, { "clause": 4, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" } ], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "799": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "91": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (head T7 X18) (',' (tail T7 X19) (',' (head X19 X20) (',' (tail X19 X21) (',' (less X18 (s X20)) (ordered (. X20 X21)))))))" }], "kb": { "nonunifying": [ [ "(ordered T7)", "(ordered ([]))" ], [ "(ordered T7)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [ "X8", "X18", "X19", "X20", "X21" ], "exprvars": [] } }, "439": { "goal": [ { "clause": 7, "scope": 6, "term": "(less T18 (s T32))" }, { "clause": 8, "scope": 6, "term": "(less T18 (s T32))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": [], "exprvars": [] } }, "120": { "goal": [{ "clause": 4, "scope": 4, "term": "(',' (head T19 X20) (',' (tail T19 X21) (',' (less T18 (s X20)) (ordered (. X20 X21)))))" }], "kb": { "nonunifying": [[ "(ordered (. T18 T19))", "(ordered (. X8 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X8", "X20", "X21" ], "exprvars": [] } }, "441": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_6)" }, { "clause": 8, "scope": 6, "term": "(less (0) (s T38))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [], "exprvars": [] } }, "442": { "goal": [{ "clause": 8, "scope": 6, "term": "(less T18 (s T32))" }], "kb": { "nonunifying": [[ "(less T18 (s T32))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": ["X64"], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "443": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "444": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(ordered T1)" }, { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "766": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "129": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "767": { "goal": [ { "clause": 9, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }, { "clause": 10, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" } ], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "768": { "goal": [{ "clause": 10, "scope": 7, "term": "(',' (p T43 X75) (',' (p (s T44) X76) (less X75 X76)))" }], "kb": { "nonunifying": [[ "(less T43 (s T44))", "(less (0) (s X64))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44" ], "free": [ "X64", "X75", "X76" ], "exprvars": [] } }, "769": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T44) X76) (less T47 X76))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "130": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (. T24 T25) X21) (',' (less T18 (s T24)) (ordered (. T24 X21))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T24", "T25" ], "free": ["X21"], "exprvars": [] } }, "770": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T18 (s T32)) (ordered (. T32 T33)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32", "T33" ], "free": [], "exprvars": [] } }, "771": { "goal": [ { "clause": 9, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" }, { "clause": 10, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "772": { "goal": [{ "clause": 10, "scope": 8, "term": "(',' (p (s T44) X76) (less T47 X76))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T47" ], "free": ["X76"], "exprvars": [] } }, "773": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T47 T51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": [], "exprvars": [] } }, "774": { "goal": [ { "clause": 7, "scope": 9, "term": "(less T47 T51)" }, { "clause": 8, "scope": 9, "term": "(less T47 T51)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": [], "exprvars": [] } }, "775": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_9)" }, { "clause": 8, "scope": 9, "term": "(less (0) (s T55))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T55"], "free": [], "exprvars": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T18 (s T32))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T32" ], "free": [], "exprvars": [] } }, "776": { "goal": [{ "clause": 8, "scope": 9, "term": "(less T47 T51)" }], "kb": { "nonunifying": [[ "(less T47 T51)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T51" ], "free": ["X91"], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T32 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": [], "exprvars": [] } }, "777": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "778": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "779": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "76": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(ordered ([]))" }, { "clause": 2, "scope": 1, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "77": { "goal": [ { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [[ "(ordered T1)", "(ordered ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "78": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "79": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "780": { "goal": [ { "clause": 9, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }, { "clause": 10, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" } ], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "781": { "goal": [{ "clause": 9, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "782": { "goal": [{ "clause": 10, "scope": 10, "term": "(',' (p T60 X102) (',' (p T61 X103) (less X102 X103)))" }], "kb": { "nonunifying": [[ "(less T60 T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": [ "X91", "X102", "X103" ], "exprvars": [] } }, "783": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "784": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "785": { "goal": [ { "clause": 9, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }, { "clause": 10, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" } ], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "786": { "goal": [{ "clause": 9, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "787": { "goal": [{ "clause": 10, "scope": 11, "term": "(',' (p T61 X103) (less (0) X103))" }], "kb": { "nonunifying": [[ "(less (0) T61)", "(less (0) (s X91))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [ "X91", "X103" ], "exprvars": [] } }, "788": { "goal": [{ "clause": -1, "scope": -1, "term": "(less (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "80": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 2, "scope": 1, "term": "(ordered (. T4 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "789": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "81": { "goal": [{ "clause": 2, "scope": 1, "term": "(ordered T1)" }], "kb": { "nonunifying": [ [ "(ordered T1)", "(ordered ([]))" ], [ "(ordered T1)", "(ordered (. X8 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X8"], "exprvars": [] } }, "83": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "84": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 76, "label": "EVAL with clause\nordered([]) :- !_1.\nand substitutionT1 -> []" }, { "from": 6, "to": 77, "label": "EVAL-BACKTRACK" }, { "from": 76, "to": 78, "label": "CUT" }, { "from": 77, "to": 80, "label": "EVAL with clause\nordered(.(X8, [])) :- !_1.\nand substitutionX8 -> T4,\nT1 -> .(T4, [])" }, { "from": 77, "to": 81, "label": "EVAL-BACKTRACK" }, { "from": 78, "to": 79, "label": "SUCCESS" }, { "from": 80, "to": 83, "label": "CUT" }, { "from": 81, "to": 88, "label": "ONLY EVAL with clause\nordered(X17) :- ','(head(X17, X18), ','(tail(X17, X19), ','(head(X19, X20), ','(tail(X19, X21), ','(less(X18, s(X20)), ordered(.(X20, X21))))))).\nand substitutionT1 -> T7,\nX17 -> T7" }, { "from": 83, "to": 84, "label": "SUCCESS" }, { "from": 88, "to": 90, "label": "CASE" }, { "from": 90, "to": 91, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(T7), ordered([]))" }, { "from": 91, "to": 110, "label": "EVAL with clause\nhead(.(X30, X31), X30).\nand substitutionX30 -> T12,\nX31 -> T13,\nT7 -> .(T12, T13),\nX18 -> T12" }, { "from": 91, "to": 111, "label": "EVAL-BACKTRACK" }, { "from": 110, "to": 112, "label": "CASE" }, { "from": 112, "to": 113, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 113, "to": 116, "label": "ONLY EVAL with clause\ntail(.(X40, X41), X41).\nand substitutionT12 -> T18,\nX40 -> T18,\nT13 -> T19,\nX41 -> T19,\nX19 -> T19" }, { "from": 116, "to": 117, "label": "CASE" }, { "from": 117, "to": 120, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(.(T18, T19)), ordered(.(X8, [])))" }, { "from": 120, "to": 127, "label": "EVAL with clause\nhead(.(X50, X51), X50).\nand substitutionX50 -> T24,\nX51 -> T25,\nT19 -> .(T24, T25),\nX20 -> T24" }, { "from": 120, "to": 128, "label": "EVAL-BACKTRACK" }, { "from": 127, "to": 129, "label": "CASE" }, { "from": 129, "to": 130, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 130, "to": 133, "label": "ONLY EVAL with clause\ntail(.(X58, X59), X59).\nand substitutionT24 -> T32,\nX58 -> T32,\nT25 -> T33,\nX59 -> T33,\nX21 -> T33" }, { "from": 133, "to": 138, "label": "SPLIT 1" }, { "from": 133, "to": 139, "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT32 is ground" }, { "from": 138, "to": 439, "label": "CASE" }, { "from": 139, "to": 3, "label": "INSTANCE with matching:\nT1 -> .(T32, T33)" }, { "from": 439, "to": 441, "label": "EVAL with clause\nless(0, s(X64)) :- !_6.\nand substitutionT18 -> 0,\nT32 -> T38,\nX64 -> T38" }, { "from": 439, "to": 442, "label": "EVAL-BACKTRACK" }, { "from": 441, "to": 443, "label": "CUT" }, { "from": 442, "to": 766, "label": "ONLY EVAL with clause\nless(X73, X74) :- ','(p(X73, X75), ','(p(X74, X76), less(X75, X76))).\nand substitutionT18 -> T43,\nX73 -> T43,\nT32 -> T44,\nX74 -> s(T44)" }, { "from": 443, "to": 444, "label": "SUCCESS" }, { "from": 766, "to": 767, "label": "CASE" }, { "from": 767, "to": 768, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (less(T43, s(T44)), less(0, s(X64)))" }, { "from": 768, "to": 769, "label": "EVAL with clause\np(s(X81), X81).\nand substitutionX81 -> T47,\nT43 -> s(T47),\nX75 -> T47" }, { "from": 768, "to": 770, "label": "EVAL-BACKTRACK" }, { "from": 769, "to": 771, "label": "CASE" }, { "from": 771, "to": 772, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 772, "to": 773, "label": "ONLY EVAL with clause\np(s(X87), X87).\nand substitutionT44 -> T51,\nX87 -> T51,\nX76 -> T51" }, { "from": 773, "to": 774, "label": "CASE" }, { "from": 774, "to": 775, "label": "EVAL with clause\nless(0, s(X91)) :- !_9.\nand substitutionT47 -> 0,\nX91 -> T55,\nT51 -> s(T55)" }, { "from": 774, "to": 776, "label": "EVAL-BACKTRACK" }, { "from": 775, "to": 777, "label": "CUT" }, { "from": 776, "to": 779, "label": "ONLY EVAL with clause\nless(X100, X101) :- ','(p(X100, X102), ','(p(X101, X103), less(X102, X103))).\nand substitutionT47 -> T60,\nX100 -> T60,\nT51 -> T61,\nX101 -> T61" }, { "from": 777, "to": 778, "label": "SUCCESS" }, { "from": 779, "to": 780, "label": "CASE" }, { "from": 780, "to": 781, "label": "PARALLEL" }, { "from": 780, "to": 782, "label": "PARALLEL" }, { "from": 781, "to": 783, "label": "EVAL with clause\np(0, 0).\nand substitutionT60 -> 0,\nX102 -> 0" }, { "from": 781, "to": 784, "label": "EVAL-BACKTRACK" }, { "from": 782, "to": 791, "label": "EVAL with clause\np(s(X112), X112).\nand substitutionX112 -> T65,\nT60 -> s(T65),\nX102 -> T65" }, { "from": 782, "to": 792, "label": "EVAL-BACKTRACK" }, { "from": 783, "to": 785, "label": "CASE" }, { "from": 785, "to": 786, "label": "PARALLEL" }, { "from": 785, "to": 787, "label": "PARALLEL" }, { "from": 786, "to": 788, "label": "EVAL with clause\np(0, 0).\nand substitutionT61 -> 0,\nX103 -> 0" }, { "from": 786, "to": 789, "label": "EVAL-BACKTRACK" }, { "from": 787, "to": 790, "label": "BACKTRACK\nfor clause: p(s(X), X)\nwith clash: (less(0, T61), less(0, s(X91)))" }, { "from": 788, "to": 773, "label": "INSTANCE with matching:\nT47 -> 0\nT51 -> 0" }, { "from": 791, "to": 793, "label": "CASE" }, { "from": 793, "to": 794, "label": "PARALLEL" }, { "from": 793, "to": 795, "label": "PARALLEL" }, { "from": 794, "to": 796, "label": "EVAL with clause\np(0, 0).\nand substitutionT61 -> 0,\nX103 -> 0" }, { "from": 794, "to": 797, "label": "EVAL-BACKTRACK" }, { "from": 795, "to": 798, "label": "EVAL with clause\np(s(X118), X118).\nand substitutionX118 -> T68,\nT61 -> s(T68),\nX103 -> T68" }, { "from": 795, "to": 799, "label": "EVAL-BACKTRACK" }, { "from": 796, "to": 773, "label": "INSTANCE with matching:\nT47 -> T65\nT51 -> 0" }, { "from": 798, "to": 773, "label": "INSTANCE with matching:\nT47 -> T65\nT51 -> T68" } ], "type": "Graph" } } ---------------------------------------- (100) Complex Obligation (AND) ---------------------------------------- (101) Obligation: Rules: f791_in(T61, T65) -> f793_in(T61, T65) :|: TRUE f793_out(x, x1) -> f791_out(x, x1) :|: TRUE f789_out -> f786_out(x2) :|: TRUE f788_out -> f786_out(0) :|: TRUE f786_in(x3) -> f789_in :|: TRUE f786_in(0) -> f788_in :|: TRUE f795_in(x4, x5) -> f799_in :|: TRUE f795_in(s(x6), x7) -> f798_in(x7, x6) :|: TRUE f799_out -> f795_out(x8, x9) :|: TRUE f798_out(x10, x11) -> f795_out(s(x11), x10) :|: TRUE f775_out(T55) -> f774_out(0, s(T55)) :|: TRUE f776_out(T47, T51) -> f774_out(T47, T51) :|: TRUE f774_in(x12, x13) -> f776_in(x12, x13) :|: TRUE f774_in(0, s(x14)) -> f775_in(x14) :|: TRUE f786_out(x15) -> f785_out(x15) :|: TRUE f787_out(x16) -> f785_out(x16) :|: TRUE f785_in(x17) -> f786_in(x17) :|: TRUE f785_in(x18) -> f787_in(x18) :|: TRUE f773_out(x19, 0) -> f796_out(x19) :|: TRUE f796_in(x20) -> f773_in(x20, 0) :|: TRUE f776_in(x21, x22) -> f779_in(x21, x22) :|: TRUE f779_out(x23, x24) -> f776_out(x23, x24) :|: TRUE f781_out(x25, x26) -> f780_out(x25, x26) :|: TRUE f782_out(x27, x28) -> f780_out(x27, x28) :|: TRUE f780_in(x29, x30) -> f781_in(x29, x30) :|: TRUE f780_in(x31, x32) -> f782_in(x31, x32) :|: TRUE f788_in -> f773_in(0, 0) :|: TRUE f773_out(0, 0) -> f788_out :|: TRUE f783_in(x33) -> f785_in(x33) :|: TRUE f785_out(x34) -> f783_out(x34) :|: TRUE f791_out(x35, x36) -> f782_out(s(x36), x35) :|: TRUE f782_in(s(x37), x38) -> f791_in(x38, x37) :|: TRUE f782_in(x39, x40) -> f792_in :|: TRUE f792_out -> f782_out(x41, x42) :|: TRUE f796_out(x43) -> f794_out(0, x43) :|: TRUE f794_in(0, x44) -> f796_in(x44) :|: TRUE f797_out -> f794_out(x45, x46) :|: TRUE f794_in(x47, x48) -> f797_in :|: TRUE f781_in(0, x49) -> f783_in(x49) :|: TRUE f784_out -> f781_out(x50, x51) :|: TRUE f783_out(x52) -> f781_out(0, x52) :|: TRUE f781_in(x53, x54) -> f784_in :|: TRUE f793_in(x55, x56) -> f795_in(x55, x56) :|: TRUE f795_out(x57, x58) -> f793_out(x57, x58) :|: TRUE f794_out(x59, x60) -> f793_out(x59, x60) :|: TRUE f793_in(x61, x62) -> f794_in(x61, x62) :|: TRUE f773_in(x63, x64) -> f774_in(x63, x64) :|: TRUE f774_out(x65, x66) -> f773_out(x65, x66) :|: TRUE f780_out(x67, x68) -> f779_out(x67, x68) :|: TRUE f779_in(x69, x70) -> f780_in(x69, x70) :|: TRUE f798_in(x71, x72) -> f773_in(x71, x72) :|: TRUE f773_out(x73, x74) -> f798_out(x73, x74) :|: TRUE f6_out(T1) -> f3_out(T1) :|: TRUE f3_in(x75) -> f6_in(x75) :|: TRUE f6_in(x76) -> f77_in(x76) :|: TRUE f76_out -> f6_out([]) :|: TRUE f6_in([]) -> f76_in :|: TRUE f77_out(x77) -> f6_out(x77) :|: TRUE f77_in(.(T4, [])) -> f80_in(T4) :|: TRUE f81_out(x78) -> f77_out(x78) :|: TRUE f80_out(x79) -> f77_out(.(x79, [])) :|: TRUE f77_in(x80) -> f81_in(x80) :|: TRUE f81_in(T7) -> f88_in(T7) :|: TRUE f88_out(x81) -> f81_out(x81) :|: TRUE f88_in(x82) -> f90_in(x82) :|: TRUE f90_out(x83) -> f88_out(x83) :|: TRUE f91_out(x84) -> f90_out(x84) :|: TRUE f90_in(x85) -> f91_in(x85) :|: TRUE f91_in(.(T12, T13)) -> f110_in(T12, T13) :|: TRUE f111_out -> f91_out(x86) :|: TRUE f91_in(x87) -> f111_in :|: TRUE f110_out(x88, x89) -> f91_out(.(x88, x89)) :|: TRUE f112_out(x90, x91) -> f110_out(x90, x91) :|: TRUE f110_in(x92, x93) -> f112_in(x92, x93) :|: TRUE f113_out(x94, x95) -> f112_out(x94, x95) :|: TRUE f112_in(x96, x97) -> f113_in(x96, x97) :|: TRUE f113_in(T18, T19) -> f116_in(T19, T18) :|: TRUE f116_out(x98, x99) -> f113_out(x99, x98) :|: TRUE f116_in(x100, x101) -> f117_in(x100, x101) :|: TRUE f117_out(x102, x103) -> f116_out(x102, x103) :|: TRUE f117_in(x104, x105) -> f120_in(x104, x105) :|: TRUE f120_out(x106, x107) -> f117_out(x106, x107) :|: TRUE f127_out(x108, x109, x110) -> f120_out(.(x108, x109), x110) :|: TRUE f128_out -> f120_out(x111, x112) :|: TRUE f120_in(.(x113, x114), x115) -> f127_in(x113, x114, x115) :|: TRUE f120_in(x116, x117) -> f128_in :|: TRUE f127_in(x118, x119, x120) -> f129_in(x118, x119, x120) :|: TRUE f129_out(x121, x122, x123) -> f127_out(x121, x122, x123) :|: TRUE f129_in(x124, x125, x126) -> f130_in(x124, x125, x126) :|: TRUE f130_out(x127, x128, x129) -> f129_out(x127, x128, x129) :|: TRUE f133_out(x130, x131, x132) -> f130_out(x131, x132, x130) :|: TRUE f130_in(x133, x134, x135) -> f133_in(x135, x133, x134) :|: TRUE f138_out(x136, x137) -> f139_in(x137, x138) :|: TRUE f139_out(x139, x140) -> f133_out(x141, x139, x140) :|: TRUE f133_in(x142, x143, x144) -> f138_in(x142, x143) :|: TRUE f439_out(x145, x146) -> f138_out(x145, x146) :|: TRUE f138_in(x147, x148) -> f439_in(x147, x148) :|: TRUE f439_in(x149, x150) -> f442_in(x149, x150) :|: TRUE f439_in(0, T38) -> f441_in(T38) :|: TRUE f441_out(x151) -> f439_out(0, x151) :|: TRUE f442_out(x152, x153) -> f439_out(x152, x153) :|: TRUE f442_in(T43, T44) -> f766_in(T43, T44) :|: TRUE f766_out(x154, x155) -> f442_out(x154, x155) :|: TRUE f767_out(x156, x157) -> f766_out(x156, x157) :|: TRUE f766_in(x158, x159) -> f767_in(x158, x159) :|: TRUE f768_out(x160, x161) -> f767_out(x160, x161) :|: TRUE f767_in(x162, x163) -> f768_in(x162, x163) :|: TRUE f768_in(s(x164), x165) -> f769_in(x165, x164) :|: TRUE f768_in(x166, x167) -> f770_in :|: TRUE f769_out(x168, x169) -> f768_out(s(x169), x168) :|: TRUE f770_out -> f768_out(x170, x171) :|: TRUE f771_out(x172, x173) -> f769_out(x172, x173) :|: TRUE f769_in(x174, x175) -> f771_in(x174, x175) :|: TRUE f771_in(x176, x177) -> f772_in(x176, x177) :|: TRUE f772_out(x178, x179) -> f771_out(x178, x179) :|: TRUE f772_in(x180, x181) -> f773_in(x181, x180) :|: TRUE f773_out(x182, x183) -> f772_out(x183, x182) :|: TRUE Start term: f3_in(T1) ---------------------------------------- (102) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f791_in(T61, T65) -> f793_in(T61, T65) :|: TRUE f786_in(0) -> f788_in :|: TRUE f795_in(s(x6), x7) -> f798_in(x7, x6) :|: TRUE f774_in(x12, x13) -> f776_in(x12, x13) :|: TRUE f785_in(x17) -> f786_in(x17) :|: TRUE f796_in(x20) -> f773_in(x20, 0) :|: TRUE f776_in(x21, x22) -> f779_in(x21, x22) :|: TRUE f780_in(x29, x30) -> f781_in(x29, x30) :|: TRUE f780_in(x31, x32) -> f782_in(x31, x32) :|: TRUE f788_in -> f773_in(0, 0) :|: TRUE f783_in(x33) -> f785_in(x33) :|: TRUE f782_in(s(x37), x38) -> f791_in(x38, x37) :|: TRUE f794_in(0, x44) -> f796_in(x44) :|: TRUE f781_in(0, x49) -> f783_in(x49) :|: TRUE f793_in(x55, x56) -> f795_in(x55, x56) :|: TRUE f793_in(x61, x62) -> f794_in(x61, x62) :|: TRUE f773_in(x63, x64) -> f774_in(x63, x64) :|: TRUE f779_in(x69, x70) -> f780_in(x69, x70) :|: TRUE f798_in(x71, x72) -> f773_in(x71, x72) :|: TRUE ---------------------------------------- (103) Obligation: Rules: f791_in(T61, T65) -> f793_in(T61, T65) :|: TRUE f786_in(0) -> f788_in :|: TRUE f795_in(s(x6), x7) -> f798_in(x7, x6) :|: TRUE f774_in(x12, x13) -> f776_in(x12, x13) :|: TRUE f785_in(x17) -> f786_in(x17) :|: TRUE f796_in(x20) -> f773_in(x20, 0) :|: TRUE f776_in(x21, x22) -> f779_in(x21, x22) :|: TRUE f780_in(x29, x30) -> f781_in(x29, x30) :|: TRUE f780_in(x31, x32) -> f782_in(x31, x32) :|: TRUE f788_in -> f773_in(0, 0) :|: TRUE f783_in(x33) -> f785_in(x33) :|: TRUE f782_in(s(x37), x38) -> f791_in(x38, x37) :|: TRUE f794_in(0, x44) -> f796_in(x44) :|: TRUE f781_in(0, x49) -> f783_in(x49) :|: TRUE f793_in(x55, x56) -> f795_in(x55, x56) :|: TRUE f793_in(x61, x62) -> f794_in(x61, x62) :|: TRUE f773_in(x63, x64) -> f774_in(x63, x64) :|: TRUE f779_in(x69, x70) -> f780_in(x69, x70) :|: TRUE f798_in(x71, x72) -> f773_in(x71, x72) :|: TRUE ---------------------------------------- (104) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (105) Obligation: Rules: f780_in(s(x37:0), cons_0) -> f780_in(x37:0, 0) :|: TRUE && cons_0 = 0 f780_in(x, x1) -> f780_in(0, 0) :|: TRUE && x = 0 && x1 = 0 f780_in(s(x2), s(x3)) -> f780_in(x2, x3) :|: TRUE ---------------------------------------- (106) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (107) Obligation: Rules: f780_in(s(x37:0), cons_0) -> f780_in(x37:0, 0) :|: TRUE && cons_0 = 0 f780_in(x, x1) -> f780_in(0, 0) :|: TRUE && x = 0 && x1 = 0 f780_in(s(x2), s(x3)) -> f780_in(x2, x3) :|: TRUE ---------------------------------------- (108) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f780_in(s(x37:0), cons_0) -> f780_in(x37:0, 0) :|: TRUE && cons_0 = 0 (2) f780_in(x, x1) -> f780_in(0, 0) :|: TRUE && x = 0 && x1 = 0 (3) f780_in(s(x2), s(x3)) -> f780_in(x2, x3) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (2) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (109) Complex Obligation (AND) ---------------------------------------- (110) Obligation: Termination digraph: Nodes: (1) f780_in(s(x2), s(x3)) -> f780_in(x2, x3) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (111) Obligation: Termination digraph: Nodes: (1) f780_in(s(x37:0), cons_0) -> f780_in(x37:0, 0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (112) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (113) Obligation: Rules: f780_in(s(x37:0:0), cons_0) -> f780_in(x37:0:0, 0) :|: TRUE && cons_0 = 0 ---------------------------------------- (114) Obligation: Termination digraph: Nodes: (1) f780_in(x, x1) -> f780_in(0, 0) :|: TRUE && x = 0 && x1 = 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (115) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (116) Obligation: Rules: f780_in(cons_0, cons_01) -> f780_in(0, 0) :|: TRUE && cons_0 = 0 && cons_01 = 0 ---------------------------------------- (117) Obligation: Rules: f139_in(T32, T33) -> f3_in(.(T32, T33)) :|: TRUE f3_out(.(x, x1)) -> f139_out(x, x1) :|: TRUE f439_out(x2, x3) -> f138_out(x2, x3) :|: TRUE f138_in(x4, x5) -> f439_in(x4, x5) :|: TRUE f443_out -> f441_out(T38) :|: TRUE f441_in(x6) -> f443_in :|: TRUE f781_out(T60, T61) -> f780_out(T60, T61) :|: TRUE f782_out(x7, x8) -> f780_out(x7, x8) :|: TRUE f780_in(x9, x10) -> f781_in(x9, x10) :|: TRUE f780_in(x11, x12) -> f782_in(x11, x12) :|: TRUE f77_in(.(T4, [])) -> f80_in(T4) :|: TRUE f81_out(T1) -> f77_out(T1) :|: TRUE f80_out(x13) -> f77_out(.(x13, [])) :|: TRUE f77_in(x14) -> f81_in(x14) :|: TRUE f6_in(x15) -> f77_in(x15) :|: TRUE f76_out -> f6_out([]) :|: TRUE f6_in([]) -> f76_in :|: TRUE f77_out(x16) -> f6_out(x16) :|: TRUE f791_out(x17, x18) -> f782_out(s(x18), x17) :|: TRUE f782_in(s(x19), x20) -> f791_in(x20, x19) :|: TRUE f782_in(x21, x22) -> f792_in :|: TRUE f792_out -> f782_out(x23, x24) :|: TRUE f781_in(0, x25) -> f783_in(x25) :|: TRUE f784_out -> f781_out(x26, x27) :|: TRUE f783_out(x28) -> f781_out(0, x28) :|: TRUE f781_in(x29, x30) -> f784_in :|: TRUE f133_out(x31, x32, x33) -> f130_out(x32, x33, x31) :|: TRUE f130_in(x34, x35, x36) -> f133_in(x36, x34, x35) :|: TRUE f138_out(x37, x38) -> f139_in(x38, x39) :|: TRUE f139_out(x40, x41) -> f133_out(x42, x40, x41) :|: TRUE f133_in(x43, x44, x45) -> f138_in(x43, x44) :|: TRUE f773_in(T47, T51) -> f774_in(T47, T51) :|: TRUE f774_out(x46, x47) -> f773_out(x46, x47) :|: TRUE f772_in(x48, x49) -> f773_in(x49, x48) :|: TRUE f773_out(x50, x51) -> f772_out(x51, x50) :|: TRUE f439_in(x52, x53) -> f442_in(x52, x53) :|: TRUE f439_in(0, x54) -> f441_in(x54) :|: TRUE f441_out(x55) -> f439_out(0, x55) :|: TRUE f442_out(x56, x57) -> f439_out(x56, x57) :|: TRUE f789_out -> f786_out(x58) :|: TRUE f788_out -> f786_out(0) :|: TRUE f786_in(x59) -> f789_in :|: TRUE f786_in(0) -> f788_in :|: TRUE f91_out(T7) -> f90_out(T7) :|: TRUE f90_in(x60) -> f91_in(x60) :|: TRUE f795_in(x61, x62) -> f799_in :|: TRUE f795_in(s(T68), T65) -> f798_in(T65, T68) :|: TRUE f799_out -> f795_out(x63, x64) :|: TRUE f798_out(x65, x66) -> f795_out(s(x66), x65) :|: TRUE f787_in(x67) -> f790_in :|: TRUE f790_out -> f787_out(x68) :|: TRUE f775_out(T55) -> f774_out(0, s(T55)) :|: TRUE f776_out(x69, x70) -> f774_out(x69, x70) :|: TRUE f774_in(x71, x72) -> f776_in(x71, x72) :|: TRUE f774_in(0, s(x73)) -> f775_in(x73) :|: TRUE f786_out(x74) -> f785_out(x74) :|: TRUE f787_out(x75) -> f785_out(x75) :|: TRUE f785_in(x76) -> f786_in(x76) :|: TRUE f785_in(x77) -> f787_in(x77) :|: TRUE f768_out(T43, T44) -> f767_out(T43, T44) :|: TRUE f767_in(x78, x79) -> f768_in(x78, x79) :|: TRUE f6_out(x80) -> f3_out(x80) :|: TRUE f3_in(x81) -> f6_in(x81) :|: TRUE f768_in(s(x82), x83) -> f769_in(x83, x82) :|: TRUE f768_in(x84, x85) -> f770_in :|: TRUE f769_out(x86, x87) -> f768_out(s(x87), x86) :|: TRUE f770_out -> f768_out(x88, x89) :|: TRUE f771_out(x90, x91) -> f769_out(x90, x91) :|: TRUE f769_in(x92, x93) -> f771_in(x92, x93) :|: TRUE f777_out -> f775_out(x94) :|: TRUE f775_in(x95) -> f777_in :|: TRUE f113_in(T18, T19) -> f116_in(T19, T18) :|: TRUE f116_out(x96, x97) -> f113_out(x97, x96) :|: TRUE f112_out(T12, T13) -> f110_out(T12, T13) :|: TRUE f110_in(x98, x99) -> f112_in(x98, x99) :|: TRUE f443_in -> f443_out :|: TRUE f798_in(x100, x101) -> f773_in(x100, x101) :|: TRUE f773_out(x102, x103) -> f798_out(x102, x103) :|: TRUE f88_in(x104) -> f90_in(x104) :|: TRUE f90_out(x105) -> f88_out(x105) :|: TRUE f129_in(x106, x107, x108) -> f130_in(x106, x107, x108) :|: TRUE f130_out(x109, x110, x111) -> f129_out(x109, x110, x111) :|: TRUE f117_in(x112, x113) -> f120_in(x112, x113) :|: TRUE f120_out(x114, x115) -> f117_out(x114, x115) :|: TRUE f91_in(.(x116, x117)) -> f110_in(x116, x117) :|: TRUE f111_out -> f91_out(x118) :|: TRUE f91_in(x119) -> f111_in :|: TRUE f110_out(x120, x121) -> f91_out(.(x120, x121)) :|: TRUE f113_out(x122, x123) -> f112_out(x122, x123) :|: TRUE f112_in(x124, x125) -> f113_in(x124, x125) :|: TRUE f788_in -> f773_in(0, 0) :|: TRUE f773_out(0, 0) -> f788_out :|: TRUE f783_in(x126) -> f785_in(x126) :|: TRUE f785_out(x127) -> f783_out(x127) :|: TRUE f777_in -> f777_out :|: TRUE f771_in(x128, x129) -> f772_in(x128, x129) :|: TRUE f772_out(x130, x131) -> f771_out(x130, x131) :|: TRUE f442_in(x132, x133) -> f766_in(x132, x133) :|: TRUE f766_out(x134, x135) -> f442_out(x134, x135) :|: TRUE f767_out(x136, x137) -> f766_out(x136, x137) :|: TRUE f766_in(x138, x139) -> f767_in(x138, x139) :|: TRUE f780_out(x140, x141) -> f779_out(x140, x141) :|: TRUE f779_in(x142, x143) -> f780_in(x142, x143) :|: TRUE f791_in(x144, x145) -> f793_in(x144, x145) :|: TRUE f793_out(x146, x147) -> f791_out(x146, x147) :|: TRUE f127_out(x148, x149, x150) -> f120_out(.(x148, x149), x150) :|: TRUE f128_out -> f120_out(x151, x152) :|: TRUE f120_in(.(x153, x154), x155) -> f127_in(x153, x154, x155) :|: TRUE f120_in(x156, x157) -> f128_in :|: TRUE f773_out(x158, 0) -> f796_out(x158) :|: TRUE f796_in(x159) -> f773_in(x159, 0) :|: TRUE f776_in(x160, x161) -> f779_in(x160, x161) :|: TRUE f779_out(x162, x163) -> f776_out(x162, x163) :|: TRUE f81_in(x164) -> f88_in(x164) :|: TRUE f88_out(x165) -> f81_out(x165) :|: TRUE f796_out(x166) -> f794_out(0, x166) :|: TRUE f794_in(0, x167) -> f796_in(x167) :|: TRUE f797_out -> f794_out(x168, x169) :|: TRUE f794_in(x170, x171) -> f797_in :|: TRUE f116_in(x172, x173) -> f117_in(x172, x173) :|: TRUE f117_out(x174, x175) -> f116_out(x174, x175) :|: TRUE f793_in(x176, x177) -> f795_in(x176, x177) :|: TRUE f795_out(x178, x179) -> f793_out(x178, x179) :|: TRUE f794_out(x180, x181) -> f793_out(x180, x181) :|: TRUE f793_in(x182, x183) -> f794_in(x182, x183) :|: TRUE f127_in(x184, x185, x186) -> f129_in(x184, x185, x186) :|: TRUE f129_out(x187, x188, x189) -> f127_out(x187, x188, x189) :|: TRUE Start term: f3_in(T1)