/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern perm(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 3 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) NonTerminationLoopProof [COMPLETE, 0 ms] (20) NO (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PrologToPiTRSProof [SOUND, 0 ms] (29) PiTRS (30) DependencyPairsProof [EQUIVALENT, 0 ms] (31) PiDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) AND (34) PiDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) PiDP (37) PiDPToQDPProof [SOUND, 7 ms] (38) QDP (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] (40) YES (41) PiDP (42) UsableRulesProof [EQUIVALENT, 0 ms] (43) PiDP (44) PiDPToQDPProof [SOUND, 0 ms] (45) QDP (46) NonTerminationLoopProof [COMPLETE, 0 ms] (47) NO (48) PiDP (49) UsableRulesProof [EQUIVALENT, 0 ms] (50) PiDP (51) PiDPToQDPProof [SOUND, 0 ms] (52) QDP (53) QDPSizeChangeProof [EQUIVALENT, 0 ms] (54) YES (55) PrologToDTProblemTransformerProof [SOUND, 0 ms] (56) TRIPLES (57) TriplesToPiDPProof [SOUND, 23 ms] (58) PiDP (59) DependencyGraphProof [EQUIVALENT, 0 ms] (60) AND (61) PiDP (62) UsableRulesProof [EQUIVALENT, 0 ms] (63) PiDP (64) PiDPToQDPProof [SOUND, 0 ms] (65) QDP (66) QDPSizeChangeProof [EQUIVALENT, 0 ms] (67) YES (68) PiDP (69) UsableRulesProof [EQUIVALENT, 0 ms] (70) PiDP (71) PiDPToQDPProof [SOUND, 0 ms] (72) QDP (73) NonTerminationLoopProof [COMPLETE, 0 ms] (74) NO (75) PiDP (76) PiDPToQDPProof [SOUND, 0 ms] (77) QDP (78) QDPSizeChangeProof [EQUIVALENT, 0 ms] (79) YES (80) PrologToTRSTransformerProof [SOUND, 24 ms] (81) QTRS (82) DependencyPairsProof [EQUIVALENT, 0 ms] (83) QDP (84) DependencyGraphProof [EQUIVALENT, 0 ms] (85) AND (86) QDP (87) MNOCProof [EQUIVALENT, 0 ms] (88) QDP (89) UsableRulesProof [EQUIVALENT, 0 ms] (90) QDP (91) QReductionProof [EQUIVALENT, 0 ms] (92) QDP (93) NonTerminationLoopProof [COMPLETE, 0 ms] (94) NO (95) QDP (96) MNOCProof [EQUIVALENT, 0 ms] (97) QDP (98) UsableRulesProof [EQUIVALENT, 0 ms] (99) QDP (100) QReductionProof [EQUIVALENT, 0 ms] (101) QDP (102) NonTerminationLoopProof [COMPLETE, 0 ms] (103) NO (104) QDP (105) MNOCProof [EQUIVALENT, 0 ms] (106) QDP (107) UsableRulesProof [EQUIVALENT, 0 ms] (108) QDP (109) QReductionProof [EQUIVALENT, 0 ms] (110) QDP (111) QDPSizeChangeProof [EQUIVALENT, 0 ms] (112) YES (113) PrologToIRSwTTransformerProof [SOUND, 36 ms] (114) AND (115) IRSwT (116) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (117) TRUE (118) IRSwT (119) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (120) IRSwT (121) IntTRSCompressionProof [EQUIVALENT, 20 ms] (122) IRSwT (123) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (124) IRSwT (125) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (126) IRSwT (127) FilterProof [EQUIVALENT, 0 ms] (128) IntTRS (129) IntTRSPeriodicNontermProof [COMPLETE, 5 ms] (130) NO (131) IRSwT (132) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (133) IRSwT ---------------------------------------- (0) Obligation: Clauses: perm([], []). perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys))). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: perm(a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: perm_in_2: (f,b) app_in_3: (f,f,f) (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) ---------------------------------------- (3) 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: PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x2, x5) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x2, x5) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 5 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 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: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_AAA -> APP_IN_AAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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 = APP_IN_AAA evaluates to t =APP_IN_AAA 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 APP_IN_AAA to APP_IN_AAA. ---------------------------------------- (20) NO ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag(x2) .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) U3_ag(x1, x2, x3, x4) = U3_ag(x3, x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x2) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x2, x5) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s)) U2_AG(Ys, app_out_gaa(X1s)) -> PERM_IN_AG(Ys) PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa) The TRS R consists of the following rules: app_in_gaa([]) -> app_out_gaa([]) app_in_gaa(.(Xs)) -> U4_gaa(Xs, app_in_gaa(Xs)) app_in_aaa -> app_out_aaa([]) app_in_aaa -> U4_aaa(app_in_aaa) U4_gaa(Xs, app_out_gaa(Xs)) -> app_out_gaa(.(Xs)) U4_aaa(app_out_aaa(Xs)) -> app_out_aaa(.(Xs)) The set Q consists of the following terms: app_in_gaa(x0) app_in_aaa U4_gaa(x0, x1) U4_aaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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: *U2_AG(Ys, app_out_gaa(X1s)) -> PERM_IN_AG(Ys) The graph contains the following edges 1 >= 1 *PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa) The graph contains the following edges 1 > 1 *U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s)) The graph contains the following edges 1 >= 1 ---------------------------------------- (27) YES ---------------------------------------- (28) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: perm_in_2: (f,b) app_in_3: (f,f,f) (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (29) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) ---------------------------------------- (30) 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: PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x5) U3_AG(x1, x2, x3, x4) = U3_AG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) Obligation: Pi DP problem: The TRS P consists of the following rules: PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U4_AAA(x1, x2, x3, x4, x5) = U4_AAA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x5) U3_AG(x1, x2, x3, x4) = U3_AG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 5 less nodes. ---------------------------------------- (33) Complex Obligation (AND) ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (37) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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: *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) The graph contains the following edges 1 > 1 ---------------------------------------- (40) YES ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (43) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (44) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_AAA -> APP_IN_AAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (46) 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 = APP_IN_AAA evaluates to t =APP_IN_AAA 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 APP_IN_AAA to APP_IN_AAA. ---------------------------------------- (47) NO ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: perm_in_ag([], []) -> perm_out_ag([], []) perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys)) U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys)) The argument filtering Pi contains the following mapping: perm_in_ag(x1, x2) = perm_in_ag(x2) [] = [] perm_out_ag(x1, x2) = perm_out_ag .(x1, x2) = .(x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) U3_ag(x1, x2, x3, x4) = U3_ag(x4) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (50) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs)) U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys) PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x2) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U4_aaa(x1, x2, x3, x4, x5) = U4_aaa(x5) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) app_out_gaa(x1, x2, x3) = app_out_gaa U4_gaa(x1, x2, x3, x4, x5) = U4_gaa(x5) PERM_IN_AG(x1, x2) = PERM_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s)) U2_AG(Ys, app_out_gaa) -> PERM_IN_AG(Ys) PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa) The TRS R consists of the following rules: app_in_gaa([]) -> app_out_gaa app_in_gaa(.(Xs)) -> U4_gaa(app_in_gaa(Xs)) app_in_aaa -> app_out_aaa([]) app_in_aaa -> U4_aaa(app_in_aaa) U4_gaa(app_out_gaa) -> app_out_gaa U4_aaa(app_out_aaa(Xs)) -> app_out_aaa(.(Xs)) The set Q consists of the following terms: app_in_gaa(x0) app_in_aaa U4_gaa(x0) U4_aaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (53) 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: *U2_AG(Ys, app_out_gaa) -> PERM_IN_AG(Ys) The graph contains the following edges 1 >= 1 *PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa) The graph contains the following edges 1 > 1 *U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s)) The graph contains the following edges 1 >= 1 ---------------------------------------- (54) YES ---------------------------------------- (55) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(perm ([]) ([]))", null ], [ "(perm Xs (. X Ys))", "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "66": { "goal": [{ "clause": 3, "scope": 3, "term": "(app ([]) T21 X12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "67": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "69": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(perm T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "193": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X53 (. T36 X54) T39) (',' (app (. T40 X53) X54 X12) (perm X12 T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T36" ], "free": [ "X12", "X53", "X54" ], "exprvars": [] } }, "type": "Nodes", "250": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "251": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T108 T109 X141)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X141"], "exprvars": [] } }, "230": { "goal": [ { "clause": 2, "scope": 4, "term": "(app X53 (. T36 X54) T39)" }, { "clause": 3, "scope": 4, "term": "(app X53 (. T36 X54) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [ "X53", "X54" ], "exprvars": [] } }, "252": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": 2, "scope": 4, "term": "(app X53 (. T36 X54) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [ "X53", "X54" ], "exprvars": [] } }, "232": { "goal": [{ "clause": 3, "scope": 4, "term": "(app X53 (. T36 X54) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [ "X53", "X54" ], "exprvars": [] } }, "233": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "235": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X92 (. T68 X93) T71)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T68"], "free": [ "X92", "X93" ], "exprvars": [] } }, "237": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": -1, "scope": -1, "term": "(app (. T47 T45) T46 X12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T76 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [[ "(perm T1 T2)", "(perm ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))" }, { "clause": 3, "scope": 2, "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "58": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "59": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "242": { "goal": [ { "clause": 2, "scope": 5, "term": "(app (. T47 T45) T46 X12)" }, { "clause": 3, "scope": 5, "term": "(app (. T47 T45) T46 X12)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "243": { "goal": [{ "clause": 3, "scope": 5, "term": "(app (. T47 T45) T46 X12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "244": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T90 T91 X119)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X119"], "exprvars": [] } }, "245": { "goal": [ { "clause": 2, "scope": 6, "term": "(app T90 T91 X119)" }, { "clause": 3, "scope": 6, "term": "(app T90 T91 X119)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X119"], "exprvars": [] } }, "246": { "goal": [{ "clause": 2, "scope": 6, "term": "(app T90 T91 X119)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X119"], "exprvars": [] } }, "225": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X53 (. T36 X54) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [ "X53", "X54" ], "exprvars": [] } }, "247": { "goal": [{ "clause": 3, "scope": 6, "term": "(app T90 T91 X119)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X119"], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app (. T47 T45) T46 X12) (perm X12 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X12"], "exprvars": [] } }, "248": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "249": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": 0, "scope": 1, "term": "(perm T1 T2)" }, { "clause": 1, "scope": 1, "term": "(perm T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app ([]) T21 X12) (perm X12 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X12"], "exprvars": [] } }, "61": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) T21 X12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T23 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } }, "64": { "goal": [ { "clause": 2, "scope": 3, "term": "(app ([]) T21 X12)" }, { "clause": 3, "scope": 3, "term": "(app ([]) T21 X12)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } }, "65": { "goal": [{ "clause": 2, "scope": 3, "term": "(app ([]) T21 X12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X12"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 8, "label": "CASE" }, { "from": 8, "to": 49, "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 8, "to": 50, "label": "EVAL-BACKTRACK" }, { "from": 49, "to": 51, "label": "SUCCESS" }, { "from": 50, "to": 54, "label": "EVAL with clause\nperm(X7, .(X8, X9)) :- ','(app(X10, .(X8, X11), X7), ','(app(X10, X11, X12), perm(X12, X9))).\nand substitutionT1 -> T10,\nX7 -> T10,\nX8 -> T8,\nX9 -> T9,\nT2 -> .(T8, T9),\nT7 -> T10" }, { "from": 50, "to": 56, "label": "EVAL-BACKTRACK" }, { "from": 51, "to": 52, "label": "BACKTRACK\nfor clause: perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys)))because of non-unification" }, { "from": 54, "to": 57, "label": "CASE" }, { "from": 57, "to": 58, "label": "PARALLEL" }, { "from": 57, "to": 59, "label": "PARALLEL" }, { "from": 58, "to": 60, "label": "EVAL with clause\napp([], X21, X21).\nand substitutionX10 -> [],\nT8 -> T19,\nX11 -> T21,\nX21 -> .(T19, T21),\nX22 -> T21,\nT10 -> .(T19, T21),\nT20 -> T21" }, { "from": 58, "to": 61, "label": "EVAL-BACKTRACK" }, { "from": 59, "to": 193, "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX10 -> .(T40, X53),\nT8 -> T36,\nX11 -> X54,\nX50 -> .(T36, X54),\nX52 -> T40,\nX51 -> T39,\nT10 -> .(T40, T39),\nT38 -> T39,\nT37 -> T40" }, { "from": 59, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 60, "to": 62, "label": "SPLIT 1" }, { "from": 60, "to": 63, "label": "SPLIT 2\nreplacements:X12 -> T23" }, { "from": 62, "to": 64, "label": "CASE" }, { "from": 63, "to": 1, "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T9" }, { "from": 64, "to": 65, "label": "PARALLEL" }, { "from": 64, "to": 66, "label": "PARALLEL" }, { "from": 65, "to": 67, "label": "ONLY EVAL with clause\napp([], X29, X29).\nand substitutionT21 -> T29,\nX29 -> T29,\nX12 -> T29" }, { "from": 66, "to": 69, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 67, "to": 68, "label": "SUCCESS" }, { "from": 193, "to": 225, "label": "SPLIT 1" }, { "from": 193, "to": 226, "label": "SPLIT 2\nreplacements:X53 -> T45,\nX54 -> T46,\nT40 -> T47" }, { "from": 225, "to": 230, "label": "CASE" }, { "from": 226, "to": 238, "label": "SPLIT 1" }, { "from": 226, "to": 239, "label": "SPLIT 2\nreplacements:X12 -> T76" }, { "from": 230, "to": 231, "label": "PARALLEL" }, { "from": 230, "to": 232, "label": "PARALLEL" }, { "from": 231, "to": 233, "label": "EVAL with clause\napp([], X71, X71).\nand substitutionX53 -> [],\nT36 -> T60,\nX54 -> T61,\nX71 -> .(T60, T61),\nX72 -> T61,\nT39 -> .(T60, T61)" }, { "from": 231, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 232, "to": 236, "label": "EVAL with clause\napp(.(X87, X88), X89, .(X87, X90)) :- app(X88, X89, X90).\nand substitutionX87 -> T69,\nX88 -> X92,\nX53 -> .(T69, X92),\nT36 -> T68,\nX54 -> X93,\nX89 -> .(T68, X93),\nX91 -> T69,\nX90 -> T71,\nT39 -> .(T69, T71),\nT70 -> T71" }, { "from": 232, "to": 237, "label": "EVAL-BACKTRACK" }, { "from": 233, "to": 235, "label": "SUCCESS" }, { "from": 236, "to": 225, "label": "INSTANCE with matching:\nX53 -> X92\nT36 -> T68\nX54 -> X93\nT39 -> T71" }, { "from": 238, "to": 242, "label": "CASE" }, { "from": 239, "to": 1, "label": "INSTANCE with matching:\nT1 -> T76\nT2 -> T9" }, { "from": 242, "to": 243, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 243, "to": 244, "label": "ONLY EVAL with clause\napp(.(X115, X116), X117, .(X115, X118)) :- app(X116, X117, X118).\nand substitutionT47 -> T87,\nX115 -> T87,\nT45 -> T90,\nX116 -> T90,\nT46 -> T91,\nX117 -> T91,\nX118 -> X119,\nX12 -> .(T87, X119),\nT88 -> T90,\nT89 -> T91" }, { "from": 244, "to": 245, "label": "CASE" }, { "from": 245, "to": 246, "label": "PARALLEL" }, { "from": 245, "to": 247, "label": "PARALLEL" }, { "from": 246, "to": 248, "label": "EVAL with clause\napp([], X126, X126).\nand substitutionT90 -> [],\nT91 -> T98,\nX126 -> T98,\nX119 -> T98" }, { "from": 246, "to": 249, "label": "EVAL-BACKTRACK" }, { "from": 247, "to": 251, "label": "EVAL with clause\napp(.(X137, X138), X139, .(X137, X140)) :- app(X138, X139, X140).\nand substitutionX137 -> T105,\nX138 -> T108,\nT90 -> .(T105, T108),\nT91 -> T109,\nX139 -> T109,\nX140 -> X141,\nX119 -> .(T105, X141),\nT106 -> T108,\nT107 -> T109" }, { "from": 247, "to": 252, "label": "EVAL-BACKTRACK" }, { "from": 248, "to": 250, "label": "SUCCESS" }, { "from": 251, "to": 244, "label": "INSTANCE with matching:\nT90 -> T108\nT91 -> T109\nX119 -> X141" } ], "type": "Graph" } } ---------------------------------------- (56) Obligation: Triples: appC(.(X1, X2), X3, X4, .(X1, X5)) :- appC(X2, X3, X4, X5). appE(.(X1, X2), X3, .(X1, X4)) :- appE(X2, X3, X4). permA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4), permA(X4, X3)). permA(.(X1, X2), .(X3, X4)) :- appC(X5, X3, X6, X2). permA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), appE(X5, X6, X7)). permA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), ','(appcD(X1, X5, X6, X7), permA(X7, X4))). Clauses: permcA([], []). permcA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4), permcA(X4, X3)). permcA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), ','(appcD(X1, X5, X6, X7), permcA(X7, X4))). appcC([], X1, X2, .(X1, X2)). appcC(.(X1, X2), X3, X4, .(X1, X5)) :- appcC(X2, X3, X4, X5). appcE([], X1, X1). appcE(.(X1, X2), X3, .(X1, X4)) :- appcE(X2, X3, X4). appcB(X1, X1). appcD(X1, X2, X3, .(X1, X4)) :- appcE(X2, X3, X4). Afs: permA(x1, x2) = permA(x2) ---------------------------------------- (57) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: permA_in_2: (f,b) appC_in_4: (f,f,f,f) appcC_in_4: (f,f,f,f) appE_in_3: (b,f,f) appcD_in_4: (f,b,f,f) appcE_in_3: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4)) U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> U4_AG(X1, X2, X3, permA_in_ag(X4, X3)) U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U5_AG(X1, X2, X3, X4, appC_in_aaaa(X5, X3, X6, X2)) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> APPC_IN_AAAA(X5, X3, X6, X2) APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AAAA(X1, X2, X3, X4, X5, appC_in_aaaa(X2, X3, X4, X5)) APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2)) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U7_AG(X1, X2, X3, X4, appE_in_gaa(X5, X6, X7)) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> APPE_IN_GAA(X5, X6, X7) APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appE_in_gaa(X2, X3, X4)) APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7)) U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> U9_AG(X1, X2, X3, X4, permA_in_ag(X7, X4)) U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4) The TRS R consists of the following rules: appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1) appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2)) appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5)) U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5)) appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1) appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4)) U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4)) The argument filtering Pi contains the following mapping: permA_in_ag(x1, x2) = permA_in_ag(x2) .(x1, x2) = .(x2) appcB_in_aa(x1, x2) = appcB_in_aa appcB_out_aa(x1, x2) = appcB_out_aa appC_in_aaaa(x1, x2, x3, x4) = appC_in_aaaa appcC_in_aaaa(x1, x2, x3, x4) = appcC_in_aaaa appcC_out_aaaa(x1, x2, x3, x4) = appcC_out_aaaa(x1) U16_aaaa(x1, x2, x3, x4, x5, x6) = U16_aaaa(x6) appE_in_gaa(x1, x2, x3) = appE_in_gaa(x1) appcD_in_agaa(x1, x2, x3, x4) = appcD_in_agaa(x2) U18_agaa(x1, x2, x3, x4, x5) = U18_agaa(x2, x5) appcE_in_gaa(x1, x2, x3) = appcE_in_gaa(x1) [] = [] appcE_out_gaa(x1, x2, x3) = appcE_out_gaa(x1) U17_gaa(x1, x2, x3, x4, x5) = U17_gaa(x2, x5) appcD_out_agaa(x1, x2, x3, x4) = appcD_out_agaa(x2) PERMA_IN_AG(x1, x2) = PERMA_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) U4_AG(x1, x2, x3, x4) = U4_AG(x3, x4) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) APPC_IN_AAAA(x1, x2, x3, x4) = APPC_IN_AAAA U1_AAAA(x1, x2, x3, x4, x5, x6) = U1_AAAA(x6) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x4, x5) APPE_IN_GAA(x1, x2, x3) = APPE_IN_GAA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (58) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4)) U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> U4_AG(X1, X2, X3, permA_in_ag(X4, X3)) U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U5_AG(X1, X2, X3, X4, appC_in_aaaa(X5, X3, X6, X2)) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> APPC_IN_AAAA(X5, X3, X6, X2) APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AAAA(X1, X2, X3, X4, X5, appC_in_aaaa(X2, X3, X4, X5)) APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2)) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U7_AG(X1, X2, X3, X4, appE_in_gaa(X5, X6, X7)) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> APPE_IN_GAA(X5, X6, X7) APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appE_in_gaa(X2, X3, X4)) APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7)) U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> U9_AG(X1, X2, X3, X4, permA_in_ag(X7, X4)) U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4) The TRS R consists of the following rules: appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1) appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2)) appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5)) U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5)) appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1) appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4)) U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4)) The argument filtering Pi contains the following mapping: permA_in_ag(x1, x2) = permA_in_ag(x2) .(x1, x2) = .(x2) appcB_in_aa(x1, x2) = appcB_in_aa appcB_out_aa(x1, x2) = appcB_out_aa appC_in_aaaa(x1, x2, x3, x4) = appC_in_aaaa appcC_in_aaaa(x1, x2, x3, x4) = appcC_in_aaaa appcC_out_aaaa(x1, x2, x3, x4) = appcC_out_aaaa(x1) U16_aaaa(x1, x2, x3, x4, x5, x6) = U16_aaaa(x6) appE_in_gaa(x1, x2, x3) = appE_in_gaa(x1) appcD_in_agaa(x1, x2, x3, x4) = appcD_in_agaa(x2) U18_agaa(x1, x2, x3, x4, x5) = U18_agaa(x2, x5) appcE_in_gaa(x1, x2, x3) = appcE_in_gaa(x1) [] = [] appcE_out_gaa(x1, x2, x3) = appcE_out_gaa(x1) U17_gaa(x1, x2, x3, x4, x5) = U17_gaa(x2, x5) appcD_out_agaa(x1, x2, x3, x4) = appcD_out_agaa(x2) PERMA_IN_AG(x1, x2) = PERMA_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) U4_AG(x1, x2, x3, x4) = U4_AG(x3, x4) U5_AG(x1, x2, x3, x4, x5) = U5_AG(x4, x5) APPC_IN_AAAA(x1, x2, x3, x4) = APPC_IN_AAAA U1_AAAA(x1, x2, x3, x4, x5, x6) = U1_AAAA(x6) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) U7_AG(x1, x2, x3, x4, x5) = U7_AG(x4, x5) APPE_IN_GAA(x1, x2, x3) = APPE_IN_GAA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (59) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 8 less nodes. ---------------------------------------- (60) Complex Obligation (AND) ---------------------------------------- (61) Obligation: Pi DP problem: The TRS P consists of the following rules: APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4) The TRS R consists of the following rules: appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1) appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2)) appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5)) U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5)) appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1) appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4)) U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) appcB_in_aa(x1, x2) = appcB_in_aa appcB_out_aa(x1, x2) = appcB_out_aa appcC_in_aaaa(x1, x2, x3, x4) = appcC_in_aaaa appcC_out_aaaa(x1, x2, x3, x4) = appcC_out_aaaa(x1) U16_aaaa(x1, x2, x3, x4, x5, x6) = U16_aaaa(x6) appcD_in_agaa(x1, x2, x3, x4) = appcD_in_agaa(x2) U18_agaa(x1, x2, x3, x4, x5) = U18_agaa(x2, x5) appcE_in_gaa(x1, x2, x3) = appcE_in_gaa(x1) [] = [] appcE_out_gaa(x1, x2, x3) = appcE_out_gaa(x1) U17_gaa(x1, x2, x3, x4, x5) = U17_gaa(x2, x5) appcD_out_agaa(x1, x2, x3, x4) = appcD_out_agaa(x2) APPE_IN_GAA(x1, x2, x3) = APPE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (62) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (63) Obligation: Pi DP problem: The TRS P consists of the following rules: APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPE_IN_GAA(x1, x2, x3) = APPE_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (64) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: APPE_IN_GAA(.(X2)) -> APPE_IN_GAA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (66) 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: *APPE_IN_GAA(.(X2)) -> APPE_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (67) YES ---------------------------------------- (68) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5) The TRS R consists of the following rules: appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1) appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2)) appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5)) U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5)) appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1) appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4)) U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) appcB_in_aa(x1, x2) = appcB_in_aa appcB_out_aa(x1, x2) = appcB_out_aa appcC_in_aaaa(x1, x2, x3, x4) = appcC_in_aaaa appcC_out_aaaa(x1, x2, x3, x4) = appcC_out_aaaa(x1) U16_aaaa(x1, x2, x3, x4, x5, x6) = U16_aaaa(x6) appcD_in_agaa(x1, x2, x3, x4) = appcD_in_agaa(x2) U18_agaa(x1, x2, x3, x4, x5) = U18_agaa(x2, x5) appcE_in_gaa(x1, x2, x3) = appcE_in_gaa(x1) [] = [] appcE_out_gaa(x1, x2, x3) = appcE_out_gaa(x1) U17_gaa(x1, x2, x3, x4, x5) = U17_gaa(x2, x5) appcD_out_agaa(x1, x2, x3, x4) = appcD_out_agaa(x2) APPC_IN_AAAA(x1, x2, x3, x4) = APPC_IN_AAAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (69) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (70) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPC_IN_AAAA(x1, x2, x3, x4) = APPC_IN_AAAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (71) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: APPC_IN_AAAA -> APPC_IN_AAAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) 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 = APPC_IN_AAAA evaluates to t =APPC_IN_AAAA 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 APPC_IN_AAAA to APPC_IN_AAAA. ---------------------------------------- (74) NO ---------------------------------------- (75) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3) PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4)) PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2)) U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7)) U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4) The TRS R consists of the following rules: appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1) appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2)) appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5)) U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5)) appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1) appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4)) U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4)) U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) appcB_in_aa(x1, x2) = appcB_in_aa appcB_out_aa(x1, x2) = appcB_out_aa appcC_in_aaaa(x1, x2, x3, x4) = appcC_in_aaaa appcC_out_aaaa(x1, x2, x3, x4) = appcC_out_aaaa(x1) U16_aaaa(x1, x2, x3, x4, x5, x6) = U16_aaaa(x6) appcD_in_agaa(x1, x2, x3, x4) = appcD_in_agaa(x2) U18_agaa(x1, x2, x3, x4, x5) = U18_agaa(x2, x5) appcE_in_gaa(x1, x2, x3) = appcE_in_gaa(x1) [] = [] appcE_out_gaa(x1, x2, x3) = appcE_out_gaa(x1) U17_gaa(x1, x2, x3, x4, x5) = U17_gaa(x2, x5) appcD_out_agaa(x1, x2, x3, x4) = appcD_out_agaa(x2) PERMA_IN_AG(x1, x2) = PERMA_IN_AG(x2) U3_AG(x1, x2, x3, x4) = U3_AG(x3, x4) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (76) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AG(X3, appcB_out_aa) -> PERMA_IN_AG(X3) PERMA_IN_AG(.(X3)) -> U3_AG(X3, appcB_in_aa) PERMA_IN_AG(.(X4)) -> U6_AG(X4, appcC_in_aaaa) U6_AG(X4, appcC_out_aaaa(X5)) -> U8_AG(X4, appcD_in_agaa(X5)) U8_AG(X4, appcD_out_agaa(X5)) -> PERMA_IN_AG(X4) The TRS R consists of the following rules: appcB_in_aa -> appcB_out_aa appcC_in_aaaa -> appcC_out_aaaa([]) appcC_in_aaaa -> U16_aaaa(appcC_in_aaaa) U16_aaaa(appcC_out_aaaa(X2)) -> appcC_out_aaaa(.(X2)) appcD_in_agaa(X2) -> U18_agaa(X2, appcE_in_gaa(X2)) appcE_in_gaa([]) -> appcE_out_gaa([]) appcE_in_gaa(.(X2)) -> U17_gaa(X2, appcE_in_gaa(X2)) U17_gaa(X2, appcE_out_gaa(X2)) -> appcE_out_gaa(.(X2)) U18_agaa(X2, appcE_out_gaa(X2)) -> appcD_out_agaa(X2) The set Q consists of the following terms: appcB_in_aa appcC_in_aaaa U16_aaaa(x0) appcD_in_agaa(x0) appcE_in_gaa(x0) U17_gaa(x0, x1) U18_agaa(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (78) 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: *PERMA_IN_AG(.(X3)) -> U3_AG(X3, appcB_in_aa) The graph contains the following edges 1 > 1 *PERMA_IN_AG(.(X4)) -> U6_AG(X4, appcC_in_aaaa) The graph contains the following edges 1 > 1 *U3_AG(X3, appcB_out_aa) -> PERMA_IN_AG(X3) The graph contains the following edges 1 >= 1 *U8_AG(X4, appcD_out_agaa(X5)) -> PERMA_IN_AG(X4) The graph contains the following edges 1 >= 1 *U6_AG(X4, appcC_out_aaaa(X5)) -> U8_AG(X4, appcD_in_agaa(X5)) The graph contains the following edges 1 >= 1 ---------------------------------------- (79) YES ---------------------------------------- (80) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 2, "program": { "directives": [], "clauses": [ [ "(perm ([]) ([]))", null ], [ "(perm Xs (. X Ys))", "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T49 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "30": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X13 (. T10 X14) T12) (',' (app X13 X14 X15) (perm X15 T11)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X13", "X14", "X15" ], "exprvars": [] } }, "31": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 0, "scope": 1, "term": "(perm T1 T2)" }, { "clause": 1, "scope": 1, "term": "(perm T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "76": { "goal": [ { "clause": 2, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }, { "clause": 3, "scope": 2, "term": "(app X13 (. T10 X14) T12)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "77": { "goal": [{ "clause": 2, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "78": { "goal": [{ "clause": 3, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "79": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "240": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T66 T67 X82)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X82"], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "222": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T17 T18 X15)" }, { "clause": 3, "scope": 3, "term": "(app T17 T18 X15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "223": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "224": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "80": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "81": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "82": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X53 (. T39 X54) T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": [ "X53", "X54" ], "exprvars": [] } }, "208": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "83": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T17 T18 X15) (perm X15 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X15"], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 10, "label": "CASE" }, { "from": 10, "to": 13, "label": "PARALLEL" }, { "from": 10, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 24, "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 13, "to": 25, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 30, "label": "EVAL with clause\nperm(X10, .(X11, X12)) :- ','(app(X13, .(X11, X14), X10), ','(app(X13, X14, X15), perm(X15, X12))).\nand substitutionT1 -> T12,\nX10 -> T12,\nX11 -> T10,\nX12 -> T11,\nT2 -> .(T10, T11),\nT9 -> T12" }, { "from": 14, "to": 31, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 27, "label": "SUCCESS" }, { "from": 30, "to": 39, "label": "SPLIT 1" }, { "from": 30, "to": 40, "label": "SPLIT 2\nreplacements:X13 -> T17,\nX14 -> T18" }, { "from": 39, "to": 76, "label": "CASE" }, { "from": 40, "to": 208, "label": "SPLIT 1" }, { "from": 40, "to": 211, "label": "SPLIT 2\nreplacements:X15 -> T49" }, { "from": 76, "to": 77, "label": "PARALLEL" }, { "from": 76, "to": 78, "label": "PARALLEL" }, { "from": 77, "to": 79, "label": "EVAL with clause\napp([], X32, X32).\nand substitutionX13 -> [],\nT10 -> T31,\nX14 -> T32,\nX32 -> .(T31, T32),\nX33 -> T32,\nT12 -> .(T31, T32)" }, { "from": 77, "to": 80, "label": "EVAL-BACKTRACK" }, { "from": 78, "to": 82, "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX13 -> .(T40, X53),\nT10 -> T39,\nX14 -> X54,\nX50 -> .(T39, X54),\nX52 -> T40,\nX51 -> T42,\nT12 -> .(T40, T42),\nT41 -> T42" }, { "from": 78, "to": 83, "label": "EVAL-BACKTRACK" }, { "from": 79, "to": 81, "label": "SUCCESS" }, { "from": 82, "to": 39, "label": "INSTANCE with matching:\nX13 -> X53\nT10 -> T39\nX14 -> X54\nT12 -> T42" }, { "from": 208, "to": 222, "label": "CASE" }, { "from": 211, "to": 2, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T11" }, { "from": 222, "to": 223, "label": "PARALLEL" }, { "from": 222, "to": 224, "label": "PARALLEL" }, { "from": 223, "to": 227, "label": "EVAL with clause\napp([], X67, X67).\nand substitutionT17 -> [],\nT18 -> T56,\nX67 -> T56,\nX15 -> T56" }, { "from": 223, "to": 228, "label": "EVAL-BACKTRACK" }, { "from": 224, "to": 240, "label": "EVAL with clause\napp(.(X78, X79), X80, .(X78, X81)) :- app(X79, X80, X81).\nand substitutionX78 -> T63,\nX79 -> T66,\nT17 -> .(T63, T66),\nT18 -> T67,\nX80 -> T67,\nX81 -> X82,\nX15 -> .(T63, X82),\nT64 -> T66,\nT65 -> T67" }, { "from": 224, "to": 241, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 229, "label": "SUCCESS" }, { "from": 240, "to": 208, "label": "INSTANCE with matching:\nT17 -> T66\nT18 -> T67\nX15 -> X82" } ], "type": "Graph" } } ---------------------------------------- (81) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 Q is empty. ---------------------------------------- (82) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T10, T11)) -> U1^1(f30_in(T10, T11), .(T10, T11)) F2_IN(.(T10, T11)) -> F30_IN(T10, T11) F39_IN(T39) -> U2^1(f39_in(T39), T39) F39_IN(T39) -> F39_IN(T39) F208_IN -> U3^1(f208_in) F208_IN -> F208_IN F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) F30_IN(T10, T11) -> F39_IN(T10) U4^1(f39_out1, T10, T11) -> U5^1(f40_in(T11), T10, T11) U4^1(f39_out1, T10, T11) -> F40_IN(T11) F40_IN(T11) -> U6^1(f208_in, T11) F40_IN(T11) -> F208_IN U6^1(f208_out1, T11) -> U7^1(f2_in(T11), T11) U6^1(f208_out1, T11) -> F2_IN(T11) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes. ---------------------------------------- (85) Complex Obligation (AND) ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: F208_IN -> F208_IN The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: F208_IN -> F208_IN The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) 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. ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: F208_IN -> F208_IN R is empty. The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) 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, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: F208_IN -> F208_IN R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) 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 = F208_IN evaluates to t =F208_IN 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 F208_IN to F208_IN. ---------------------------------------- (94) NO ---------------------------------------- (95) Obligation: Q DP problem: The TRS P consists of the following rules: F39_IN(T39) -> F39_IN(T39) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (97) Obligation: Q DP problem: The TRS P consists of the following rules: F39_IN(T39) -> F39_IN(T39) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (98) 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. ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: F39_IN(T39) -> F39_IN(T39) R is empty. The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (100) 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, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) ---------------------------------------- (101) Obligation: Q DP problem: The TRS P consists of the following rules: F39_IN(T39) -> F39_IN(T39) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (102) 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 = F39_IN(T39) evaluates to t =F39_IN(T39) 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 F39_IN(T39) to F39_IN(T39). ---------------------------------------- (103) NO ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T10, T11)) -> F30_IN(T10, T11) F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) U4^1(f39_out1, T10, T11) -> F40_IN(T11) F40_IN(T11) -> U6^1(f208_in, T11) U6^1(f208_out1, T11) -> F2_IN(T11) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T10, T11)) -> F30_IN(T10, T11) F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) U4^1(f39_out1, T10, T11) -> F40_IN(T11) F40_IN(T11) -> U6^1(f208_in, T11) U6^1(f208_out1, T11) -> F2_IN(T11) The TRS R consists of the following rules: f2_in([]) -> f2_out1 f2_in(.(T10, T11)) -> U1(f30_in(T10, T11), .(T10, T11)) U1(f30_out1, .(T10, T11)) -> f2_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f30_in(T10, T11) -> U4(f39_in(T10), T10, T11) U4(f39_out1, T10, T11) -> U5(f40_in(T11), T10, T11) U5(f40_out1, T10, T11) -> f30_out1 f40_in(T11) -> U6(f208_in, T11) U6(f208_out1, T11) -> U7(f2_in(T11), T11) U7(f2_out1, T11) -> f40_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (107) 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. ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T10, T11)) -> F30_IN(T10, T11) F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) U4^1(f39_out1, T10, T11) -> F40_IN(T11) F40_IN(T11) -> U6^1(f208_in, T11) U6^1(f208_out1, T11) -> F2_IN(T11) The TRS R consists of the following rules: f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 The set Q consists of the following terms: f2_in([]) f2_in(.(x0, x1)) U1(f30_out1, .(x0, x1)) f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) 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, x1)) U1(f30_out1, .(x0, x1)) f30_in(x0, x1) U4(f39_out1, x0, x1) U5(f40_out1, x0, x1) f40_in(x0) U6(f208_out1, x0) U7(f2_out1, x0) ---------------------------------------- (110) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(.(T10, T11)) -> F30_IN(T10, T11) F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) U4^1(f39_out1, T10, T11) -> F40_IN(T11) F40_IN(T11) -> U6^1(f208_in, T11) U6^1(f208_out1, T11) -> F2_IN(T11) The TRS R consists of the following rules: f208_in -> f208_out1 f208_in -> U3(f208_in) U3(f208_out1) -> f208_out1 f39_in(T31) -> f39_out1 f39_in(T39) -> U2(f39_in(T39), T39) U2(f39_out1, T39) -> f39_out1 The set Q consists of the following terms: f39_in(x0) U2(f39_out1, x0) f208_in U3(f208_out1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (111) 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: *F30_IN(T10, T11) -> U4^1(f39_in(T10), T10, T11) The graph contains the following edges 1 >= 2, 2 >= 3 *U6^1(f208_out1, T11) -> F2_IN(T11) The graph contains the following edges 2 >= 1 *U4^1(f39_out1, T10, T11) -> F40_IN(T11) The graph contains the following edges 3 >= 1 *F2_IN(.(T10, T11)) -> F30_IN(T10, T11) The graph contains the following edges 1 > 1, 1 > 2 *F40_IN(T11) -> U6^1(f208_in, T11) The graph contains the following edges 1 >= 2 ---------------------------------------- (112) YES ---------------------------------------- (113) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(perm ([]) ([]))", null ], [ "(perm Xs (. X Ys))", "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "44": { "goal": [{ "clause": 2, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [{ "clause": 3, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "46": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X13 (. T10 X14) T12) (',' (app X13 X14 X15) (perm X15 T11)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X13", "X14", "X15" ], "exprvars": [] } }, "29": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "70": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "119": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "71": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T49 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "72": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T17 T18 X15)" }, { "clause": 3, "scope": 3, "term": "(app T17 T18 X15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "73": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "74": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T17 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X53 (. T39 X54) T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": [ "X53", "X54" ], "exprvars": [] } }, "75": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": 0, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": 0, "scope": 1, "term": "(perm T1 T2)" }, { "clause": 1, "scope": 1, "term": "(perm T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T66 T67 X82)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X82"], "exprvars": [] } }, "84": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X13 (. T10 X14) T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } }, "85": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T17 T18 X15) (perm X15 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X15"], "exprvars": [] } }, "43": { "goal": [ { "clause": 2, "scope": 2, "term": "(app X13 (. T10 X14) T12)" }, { "clause": 3, "scope": 2, "term": "(app X13 (. T10 X14) T12)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X13", "X14" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 9, "label": "CASE" }, { "from": 9, "to": 11, "label": "PARALLEL" }, { "from": 9, "to": 12, "label": "PARALLEL" }, { "from": 11, "to": 22, "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 11, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 28, "label": "EVAL with clause\nperm(X10, .(X11, X12)) :- ','(app(X13, .(X11, X14), X10), ','(app(X13, X14, X15), perm(X15, X12))).\nand substitutionT1 -> T12,\nX10 -> T12,\nX11 -> T10,\nX12 -> T11,\nT2 -> .(T10, T11),\nT9 -> T12" }, { "from": 12, "to": 29, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 26, "label": "SUCCESS" }, { "from": 28, "to": 41, "label": "SPLIT 1" }, { "from": 28, "to": 42, "label": "SPLIT 2\nreplacements:X13 -> T17,\nX14 -> T18" }, { "from": 41, "to": 43, "label": "CASE" }, { "from": 42, "to": 70, "label": "SPLIT 1" }, { "from": 42, "to": 71, "label": "SPLIT 2\nreplacements:X15 -> T49" }, { "from": 43, "to": 44, "label": "PARALLEL" }, { "from": 43, "to": 45, "label": "PARALLEL" }, { "from": 44, "to": 46, "label": "EVAL with clause\napp([], X32, X32).\nand substitutionX13 -> [],\nT10 -> T31,\nX14 -> T32,\nX32 -> .(T31, T32),\nX33 -> T32,\nT12 -> .(T31, T32)" }, { "from": 44, "to": 47, "label": "EVAL-BACKTRACK" }, { "from": 45, "to": 53, "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX13 -> .(T40, X53),\nT10 -> T39,\nX14 -> X54,\nX50 -> .(T39, X54),\nX52 -> T40,\nX51 -> T42,\nT12 -> .(T40, T42),\nT41 -> T42" }, { "from": 45, "to": 55, "label": "EVAL-BACKTRACK" }, { "from": 46, "to": 48, "label": "SUCCESS" }, { "from": 53, "to": 41, "label": "INSTANCE with matching:\nX13 -> X53\nT10 -> T39\nX14 -> X54\nT12 -> T42" }, { "from": 70, "to": 72, "label": "CASE" }, { "from": 71, "to": 3, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T11" }, { "from": 72, "to": 73, "label": "PARALLEL" }, { "from": 72, "to": 74, "label": "PARALLEL" }, { "from": 73, "to": 75, "label": "EVAL with clause\napp([], X67, X67).\nand substitutionT17 -> [],\nT18 -> T56,\nX67 -> T56,\nX15 -> T56" }, { "from": 73, "to": 84, "label": "EVAL-BACKTRACK" }, { "from": 74, "to": 109, "label": "EVAL with clause\napp(.(X78, X79), X80, .(X78, X81)) :- app(X79, X80, X81).\nand substitutionX78 -> T63,\nX79 -> T66,\nT17 -> .(T63, T66),\nT18 -> T67,\nX80 -> T67,\nX81 -> X82,\nX15 -> .(T63, X82),\nT64 -> T66,\nT65 -> T67" }, { "from": 74, "to": 119, "label": "EVAL-BACKTRACK" }, { "from": 75, "to": 85, "label": "SUCCESS" }, { "from": 109, "to": 70, "label": "INSTANCE with matching:\nT17 -> T66\nT18 -> T67\nX15 -> X82" } ], "type": "Graph" } } ---------------------------------------- (114) Complex Obligation (AND) ---------------------------------------- (115) Obligation: Rules: f72_in -> f74_in :|: TRUE f72_in -> f73_in :|: TRUE f74_out -> f72_out :|: TRUE f73_out -> f72_out :|: TRUE f72_out -> f70_out :|: TRUE f70_in -> f72_in :|: TRUE f70_out -> f109_out :|: TRUE f109_in -> f70_in :|: TRUE f74_in -> f109_in :|: TRUE f109_out -> f74_out :|: TRUE f74_in -> f119_in :|: TRUE f119_out -> f74_out :|: TRUE f9_out(T2) -> f3_out(T2) :|: TRUE f3_in(x) -> f9_in(x) :|: TRUE f9_in(x1) -> f12_in(x1) :|: TRUE f9_in(x2) -> f11_in(x2) :|: TRUE f11_out(x3) -> f9_out(x3) :|: TRUE f12_out(x4) -> f9_out(x4) :|: TRUE f29_out -> f12_out(x5) :|: TRUE f28_out(T10, T11) -> f12_out(.(T10, T11)) :|: TRUE f12_in(x6) -> f29_in :|: TRUE f12_in(.(x7, x8)) -> f28_in(x7, x8) :|: TRUE f28_in(x9, x10) -> f41_in(x9) :|: TRUE f42_out(x11) -> f28_out(x12, x11) :|: TRUE f41_out(x13) -> f42_in(x14) :|: TRUE f71_out(x15) -> f42_out(x15) :|: TRUE f42_in(x16) -> f70_in :|: TRUE f70_out -> f71_in(x17) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (116) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (117) TRUE ---------------------------------------- (118) Obligation: Rules: f41_in(T10) -> f43_in(T10) :|: TRUE f43_out(x) -> f41_out(x) :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f41_out(x1) -> f53_out(x1) :|: TRUE f44_out(x2) -> f43_out(x2) :|: TRUE f43_in(x3) -> f44_in(x3) :|: TRUE f43_in(x4) -> f45_in(x4) :|: TRUE f45_out(x5) -> f43_out(x5) :|: TRUE f53_out(x6) -> f45_out(x6) :|: TRUE f55_out -> f45_out(x7) :|: TRUE f45_in(x8) -> f53_in(x8) :|: TRUE f45_in(x9) -> f55_in :|: TRUE f9_out(T2) -> f3_out(T2) :|: TRUE f3_in(x10) -> f9_in(x10) :|: TRUE f9_in(x11) -> f12_in(x11) :|: TRUE f9_in(x12) -> f11_in(x12) :|: TRUE f11_out(x13) -> f9_out(x13) :|: TRUE f12_out(x14) -> f9_out(x14) :|: TRUE f29_out -> f12_out(x15) :|: TRUE f28_out(x16, x17) -> f12_out(.(x16, x17)) :|: TRUE f12_in(x18) -> f29_in :|: TRUE f12_in(.(x19, x20)) -> f28_in(x19, x20) :|: TRUE f28_in(x21, x22) -> f41_in(x21) :|: TRUE f42_out(x23) -> f28_out(x24, x23) :|: TRUE f41_out(x25) -> f42_in(x26) :|: TRUE Start term: f3_in(T2) ---------------------------------------- (119) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f41_in(T10) -> f43_in(T10) :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f43_in(x4) -> f45_in(x4) :|: TRUE f45_in(x8) -> f53_in(x8) :|: TRUE ---------------------------------------- (120) Obligation: Rules: f41_in(T10) -> f43_in(T10) :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f43_in(x4) -> f45_in(x4) :|: TRUE f45_in(x8) -> f53_in(x8) :|: TRUE ---------------------------------------- (121) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (122) Obligation: Rules: f53_in(T39:0) -> f53_in(T39:0) :|: TRUE ---------------------------------------- (123) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (124) Obligation: Rules: f53_in(T39:0) -> f53_in(T39:0) :|: TRUE ---------------------------------------- (125) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f53_in(T39:0) -> f53_in(T39:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (126) Obligation: Termination digraph: Nodes: (1) f53_in(T39:0) -> f53_in(T39:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (127) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f53_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (128) Obligation: Rules: f53_in(T39:0) -> f53_in(T39:0) :|: TRUE ---------------------------------------- (129) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, T39:0) -> f(1, T39:0) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1, -8) ---------------------------------------- (130) NO ---------------------------------------- (131) Obligation: Rules: f72_in -> f74_in :|: TRUE f72_in -> f73_in :|: TRUE f74_out -> f72_out :|: TRUE f73_out -> f72_out :|: TRUE f41_in(T10) -> f43_in(T10) :|: TRUE f43_out(x) -> f41_out(x) :|: TRUE f72_out -> f70_out :|: TRUE f70_in -> f72_in :|: TRUE f46_in -> f46_out :|: TRUE f70_out -> f109_out :|: TRUE f109_in -> f70_in :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f41_out(x1) -> f53_out(x1) :|: TRUE f53_out(x2) -> f45_out(x2) :|: TRUE f55_out -> f45_out(x3) :|: TRUE f45_in(x4) -> f53_in(x4) :|: TRUE f45_in(x5) -> f55_in :|: TRUE f71_out(T11) -> f42_out(T11) :|: TRUE f42_in(x6) -> f70_in :|: TRUE f70_out -> f71_in(x7) :|: TRUE f9_out(T2) -> f3_out(T2) :|: TRUE f3_in(x8) -> f9_in(x8) :|: TRUE f29_out -> f12_out(x9) :|: TRUE f28_out(x10, x11) -> f12_out(.(x10, x11)) :|: TRUE f12_in(x12) -> f29_in :|: TRUE f12_in(.(x13, x14)) -> f28_in(x13, x14) :|: TRUE f44_in(x15) -> f47_in :|: TRUE f46_out -> f44_out(T31) :|: TRUE f44_in(x16) -> f46_in :|: TRUE f47_out -> f44_out(x17) :|: TRUE f75_in -> f75_out :|: TRUE f9_in(x18) -> f12_in(x18) :|: TRUE f9_in(x19) -> f11_in(x19) :|: TRUE f11_out(x20) -> f9_out(x20) :|: TRUE f12_out(x21) -> f9_out(x21) :|: TRUE f28_in(x22, x23) -> f41_in(x22) :|: TRUE f42_out(x24) -> f28_out(x25, x24) :|: TRUE f41_out(x26) -> f42_in(x27) :|: TRUE f44_out(x28) -> f43_out(x28) :|: TRUE f43_in(x29) -> f44_in(x29) :|: TRUE f43_in(x30) -> f45_in(x30) :|: TRUE f45_out(x31) -> f43_out(x31) :|: TRUE f73_in -> f84_in :|: TRUE f73_in -> f75_in :|: TRUE f84_out -> f73_out :|: TRUE f75_out -> f73_out :|: TRUE f3_out(x32) -> f71_out(x32) :|: TRUE f71_in(x33) -> f3_in(x33) :|: TRUE f74_in -> f109_in :|: TRUE f109_out -> f74_out :|: TRUE f74_in -> f119_in :|: TRUE f119_out -> f74_out :|: TRUE Start term: f3_in(T2) ---------------------------------------- (132) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f72_in -> f74_in :|: TRUE f72_in -> f73_in :|: TRUE f74_out -> f72_out :|: TRUE f73_out -> f72_out :|: TRUE f41_in(T10) -> f43_in(T10) :|: TRUE f43_out(x) -> f41_out(x) :|: TRUE f72_out -> f70_out :|: TRUE f70_in -> f72_in :|: TRUE f46_in -> f46_out :|: TRUE f70_out -> f109_out :|: TRUE f109_in -> f70_in :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f41_out(x1) -> f53_out(x1) :|: TRUE f53_out(x2) -> f45_out(x2) :|: TRUE f45_in(x4) -> f53_in(x4) :|: TRUE f42_in(x6) -> f70_in :|: TRUE f70_out -> f71_in(x7) :|: TRUE f3_in(x8) -> f9_in(x8) :|: TRUE f12_in(.(x13, x14)) -> f28_in(x13, x14) :|: TRUE f46_out -> f44_out(T31) :|: TRUE f44_in(x16) -> f46_in :|: TRUE f75_in -> f75_out :|: TRUE f9_in(x18) -> f12_in(x18) :|: TRUE f28_in(x22, x23) -> f41_in(x22) :|: TRUE f41_out(x26) -> f42_in(x27) :|: TRUE f44_out(x28) -> f43_out(x28) :|: TRUE f43_in(x29) -> f44_in(x29) :|: TRUE f43_in(x30) -> f45_in(x30) :|: TRUE f45_out(x31) -> f43_out(x31) :|: TRUE f73_in -> f75_in :|: TRUE f75_out -> f73_out :|: TRUE f71_in(x33) -> f3_in(x33) :|: TRUE f74_in -> f109_in :|: TRUE f109_out -> f74_out :|: TRUE ---------------------------------------- (133) Obligation: Rules: f72_in -> f74_in :|: TRUE f72_in -> f73_in :|: TRUE f74_out -> f72_out :|: TRUE f73_out -> f72_out :|: TRUE f41_in(T10) -> f43_in(T10) :|: TRUE f43_out(x) -> f41_out(x) :|: TRUE f72_out -> f70_out :|: TRUE f70_in -> f72_in :|: TRUE f46_in -> f46_out :|: TRUE f70_out -> f109_out :|: TRUE f109_in -> f70_in :|: TRUE f53_in(T39) -> f41_in(T39) :|: TRUE f41_out(x1) -> f53_out(x1) :|: TRUE f53_out(x2) -> f45_out(x2) :|: TRUE f45_in(x4) -> f53_in(x4) :|: TRUE f42_in(x6) -> f70_in :|: TRUE f70_out -> f71_in(x7) :|: TRUE f3_in(x8) -> f9_in(x8) :|: TRUE f12_in(.(x13, x14)) -> f28_in(x13, x14) :|: TRUE f46_out -> f44_out(T31) :|: TRUE f44_in(x16) -> f46_in :|: TRUE f75_in -> f75_out :|: TRUE f9_in(x18) -> f12_in(x18) :|: TRUE f28_in(x22, x23) -> f41_in(x22) :|: TRUE f41_out(x26) -> f42_in(x27) :|: TRUE f44_out(x28) -> f43_out(x28) :|: TRUE f43_in(x29) -> f44_in(x29) :|: TRUE f43_in(x30) -> f45_in(x30) :|: TRUE f45_out(x31) -> f43_out(x31) :|: TRUE f73_in -> f75_in :|: TRUE f75_out -> f73_out :|: TRUE f71_in(x33) -> f3_in(x33) :|: TRUE f74_in -> f109_in :|: TRUE f109_out -> f74_out :|: TRUE