8.97/3.17 MAYBE 8.97/3.18 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 8.97/3.18 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.97/3.18 8.97/3.18 8.97/3.18 Left Termination of the query pattern 8.97/3.18 8.97/3.18 fl(a,g,a) 8.97/3.18 8.97/3.18 w.r.t. the given Prolog program could not be shown: 8.97/3.18 8.97/3.18 (0) Prolog 8.97/3.18 (1) PrologToPiTRSProof [SOUND, 0 ms] 8.97/3.18 (2) PiTRS 8.97/3.18 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.97/3.18 (4) PiDP 8.97/3.18 (5) DependencyGraphProof [EQUIVALENT, 1 ms] 8.97/3.18 (6) AND 8.97/3.18 (7) PiDP 8.97/3.18 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (9) PiDP 8.97/3.18 (10) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (11) QDP 8.97/3.18 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.97/3.18 (13) YES 8.97/3.18 (14) PiDP 8.97/3.18 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (16) PiDP 8.97/3.18 (17) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (18) QDP 8.97/3.18 (19) QDPQMonotonicMRRProof [EQUIVALENT, 14 ms] 8.97/3.18 (20) QDP 8.97/3.18 (21) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (22) QDP 8.97/3.18 (23) QReductionProof [EQUIVALENT, 0 ms] 8.97/3.18 (24) QDP 8.97/3.18 (25) TransformationProof [EQUIVALENT, 0 ms] 8.97/3.18 (26) QDP 8.97/3.18 (27) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (28) QDP 8.97/3.18 (29) QReductionProof [EQUIVALENT, 0 ms] 8.97/3.18 (30) QDP 8.97/3.18 (31) TransformationProof [EQUIVALENT, 0 ms] 8.97/3.18 (32) QDP 8.97/3.18 (33) PrologToPiTRSProof [SOUND, 0 ms] 8.97/3.18 (34) PiTRS 8.97/3.18 (35) DependencyPairsProof [EQUIVALENT, 0 ms] 8.97/3.18 (36) PiDP 8.97/3.18 (37) DependencyGraphProof [EQUIVALENT, 0 ms] 8.97/3.18 (38) AND 8.97/3.18 (39) PiDP 8.97/3.18 (40) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (41) PiDP 8.97/3.18 (42) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (43) QDP 8.97/3.18 (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.97/3.18 (45) YES 8.97/3.18 (46) PiDP 8.97/3.18 (47) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (48) PiDP 8.97/3.18 (49) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (50) QDP 8.97/3.18 (51) MRRProof [EQUIVALENT, 11 ms] 8.97/3.18 (52) QDP 8.97/3.18 (53) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (54) QDP 8.97/3.18 (55) QReductionProof [EQUIVALENT, 0 ms] 8.97/3.18 (56) QDP 8.97/3.18 (57) TransformationProof [EQUIVALENT, 0 ms] 8.97/3.18 (58) QDP 8.97/3.18 (59) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (60) QDP 8.97/3.18 (61) QReductionProof [EQUIVALENT, 0 ms] 8.97/3.18 (62) QDP 8.97/3.18 (63) TransformationProof [EQUIVALENT, 0 ms] 8.97/3.18 (64) QDP 8.97/3.18 (65) PrologToDTProblemTransformerProof [SOUND, 0 ms] 8.97/3.18 (66) TRIPLES 8.97/3.18 (67) TriplesToPiDPProof [SOUND, 0 ms] 8.97/3.18 (68) PiDP 8.97/3.18 (69) DependencyGraphProof [EQUIVALENT, 0 ms] 8.97/3.18 (70) AND 8.97/3.18 (71) PiDP 8.97/3.18 (72) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (73) PiDP 8.97/3.18 (74) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (75) QDP 8.97/3.18 (76) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.97/3.18 (77) YES 8.97/3.18 (78) PiDP 8.97/3.18 (79) PiDPToQDPProof [SOUND, 0 ms] 8.97/3.18 (80) QDP 8.97/3.18 (81) QDPQMonotonicMRRProof [EQUIVALENT, 21 ms] 8.97/3.18 (82) QDP 8.97/3.18 (83) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (84) QDP 8.97/3.18 (85) QReductionProof [EQUIVALENT, 0 ms] 8.97/3.18 (86) QDP 8.97/3.18 (87) PrologToTRSTransformerProof [SOUND, 0 ms] 8.97/3.18 (88) QTRS 8.97/3.18 (89) DependencyPairsProof [EQUIVALENT, 0 ms] 8.97/3.18 (90) QDP 8.97/3.18 (91) DependencyGraphProof [EQUIVALENT, 2 ms] 8.97/3.18 (92) AND 8.97/3.18 (93) QDP 8.97/3.18 (94) UsableRulesProof [EQUIVALENT, 0 ms] 8.97/3.18 (95) QDP 8.97/3.18 (96) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.97/3.18 (97) YES 8.97/3.18 (98) QDP 8.97/3.18 (99) NonTerminationLoopProof [COMPLETE, 0 ms] 8.97/3.18 (100) NO 8.97/3.18 (101) PrologToIRSwTTransformerProof [SOUND, 0 ms] 8.97/3.18 (102) AND 8.97/3.18 (103) IRSwT 8.97/3.18 (104) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 8.97/3.18 (105) IRSwT 8.97/3.18 (106) IntTRSCompressionProof [EQUIVALENT, 34 ms] 8.97/3.18 (107) IRSwT 8.97/3.18 (108) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.97/3.18 (109) IRSwT 8.97/3.18 (110) IRSwTTerminationDigraphProof [EQUIVALENT, 5 ms] 8.97/3.18 (111) IRSwT 8.97/3.18 (112) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 18 ms] 8.97/3.18 (113) IRSwT 8.97/3.18 (114) TempFilterProof [SOUND, 2 ms] 8.97/3.18 (115) IRSwT 8.97/3.18 (116) IRSwTToQDPProof [SOUND, 0 ms] 8.97/3.18 (117) QDP 8.97/3.18 (118) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.97/3.18 (119) YES 8.97/3.18 (120) IRSwT 8.97/3.18 (121) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 8.97/3.18 (122) IRSwT 8.97/3.18 (123) IntTRSCompressionProof [EQUIVALENT, 10 ms] 8.97/3.18 (124) IRSwT 8.97/3.18 (125) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.97/3.18 (126) IRSwT 8.97/3.18 (127) IRSwTTerminationDigraphProof [EQUIVALENT, 9 ms] 8.97/3.18 (128) IRSwT 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (0) 8.97/3.18 Obligation: 8.97/3.18 Clauses: 8.97/3.18 8.97/3.18 fl([], [], 0). 8.97/3.18 fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). 8.97/3.18 append([], X, X). 8.97/3.18 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 8.97/3.18 8.97/3.18 8.97/3.18 Query: fl(a,g,a) 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (1) PrologToPiTRSProof (SOUND) 8.97/3.18 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.97/3.18 8.97/3.18 fl_in_3: (f,b,f) 8.97/3.18 8.97/3.18 append_in_3: (f,f,b) 8.97/3.18 8.97/3.18 Transforming Prolog into the following Term Rewriting System: 8.97/3.18 8.97/3.18 Pi-finite rewrite system: 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 8.97/3.18 8.97/3.18 8.97/3.18 8.97/3.18 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.97/3.18 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (2) 8.97/3.18 Obligation: 8.97/3.18 Pi-finite rewrite system: 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (3) DependencyPairsProof (EQUIVALENT) 8.97/3.18 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 8.97/3.18 8.97/3.18 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 8.97/3.18 8.97/3.18 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 8.97/3.18 8.97/3.18 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x3, x5) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (4) 8.97/3.18 Obligation: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 8.97/3.18 8.97/3.18 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 8.97/3.18 8.97/3.18 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 8.97/3.18 8.97/3.18 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x3, x5) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (5) DependencyGraphProof (EQUIVALENT) 8.97/3.18 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (6) 8.97/3.18 Complex Obligation (AND) 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (7) 8.97/3.18 Obligation: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (8) UsableRulesProof (EQUIVALENT) 8.97/3.18 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (9) 8.97/3.18 Obligation: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 8.97/3.18 8.97/3.18 R is empty. 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (10) PiDPToQDPProof (SOUND) 8.97/3.18 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (11) 8.97/3.18 Obligation: 8.97/3.18 Q DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) 8.97/3.18 8.97/3.18 R is empty. 8.97/3.18 Q is empty. 8.97/3.18 We have to consider all (P,Q,R)-chains. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (12) QDPSizeChangeProof (EQUIVALENT) 8.97/3.18 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. 8.97/3.18 8.97/3.18 From the DPs we obtained the following set of size-change graphs: 8.97/3.18 *APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) 8.97/3.18 The graph contains the following edges 1 > 1 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (13) 8.97/3.18 YES 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (14) 8.97/3.18 Obligation: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.18 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.18 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.18 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) 8.97/3.18 8.97/3.18 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 8.97/3.18 8.97/3.18 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (15) UsableRulesProof (EQUIVALENT) 8.97/3.18 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (16) 8.97/3.18 Obligation: 8.97/3.18 Pi DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 8.97/3.18 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.18 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 8.97/3.18 The argument filtering Pi contains the following mapping: 8.97/3.18 [] = [] 8.97/3.18 8.97/3.18 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.18 8.97/3.18 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 8.97/3.18 8.97/3.18 .(x1, x2) = .(x1, x2) 8.97/3.18 8.97/3.18 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) 8.97/3.18 8.97/3.18 s(x1) = s(x1) 8.97/3.18 8.97/3.18 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 8.97/3.18 8.97/3.18 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 8.97/3.18 8.97/3.18 8.97/3.18 We have to consider all (P,R,Pi)-chains 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (17) PiDPToQDPProof (SOUND) 8.97/3.18 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (18) 8.97/3.18 Obligation: 8.97/3.18 Q DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.18 FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 append_in_aag(X) -> append_out_aag([], X, X) 8.97/3.18 append_in_aag(.(X, Zs)) -> U3_aag(X, Zs, append_in_aag(Zs)) 8.97/3.18 U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 8.97/3.18 The set Q consists of the following terms: 8.97/3.18 8.97/3.18 append_in_aag(x0) 8.97/3.18 U3_aag(x0, x1, x2) 8.97/3.18 8.97/3.18 We have to consider all (P,Q,R)-chains. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (19) QDPQMonotonicMRRProof (EQUIVALENT) 8.97/3.18 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 8.97/3.18 8.97/3.18 8.97/3.18 Strictly oriented rules of the TRS R: 8.97/3.18 8.97/3.18 append_in_aag(.(X, Zs)) -> U3_aag(X, Zs, append_in_aag(Zs)) 8.97/3.18 8.97/3.18 Used ordering: Polynomial interpretation [POLO]: 8.97/3.18 8.97/3.18 POL(.(x_1, x_2)) = 1 + 2*x_2 8.97/3.18 POL(FL_IN_AGA(x_1)) = 2*x_1 8.97/3.18 POL(U1_AGA(x_1, x_2)) = x_2 8.97/3.18 POL(U3_aag(x_1, x_2, x_3)) = x_3 8.97/3.18 POL([]) = 2 8.97/3.18 POL(append_in_aag(x_1)) = 2*x_1 8.97/3.18 POL(append_out_aag(x_1, x_2, x_3)) = 2*x_2 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (20) 8.97/3.18 Obligation: 8.97/3.18 Q DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.18 FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 append_in_aag(X) -> append_out_aag([], X, X) 8.97/3.18 U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.18 8.97/3.18 The set Q consists of the following terms: 8.97/3.18 8.97/3.18 append_in_aag(x0) 8.97/3.18 U3_aag(x0, x1, x2) 8.97/3.18 8.97/3.18 We have to consider all (P,Q,R)-chains. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (21) UsableRulesProof (EQUIVALENT) 8.97/3.18 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. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (22) 8.97/3.18 Obligation: 8.97/3.18 Q DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.18 FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 append_in_aag(X) -> append_out_aag([], X, X) 8.97/3.18 8.97/3.18 The set Q consists of the following terms: 8.97/3.18 8.97/3.18 append_in_aag(x0) 8.97/3.18 U3_aag(x0, x1, x2) 8.97/3.18 8.97/3.18 We have to consider all (P,Q,R)-chains. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (23) QReductionProof (EQUIVALENT) 8.97/3.18 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.97/3.18 8.97/3.18 U3_aag(x0, x1, x2) 8.97/3.18 8.97/3.18 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (24) 8.97/3.18 Obligation: 8.97/3.18 Q DP problem: 8.97/3.18 The TRS P consists of the following rules: 8.97/3.18 8.97/3.18 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.18 FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) 8.97/3.18 8.97/3.18 The TRS R consists of the following rules: 8.97/3.18 8.97/3.18 append_in_aag(X) -> append_out_aag([], X, X) 8.97/3.18 8.97/3.18 The set Q consists of the following terms: 8.97/3.18 8.97/3.18 append_in_aag(x0) 8.97/3.18 8.97/3.18 We have to consider all (P,Q,R)-chains. 8.97/3.18 ---------------------------------------- 8.97/3.18 8.97/3.18 (25) TransformationProof (EQUIVALENT) 8.97/3.18 By rewriting [LPAR04] the rule FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) at position [1] we obtained the following new rules [LPAR04]: 8.97/3.18 8.97/3.18 (FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)),FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R))) 8.97/3.19 8.97/3.19 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (26) 8.97/3.19 Obligation: 8.97/3.19 Q DP problem: 8.97/3.19 The TRS P consists of the following rules: 8.97/3.19 8.97/3.19 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.19 FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) 8.97/3.19 8.97/3.19 The TRS R consists of the following rules: 8.97/3.19 8.97/3.19 append_in_aag(X) -> append_out_aag([], X, X) 8.97/3.19 8.97/3.19 The set Q consists of the following terms: 8.97/3.19 8.97/3.19 append_in_aag(x0) 8.97/3.19 8.97/3.19 We have to consider all (P,Q,R)-chains. 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (27) UsableRulesProof (EQUIVALENT) 8.97/3.19 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. 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (28) 8.97/3.19 Obligation: 8.97/3.19 Q DP problem: 8.97/3.19 The TRS P consists of the following rules: 8.97/3.19 8.97/3.19 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.19 FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) 8.97/3.19 8.97/3.19 R is empty. 8.97/3.19 The set Q consists of the following terms: 8.97/3.19 8.97/3.19 append_in_aag(x0) 8.97/3.19 8.97/3.19 We have to consider all (P,Q,R)-chains. 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (29) QReductionProof (EQUIVALENT) 8.97/3.19 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.97/3.19 8.97/3.19 append_in_aag(x0) 8.97/3.19 8.97/3.19 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (30) 8.97/3.19 Obligation: 8.97/3.19 Q DP problem: 8.97/3.19 The TRS P consists of the following rules: 8.97/3.19 8.97/3.19 U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) 8.97/3.19 FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) 8.97/3.19 8.97/3.19 R is empty. 8.97/3.19 Q is empty. 8.97/3.19 We have to consider all (P,Q,R)-chains. 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (31) TransformationProof (EQUIVALENT) 8.97/3.19 By instantiating [LPAR04] the rule U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) we obtained the following new rules [LPAR04]: 8.97/3.19 8.97/3.19 (U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0),U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0)) 8.97/3.19 8.97/3.19 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (32) 8.97/3.19 Obligation: 8.97/3.19 Q DP problem: 8.97/3.19 The TRS P consists of the following rules: 8.97/3.19 8.97/3.19 FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) 8.97/3.19 U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0) 8.97/3.19 8.97/3.19 R is empty. 8.97/3.19 Q is empty. 8.97/3.19 We have to consider all (P,Q,R)-chains. 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (33) PrologToPiTRSProof (SOUND) 8.97/3.19 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.97/3.19 8.97/3.19 fl_in_3: (f,b,f) 8.97/3.19 8.97/3.19 append_in_3: (f,f,b) 8.97/3.19 8.97/3.19 Transforming Prolog into the following Term Rewriting System: 8.97/3.19 8.97/3.19 Pi-finite rewrite system: 8.97/3.19 The TRS R consists of the following rules: 8.97/3.19 8.97/3.19 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.19 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.19 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.19 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 8.97/3.19 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 8.97/3.19 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 8.97/3.19 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 8.97/3.19 8.97/3.19 The argument filtering Pi contains the following mapping: 8.97/3.19 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 8.97/3.19 8.97/3.19 [] = [] 8.97/3.19 8.97/3.19 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 8.97/3.19 8.97/3.19 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 8.97/3.19 8.97/3.19 append_in_aag(x1, x2, x3) = append_in_aag(x3) 8.97/3.19 8.97/3.19 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 8.97/3.19 8.97/3.19 .(x1, x2) = .(x1, x2) 8.97/3.19 8.97/3.19 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 8.97/3.19 8.97/3.19 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 8.97/3.19 8.97/3.19 s(x1) = s(x1) 8.97/3.19 8.97/3.19 8.97/3.19 8.97/3.19 8.97/3.19 8.97/3.19 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.97/3.19 8.97/3.19 8.97/3.19 8.97/3.19 ---------------------------------------- 8.97/3.19 8.97/3.19 (34) 8.97/3.19 Obligation: 8.97/3.19 Pi-finite rewrite system: 8.97/3.19 The TRS R consists of the following rules: 8.97/3.19 8.97/3.19 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 8.97/3.19 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 8.97/3.19 append_in_aag([], X, X) -> append_out_aag([], X, X) 8.97/3.19 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 9.12/3.21 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 9.12/3.21 9.12/3.21 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (35) DependencyPairsProof (EQUIVALENT) 9.12/3.21 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 9.12/3.21 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 append_in_aag([], X, X) -> append_out_aag([], X, X) 9.12/3.21 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 9.12/3.21 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 9.12/3.21 9.12/3.21 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 9.12/3.21 9.12/3.21 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 9.12/3.21 9.12/3.21 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 9.12/3.21 9.12/3.21 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x5) 9.12/3.21 9.12/3.21 U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x5) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (36) 9.12/3.21 Obligation: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 9.12/3.21 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 append_in_aag([], X, X) -> append_out_aag([], X, X) 9.12/3.21 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 9.12/3.21 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 9.12/3.21 9.12/3.21 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 9.12/3.21 9.12/3.21 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 9.12/3.21 9.12/3.21 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 9.12/3.21 9.12/3.21 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x5) 9.12/3.21 9.12/3.21 U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x5) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (37) DependencyGraphProof (EQUIVALENT) 9.12/3.21 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (38) 9.12/3.21 Complex Obligation (AND) 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (39) 9.12/3.21 Obligation: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 9.12/3.21 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 append_in_aag([], X, X) -> append_out_aag([], X, X) 9.12/3.21 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 9.12/3.21 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 9.12/3.21 9.12/3.21 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (40) UsableRulesProof (EQUIVALENT) 9.12/3.21 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (41) 9.12/3.21 Obligation: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) 9.12/3.21 9.12/3.21 R is empty. 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (42) PiDPToQDPProof (SOUND) 9.12/3.21 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (43) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) 9.12/3.21 9.12/3.21 R is empty. 9.12/3.21 Q is empty. 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (44) QDPSizeChangeProof (EQUIVALENT) 9.12/3.21 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. 9.12/3.21 9.12/3.21 From the DPs we obtained the following set of size-change graphs: 9.12/3.21 *APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) 9.12/3.21 The graph contains the following edges 1 > 1 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (45) 9.12/3.21 YES 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (46) 9.12/3.21 Obligation: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) 9.12/3.21 fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 append_in_aag([], X, X) -> append_out_aag([], X, X) 9.12/3.21 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) 9.12/3.21 U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 fl_in_aga(x1, x2, x3) = fl_in_aga(x2) 9.12/3.21 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) 9.12/3.21 9.12/3.21 U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 9.12/3.21 9.12/3.21 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (47) UsableRulesProof (EQUIVALENT) 9.12/3.21 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (48) 9.12/3.21 Obligation: 9.12/3.21 Pi DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) 9.12/3.21 FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag([], X, X) -> append_out_aag([], X, X) 9.12/3.21 append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) 9.12/3.21 U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) 9.12/3.21 9.12/3.21 The argument filtering Pi contains the following mapping: 9.12/3.21 [] = [] 9.12/3.21 9.12/3.21 append_in_aag(x1, x2, x3) = append_in_aag(x3) 9.12/3.21 9.12/3.21 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 9.12/3.21 9.12/3.21 .(x1, x2) = .(x1, x2) 9.12/3.21 9.12/3.21 U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) 9.12/3.21 9.12/3.21 s(x1) = s(x1) 9.12/3.21 9.12/3.21 FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) 9.12/3.21 9.12/3.21 U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 9.12/3.21 9.12/3.21 9.12/3.21 We have to consider all (P,R,Pi)-chains 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (49) PiDPToQDPProof (SOUND) 9.12/3.21 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (50) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag(X) -> append_out_aag([], X) 9.12/3.21 append_in_aag(.(X, Zs)) -> U3_aag(X, append_in_aag(Zs)) 9.12/3.21 U3_aag(X, append_out_aag(Xs, Ys)) -> append_out_aag(.(X, Xs), Ys) 9.12/3.21 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 U3_aag(x0, x1) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (51) MRRProof (EQUIVALENT) 9.12/3.21 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 9.12/3.21 9.12/3.21 9.12/3.21 Strictly oriented rules of the TRS R: 9.12/3.21 9.12/3.21 append_in_aag(.(X, Zs)) -> U3_aag(X, append_in_aag(Zs)) 9.12/3.21 9.12/3.21 Used ordering: Polynomial interpretation [POLO]: 9.12/3.21 9.12/3.21 POL(.(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 9.12/3.21 POL(FL_IN_AGA(x_1)) = 2*x_1 9.12/3.21 POL(U1_AGA(x_1)) = x_1 9.12/3.21 POL(U3_aag(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 9.12/3.21 POL([]) = 0 9.12/3.21 POL(append_in_aag(x_1)) = 2*x_1 9.12/3.21 POL(append_out_aag(x_1, x_2)) = x_1 + 2*x_2 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (52) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag(X) -> append_out_aag([], X) 9.12/3.21 U3_aag(X, append_out_aag(Xs, Ys)) -> append_out_aag(.(X, Xs), Ys) 9.12/3.21 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 U3_aag(x0, x1) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (53) UsableRulesProof (EQUIVALENT) 9.12/3.21 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. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (54) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag(X) -> append_out_aag([], X) 9.12/3.21 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 U3_aag(x0, x1) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (55) QReductionProof (EQUIVALENT) 9.12/3.21 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.12/3.21 9.12/3.21 U3_aag(x0, x1) 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (56) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag(X) -> append_out_aag([], X) 9.12/3.21 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (57) TransformationProof (EQUIVALENT) 9.12/3.21 By rewriting [LPAR04] the rule FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) at position [0] we obtained the following new rules [LPAR04]: 9.12/3.21 9.12/3.21 (FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)),FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R))) 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (58) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) 9.12/3.21 9.12/3.21 The TRS R consists of the following rules: 9.12/3.21 9.12/3.21 append_in_aag(X) -> append_out_aag([], X) 9.12/3.21 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (59) UsableRulesProof (EQUIVALENT) 9.12/3.21 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. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (60) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) 9.12/3.21 9.12/3.21 R is empty. 9.12/3.21 The set Q consists of the following terms: 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (61) QReductionProof (EQUIVALENT) 9.12/3.21 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.12/3.21 9.12/3.21 append_in_aag(x0) 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (62) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) 9.12/3.21 9.12/3.21 R is empty. 9.12/3.21 Q is empty. 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (63) TransformationProof (EQUIVALENT) 9.12/3.21 By instantiating [LPAR04] the rule U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) we obtained the following new rules [LPAR04]: 9.12/3.21 9.12/3.21 (U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0),U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0)) 9.12/3.21 9.12/3.21 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (64) 9.12/3.21 Obligation: 9.12/3.21 Q DP problem: 9.12/3.21 The TRS P consists of the following rules: 9.12/3.21 9.12/3.21 FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) 9.12/3.21 U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0) 9.12/3.21 9.12/3.21 R is empty. 9.12/3.21 Q is empty. 9.12/3.21 We have to consider all (P,Q,R)-chains. 9.12/3.21 ---------------------------------------- 9.12/3.21 9.12/3.21 (65) PrologToDTProblemTransformerProof (SOUND) 9.12/3.21 Built DT problem from termination graph DT10. 9.12/3.21 9.12/3.21 { 9.12/3.21 "root": 1, 9.12/3.21 "program": { 9.12/3.21 "directives": [], 9.12/3.21 "clauses": [ 9.12/3.21 [ 9.12/3.21 "(fl ([]) ([]) (0))", 9.12/3.21 null 9.12/3.21 ], 9.12/3.21 [ 9.12/3.21 "(fl (. E X) R (s Z))", 9.12/3.21 "(',' (append E Y R) (fl X Y Z))" 9.12/3.21 ], 9.12/3.21 [ 9.12/3.21 "(append ([]) X X)", 9.12/3.21 null 9.12/3.21 ], 9.12/3.21 [ 9.12/3.21 "(append (. X Xs) Ys (. X Zs))", 9.12/3.21 "(append Xs Ys Zs)" 9.12/3.21 ] 9.12/3.21 ] 9.12/3.21 }, 9.12/3.21 "graph": { 9.12/3.21 "nodes": { 9.12/3.21 "191": { 9.12/3.21 "goal": [ 9.12/3.21 { 9.12/3.21 "clause": 0, 9.12/3.21 "scope": 1, 9.12/3.21 "term": "(fl T1 T2 T3)" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "clause": 1, 9.12/3.21 "scope": 1, 9.12/3.21 "term": "(fl T1 T2 T3)" 9.12/3.21 } 9.12/3.21 ], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T2"], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "192": { 9.12/3.21 "goal": [ 9.12/3.21 { 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(true)" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "clause": 1, 9.12/3.21 "scope": 1, 9.12/3.21 "term": "(fl T1 ([]) T3)" 9.12/3.21 } 9.12/3.21 ], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "193": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 1, 9.12/3.21 "scope": 1, 9.12/3.21 "term": "(fl T1 T2 T3)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T2 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T2"], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "type": "Nodes", 9.12/3.21 "194": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 1, 9.12/3.21 "scope": 1, 9.12/3.21 "term": "(fl T1 ([]) T3)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "195": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": ["X9"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "196": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "197": { 9.12/3.21 "goal": [ 9.12/3.21 { 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 2, 9.12/3.21 "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 2, 9.12/3.21 "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" 9.12/3.21 } 9.12/3.21 ], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": ["X9"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "230": { 9.12/3.21 "goal": [ 9.12/3.21 { 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 4, 9.12/3.21 "term": "(append T44 X58 T43)" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 4, 9.12/3.21 "term": "(append T44 X58 T43)" 9.12/3.21 } 9.12/3.21 ], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T43"], 9.12/3.21 "free": ["X58"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "198": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 2, 9.12/3.21 "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": ["X9"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "231": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 4, 9.12/3.21 "term": "(append T44 X58 T43)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T43"], 9.12/3.21 "free": ["X58"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "199": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 2, 9.12/3.21 "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": ["X9"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "210": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(fl T33 T32 T34)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T32 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T32"], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "232": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 4, 9.12/3.21 "term": "(append T44 X58 T43)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T43"], 9.12/3.21 "free": ["X58"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "211": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "233": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(true)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "212": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(',' (append T44 X58 T43) (fl T45 X58 T46))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T43"], 9.12/3.21 "free": ["X58"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "234": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "235": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "242": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(append T68 X91 T67)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T67"], 9.12/3.21 "free": ["X91"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "1": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(fl T1 T2 T3)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T2"], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "243": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "202": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(fl T13 ([]) T14)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "203": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "204": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "205": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T23 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T23"], 9.12/3.21 "free": ["X33"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "227": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "206": { 9.12/3.21 "goal": [], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": [], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "228": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(append T44 X58 T43)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T43"], 9.12/3.21 "free": ["X58"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "207": { 9.12/3.21 "goal": [ 9.12/3.21 { 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 3, 9.12/3.21 "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 3, 9.12/3.21 "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" 9.12/3.21 } 9.12/3.21 ], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T23 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T23"], 9.12/3.21 "free": ["X33"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "229": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": -1, 9.12/3.21 "scope": -1, 9.12/3.21 "term": "(fl T50 T49 T51)" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T49"], 9.12/3.21 "free": [], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "208": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 2, 9.12/3.21 "scope": 3, 9.12/3.21 "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T23 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T23"], 9.12/3.21 "free": ["X33"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "209": { 9.12/3.21 "goal": [{ 9.12/3.21 "clause": 3, 9.12/3.21 "scope": 3, 9.12/3.21 "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" 9.12/3.21 }], 9.12/3.21 "kb": { 9.12/3.21 "nonunifying": [[ 9.12/3.21 "(fl T1 T23 T3)", 9.12/3.21 "(fl ([]) ([]) (0))" 9.12/3.21 ]], 9.12/3.21 "intvars": {}, 9.12/3.21 "arithmetic": { 9.12/3.21 "type": "PlainIntegerRelationState", 9.12/3.21 "relations": [] 9.12/3.21 }, 9.12/3.21 "ground": ["T23"], 9.12/3.21 "free": ["X33"], 9.12/3.21 "exprvars": [] 9.12/3.21 } 9.12/3.21 } 9.12/3.21 }, 9.12/3.21 "edges": [ 9.12/3.21 { 9.12/3.21 "from": 1, 9.12/3.21 "to": 191, 9.12/3.21 "label": "CASE" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 191, 9.12/3.21 "to": 192, 9.12/3.21 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 191, 9.12/3.21 "to": 193, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 192, 9.12/3.21 "to": 194, 9.12/3.21 "label": "SUCCESS" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 193, 9.12/3.21 "to": 205, 9.12/3.21 "label": "EVAL with clause\nfl(.(X29, X30), X31, s(X32)) :- ','(append(X29, X33, X31), fl(X30, X33, X32)).\nand substitutionX29 -> T25,\nX30 -> T26,\nT1 -> .(T25, T26),\nT2 -> T23,\nX31 -> T23,\nX32 -> T27,\nT3 -> s(T27),\nT21 -> T25,\nT22 -> T26,\nT24 -> T27" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 193, 9.12/3.21 "to": 206, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 194, 9.12/3.21 "to": 195, 9.12/3.21 "label": "EVAL with clause\nfl(.(X5, X6), X7, s(X8)) :- ','(append(X5, X9, X7), fl(X6, X9, X8)).\nand substitutionX5 -> T10,\nX6 -> T11,\nT1 -> .(T10, T11),\nX7 -> [],\nX8 -> T12,\nT3 -> s(T12),\nT7 -> T10,\nT8 -> T11,\nT9 -> T12" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 194, 9.12/3.21 "to": 196, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 195, 9.12/3.21 "to": 197, 9.12/3.21 "label": "CASE" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 197, 9.12/3.21 "to": 198, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 197, 9.12/3.21 "to": 199, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 198, 9.12/3.21 "to": 202, 9.12/3.21 "label": "EVAL with clause\nappend([], X18, X18).\nand substitutionT10 -> [],\nX9 -> [],\nX18 -> [],\nX19 -> [],\nT11 -> T13,\nT12 -> T14" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 198, 9.12/3.21 "to": 203, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 199, 9.12/3.21 "to": 204, 9.12/3.21 "label": "BACKTRACK\nfor clause: append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs)because of non-unification" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 202, 9.12/3.21 "to": 1, 9.12/3.21 "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> []\nT3 -> T14" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 205, 9.12/3.21 "to": 207, 9.12/3.21 "label": "CASE" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 207, 9.12/3.21 "to": 208, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 207, 9.12/3.21 "to": 209, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 208, 9.12/3.21 "to": 210, 9.12/3.21 "label": "EVAL with clause\nappend([], X42, X42).\nand substitutionT25 -> [],\nX33 -> T32,\nX42 -> T32,\nT23 -> T32,\nX43 -> T32,\nT26 -> T33,\nT27 -> T34" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 208, 9.12/3.21 "to": 211, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 209, 9.12/3.21 "to": 212, 9.12/3.21 "label": "EVAL with clause\nappend(.(X54, X55), X56, .(X54, X57)) :- append(X55, X56, X57).\nand substitutionX54 -> T41,\nX55 -> T44,\nT25 -> .(T41, T44),\nX33 -> X58,\nX56 -> X58,\nX57 -> T43,\nT23 -> .(T41, T43),\nT42 -> T44,\nT26 -> T45,\nT27 -> T46" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 209, 9.12/3.21 "to": 227, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 210, 9.12/3.21 "to": 1, 9.12/3.21 "label": "INSTANCE with matching:\nT1 -> T33\nT2 -> T32\nT3 -> T34" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 212, 9.12/3.21 "to": 228, 9.12/3.21 "label": "SPLIT 1" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 212, 9.12/3.21 "to": 229, 9.12/3.21 "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nT49 is ground\nT43 is ground\nreplacements:X58 -> T49,\nT45 -> T50,\nT46 -> T51" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 228, 9.12/3.21 "to": 230, 9.12/3.21 "label": "CASE" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 229, 9.12/3.21 "to": 1, 9.12/3.21 "label": "INSTANCE with matching:\nT1 -> T50\nT2 -> T49\nT3 -> T51" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 230, 9.12/3.21 "to": 231, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 230, 9.12/3.21 "to": 232, 9.12/3.21 "label": "PARALLEL" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 231, 9.12/3.21 "to": 233, 9.12/3.21 "label": "EVAL with clause\nappend([], X75, X75).\nand substitutionT44 -> [],\nX58 -> T58,\nX75 -> T58,\nT43 -> T58,\nX76 -> T58" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 231, 9.12/3.21 "to": 234, 9.12/3.21 "label": "EVAL-BACKTRACK" 9.12/3.21 }, 9.12/3.21 { 9.12/3.21 "from": 232, 9.12/3.21 "to": 242, 9.12/3.22 "label": "EVAL with clause\nappend(.(X87, X88), X89, .(X87, X90)) :- append(X88, X89, X90).\nand substitutionX87 -> T65,\nX88 -> T68,\nT44 -> .(T65, T68),\nX58 -> X91,\nX89 -> X91,\nX90 -> T67,\nT43 -> .(T65, T67),\nT66 -> T68" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 232, 9.12/3.22 "to": 243, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 233, 9.12/3.22 "to": 235, 9.12/3.22 "label": "SUCCESS" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 242, 9.12/3.22 "to": 228, 9.12/3.22 "label": "INSTANCE with matching:\nT44 -> T68\nX58 -> X91\nT43 -> T67" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "type": "Graph" 9.12/3.22 } 9.12/3.22 } 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (66) 9.12/3.22 Obligation: 9.12/3.22 Triples: 9.12/3.22 9.12/3.22 appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4). 9.12/3.22 flA(.([], X1), [], s(X2)) :- flA(X1, [], X2). 9.12/3.22 flA(.([], X1), X2, s(X3)) :- flA(X1, X2, X3). 9.12/3.22 flA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- appendB(X2, X6, X4). 9.12/3.22 flA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- ','(appendcB(X2, X6, X4), flA(X3, X6, X5)). 9.12/3.22 9.12/3.22 Clauses: 9.12/3.22 9.12/3.22 flcA([], [], 0). 9.12/3.22 flcA(.([], X1), [], s(X2)) :- flcA(X1, [], X2). 9.12/3.22 flcA(.([], X1), X2, s(X3)) :- flcA(X1, X2, X3). 9.12/3.22 flcA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- ','(appendcB(X2, X6, X4), flcA(X3, X6, X5)). 9.12/3.22 appendcB([], X1, X1). 9.12/3.22 appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4). 9.12/3.22 9.12/3.22 Afs: 9.12/3.22 9.12/3.22 flA(x1, x2, x3) = flA(x2) 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (67) TriplesToPiDPProof (SOUND) 9.12/3.22 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 9.12/3.22 9.12/3.22 flA_in_3: (f,b,f) 9.12/3.22 9.12/3.22 appendB_in_3: (f,f,b) 9.12/3.22 9.12/3.22 appendcB_in_3: (f,f,b) 9.12/3.22 9.12/3.22 Transforming TRIPLES into the following Term Rewriting System: 9.12/3.22 9.12/3.22 Pi DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(.([], X1), [], s(X2)) -> U2_AGA(X1, X2, flA_in_aga(X1, [], X2)) 9.12/3.22 FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) 9.12/3.22 FLA_IN_AGA(.([], X1), X2, s(X3)) -> U3_AGA(X1, X2, X3, flA_in_aga(X1, X2, X3)) 9.12/3.22 FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U4_AGA(X1, X2, X3, X4, X5, appendB_in_aag(X2, X6, X4)) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> APPENDB_IN_AAG(X2, X6, X4) 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendB_in_aag(X2, X3, X4)) 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) 9.12/3.22 U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> U6_AGA(X1, X2, X3, X4, X5, flA_in_aga(X3, X6, X5)) 9.12/3.22 U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) 9.12/3.22 U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 The argument filtering Pi contains the following mapping: 9.12/3.22 flA_in_aga(x1, x2, x3) = flA_in_aga(x2) 9.12/3.22 9.12/3.22 [] = [] 9.12/3.22 9.12/3.22 .(x1, x2) = .(x1, x2) 9.12/3.22 9.12/3.22 appendB_in_aag(x1, x2, x3) = appendB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) 9.12/3.22 9.12/3.22 U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) 9.12/3.22 9.12/3.22 FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) 9.12/3.22 9.12/3.22 U2_AGA(x1, x2, x3) = U2_AGA(x3) 9.12/3.22 9.12/3.22 U3_AGA(x1, x2, x3, x4) = U3_AGA(x2, x4) 9.12/3.22 9.12/3.22 U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) 9.12/3.22 9.12/3.22 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) 9.12/3.22 9.12/3.22 U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 U6_AGA(x1, x2, x3, x4, x5, x6) = U6_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 9.12/3.22 We have to consider all (P,R,Pi)-chains 9.12/3.22 9.12/3.22 9.12/3.22 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 9.12/3.22 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (68) 9.12/3.22 Obligation: 9.12/3.22 Pi DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(.([], X1), [], s(X2)) -> U2_AGA(X1, X2, flA_in_aga(X1, [], X2)) 9.12/3.22 FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) 9.12/3.22 FLA_IN_AGA(.([], X1), X2, s(X3)) -> U3_AGA(X1, X2, X3, flA_in_aga(X1, X2, X3)) 9.12/3.22 FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U4_AGA(X1, X2, X3, X4, X5, appendB_in_aag(X2, X6, X4)) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> APPENDB_IN_AAG(X2, X6, X4) 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendB_in_aag(X2, X3, X4)) 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) 9.12/3.22 U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> U6_AGA(X1, X2, X3, X4, X5, flA_in_aga(X3, X6, X5)) 9.12/3.22 U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) 9.12/3.22 U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 The argument filtering Pi contains the following mapping: 9.12/3.22 flA_in_aga(x1, x2, x3) = flA_in_aga(x2) 9.12/3.22 9.12/3.22 [] = [] 9.12/3.22 9.12/3.22 .(x1, x2) = .(x1, x2) 9.12/3.22 9.12/3.22 appendB_in_aag(x1, x2, x3) = appendB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) 9.12/3.22 9.12/3.22 U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) 9.12/3.22 9.12/3.22 FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) 9.12/3.22 9.12/3.22 U2_AGA(x1, x2, x3) = U2_AGA(x3) 9.12/3.22 9.12/3.22 U3_AGA(x1, x2, x3, x4) = U3_AGA(x2, x4) 9.12/3.22 9.12/3.22 U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) 9.12/3.22 9.12/3.22 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) 9.12/3.22 9.12/3.22 U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 U6_AGA(x1, x2, x3, x4, x5, x6) = U6_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 9.12/3.22 We have to consider all (P,R,Pi)-chains 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (69) DependencyGraphProof (EQUIVALENT) 9.12/3.22 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (70) 9.12/3.22 Complex Obligation (AND) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (71) 9.12/3.22 Obligation: 9.12/3.22 Pi DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) 9.12/3.22 U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 The argument filtering Pi contains the following mapping: 9.12/3.22 [] = [] 9.12/3.22 9.12/3.22 .(x1, x2) = .(x1, x2) 9.12/3.22 9.12/3.22 appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) 9.12/3.22 9.12/3.22 U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) 9.12/3.22 9.12/3.22 9.12/3.22 We have to consider all (P,R,Pi)-chains 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (72) UsableRulesProof (EQUIVALENT) 9.12/3.22 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (73) 9.12/3.22 Obligation: 9.12/3.22 Pi DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 The argument filtering Pi contains the following mapping: 9.12/3.22 .(x1, x2) = .(x1, x2) 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) 9.12/3.22 9.12/3.22 9.12/3.22 We have to consider all (P,R,Pi)-chains 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (74) PiDPToQDPProof (SOUND) 9.12/3.22 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (75) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 APPENDB_IN_AAG(.(X1, X4)) -> APPENDB_IN_AAG(X4) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (76) QDPSizeChangeProof (EQUIVALENT) 9.12/3.22 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. 9.12/3.22 9.12/3.22 From the DPs we obtained the following set of size-change graphs: 9.12/3.22 *APPENDB_IN_AAG(.(X1, X4)) -> APPENDB_IN_AAG(X4) 9.12/3.22 The graph contains the following edges 1 > 1 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (77) 9.12/3.22 YES 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (78) 9.12/3.22 Obligation: 9.12/3.22 Pi DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) 9.12/3.22 FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) 9.12/3.22 FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) 9.12/3.22 U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) 9.12/3.22 U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 The argument filtering Pi contains the following mapping: 9.12/3.22 [] = [] 9.12/3.22 9.12/3.22 .(x1, x2) = .(x1, x2) 9.12/3.22 9.12/3.22 appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) 9.12/3.22 9.12/3.22 appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) 9.12/3.22 9.12/3.22 U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) 9.12/3.22 9.12/3.22 FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) 9.12/3.22 9.12/3.22 U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) 9.12/3.22 9.12/3.22 9.12/3.22 We have to consider all (P,R,Pi)-chains 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (79) PiDPToQDPProof (SOUND) 9.12/3.22 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (80) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) 9.12/3.22 FLA_IN_AGA([]) -> FLA_IN_AGA([]) 9.12/3.22 FLA_IN_AGA(.(X1, X4)) -> U5_AGA(X1, X4, appendcB_in_aag(X4)) 9.12/3.22 U5_AGA(X1, X4, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X6) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag(X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 appendcB_in_aag(.(X1, X4)) -> U12_aag(X1, X4, appendcB_in_aag(X4)) 9.12/3.22 U12_aag(X1, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 The set Q consists of the following terms: 9.12/3.22 9.12/3.22 appendcB_in_aag(x0) 9.12/3.22 U12_aag(x0, x1, x2) 9.12/3.22 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (81) QDPQMonotonicMRRProof (EQUIVALENT) 9.12/3.22 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 9.12/3.22 9.12/3.22 Strictly oriented dependency pairs: 9.12/3.22 9.12/3.22 FLA_IN_AGA(.(X1, X4)) -> U5_AGA(X1, X4, appendcB_in_aag(X4)) 9.12/3.22 U5_AGA(X1, X4, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X6) 9.12/3.22 9.12/3.22 Strictly oriented rules of the TRS R: 9.12/3.22 9.12/3.22 appendcB_in_aag(.(X1, X4)) -> U12_aag(X1, X4, appendcB_in_aag(X4)) 9.12/3.22 U12_aag(X1, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) 9.12/3.22 9.12/3.22 Used ordering: Polynomial interpretation [POLO]: 9.12/3.22 9.12/3.22 POL(.(x_1, x_2)) = 2 + 2*x_2 9.12/3.22 POL(FLA_IN_AGA(x_1)) = 2 + 2*x_1 9.12/3.22 POL(U12_aag(x_1, x_2, x_3)) = 2*x_3 9.12/3.22 POL(U5_AGA(x_1, x_2, x_3)) = 2*x_3 9.12/3.22 POL([]) = 2 9.12/3.22 POL(appendcB_in_aag(x_1)) = 2 + 2*x_1 9.12/3.22 POL(appendcB_out_aag(x_1, x_2, x_3)) = 2 + 2*x_2 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (82) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) 9.12/3.22 FLA_IN_AGA([]) -> FLA_IN_AGA([]) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 appendcB_in_aag(X1) -> appendcB_out_aag([], X1, X1) 9.12/3.22 9.12/3.22 The set Q consists of the following terms: 9.12/3.22 9.12/3.22 appendcB_in_aag(x0) 9.12/3.22 U12_aag(x0, x1, x2) 9.12/3.22 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (83) UsableRulesProof (EQUIVALENT) 9.12/3.22 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. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (84) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) 9.12/3.22 FLA_IN_AGA([]) -> FLA_IN_AGA([]) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 The set Q consists of the following terms: 9.12/3.22 9.12/3.22 appendcB_in_aag(x0) 9.12/3.22 U12_aag(x0, x1, x2) 9.12/3.22 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (85) QReductionProof (EQUIVALENT) 9.12/3.22 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.12/3.22 9.12/3.22 appendcB_in_aag(x0) 9.12/3.22 U12_aag(x0, x1, x2) 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (86) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) 9.12/3.22 FLA_IN_AGA([]) -> FLA_IN_AGA([]) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (87) PrologToTRSTransformerProof (SOUND) 9.12/3.22 Transformed Prolog program to TRS. 9.12/3.22 9.12/3.22 { 9.12/3.22 "root": 2, 9.12/3.22 "program": { 9.12/3.22 "directives": [], 9.12/3.22 "clauses": [ 9.12/3.22 [ 9.12/3.22 "(fl ([]) ([]) (0))", 9.12/3.22 null 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(fl (. E X) R (s Z))", 9.12/3.22 "(',' (append E Y R) (fl X Y Z))" 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(append ([]) X X)", 9.12/3.22 null 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(append (. X Xs) Ys (. X Zs))", 9.12/3.22 "(append Xs Ys Zs)" 9.12/3.22 ] 9.12/3.22 ] 9.12/3.22 }, 9.12/3.22 "graph": { 9.12/3.22 "nodes": { 9.12/3.22 "78": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(true)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "14": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 0, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "15": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 1, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "type": "Nodes", 9.12/3.22 "220": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "2": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "200": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "201": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(fl T22 T21 T23)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T21"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "213": { 9.12/3.22 "goal": [ 9.12/3.22 { 9.12/3.22 "clause": 2, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "clause": 3, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "214": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 2, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "6": { 9.12/3.22 "goal": [ 9.12/3.22 { 9.12/3.22 "clause": 0, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "clause": 1, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "215": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 3, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "216": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(true)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "80": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "217": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "218": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "219": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(append T40 X47 T39)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T39"], 9.12/3.22 "free": ["X47"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "83": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "95": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(',' (append T16 X14 T14) (fl T17 X14 T18))" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "96": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "edges": [ 9.12/3.22 { 9.12/3.22 "from": 2, 9.12/3.22 "to": 6, 9.12/3.22 "label": "CASE" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 6, 9.12/3.22 "to": 14, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 6, 9.12/3.22 "to": 15, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 14, 9.12/3.22 "to": 78, 9.12/3.22 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 14, 9.12/3.22 "to": 80, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 15, 9.12/3.22 "to": 95, 9.12/3.22 "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T17,\nT1 -> .(T16, T17),\nT2 -> T14,\nX12 -> T14,\nX13 -> T18,\nT3 -> s(T18),\nT12 -> T16,\nT13 -> T17,\nT15 -> T18" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 15, 9.12/3.22 "to": 96, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 78, 9.12/3.22 "to": 83, 9.12/3.22 "label": "SUCCESS" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 95, 9.12/3.22 "to": 200, 9.12/3.22 "label": "SPLIT 1" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 95, 9.12/3.22 "to": 201, 9.12/3.22 "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 200, 9.12/3.22 "to": 213, 9.12/3.22 "label": "CASE" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 201, 9.12/3.22 "to": 2, 9.12/3.22 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 213, 9.12/3.22 "to": 214, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 213, 9.12/3.22 "to": 215, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 214, 9.12/3.22 "to": 216, 9.12/3.22 "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 214, 9.12/3.22 "to": 217, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 215, 9.12/3.22 "to": 219, 9.12/3.22 "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T37,\nX44 -> T40,\nT16 -> .(T37, T40),\nX14 -> X47,\nX45 -> X47,\nX46 -> T39,\nT14 -> .(T37, T39),\nT38 -> T40" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 215, 9.12/3.22 "to": 220, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 216, 9.12/3.22 "to": 218, 9.12/3.22 "label": "SUCCESS" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 219, 9.12/3.22 "to": 200, 9.12/3.22 "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "type": "Graph" 9.12/3.22 } 9.12/3.22 } 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (88) 9.12/3.22 Obligation: 9.12/3.22 Q restricted rewrite system: 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 f2_in([]) -> f2_out1([], 0) 9.12/3.22 f2_in(T14) -> U1(f95_in(T14), T14) 9.12/3.22 U1(f95_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) 9.12/3.22 f200_in(T30) -> f200_out1([], T30) 9.12/3.22 f200_in(.(T37, T39)) -> U2(f200_in(T39), .(T37, T39)) 9.12/3.22 U2(f200_out1(T40, X47), .(T37, T39)) -> f200_out1(.(T37, T40), X47) 9.12/3.22 f95_in(T14) -> U3(f200_in(T14), T14) 9.12/3.22 U3(f200_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) 9.12/3.22 U4(f2_out1(T22, T23), T14, T16, T21) -> f95_out1(T16, T21, T22, T23) 9.12/3.22 9.12/3.22 Q is empty. 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (89) DependencyPairsProof (EQUIVALENT) 9.12/3.22 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (90) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 F2_IN(T14) -> U1^1(f95_in(T14), T14) 9.12/3.22 F2_IN(T14) -> F95_IN(T14) 9.12/3.22 F200_IN(.(T37, T39)) -> U2^1(f200_in(T39), .(T37, T39)) 9.12/3.22 F200_IN(.(T37, T39)) -> F200_IN(T39) 9.12/3.22 F95_IN(T14) -> U3^1(f200_in(T14), T14) 9.12/3.22 F95_IN(T14) -> F200_IN(T14) 9.12/3.22 U3^1(f200_out1(T16, T21), T14) -> U4^1(f2_in(T21), T14, T16, T21) 9.12/3.22 U3^1(f200_out1(T16, T21), T14) -> F2_IN(T21) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 f2_in([]) -> f2_out1([], 0) 9.12/3.22 f2_in(T14) -> U1(f95_in(T14), T14) 9.12/3.22 U1(f95_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) 9.12/3.22 f200_in(T30) -> f200_out1([], T30) 9.12/3.22 f200_in(.(T37, T39)) -> U2(f200_in(T39), .(T37, T39)) 9.12/3.22 U2(f200_out1(T40, X47), .(T37, T39)) -> f200_out1(.(T37, T40), X47) 9.12/3.22 f95_in(T14) -> U3(f200_in(T14), T14) 9.12/3.22 U3(f200_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) 9.12/3.22 U4(f2_out1(T22, T23), T14, T16, T21) -> f95_out1(T16, T21, T22, T23) 9.12/3.22 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all minimal (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (91) DependencyGraphProof (EQUIVALENT) 9.12/3.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (92) 9.12/3.22 Complex Obligation (AND) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (93) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 F200_IN(.(T37, T39)) -> F200_IN(T39) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 f2_in([]) -> f2_out1([], 0) 9.12/3.22 f2_in(T14) -> U1(f95_in(T14), T14) 9.12/3.22 U1(f95_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) 9.12/3.22 f200_in(T30) -> f200_out1([], T30) 9.12/3.22 f200_in(.(T37, T39)) -> U2(f200_in(T39), .(T37, T39)) 9.12/3.22 U2(f200_out1(T40, X47), .(T37, T39)) -> f200_out1(.(T37, T40), X47) 9.12/3.22 f95_in(T14) -> U3(f200_in(T14), T14) 9.12/3.22 U3(f200_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) 9.12/3.22 U4(f2_out1(T22, T23), T14, T16, T21) -> f95_out1(T16, T21, T22, T23) 9.12/3.22 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all minimal (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (94) UsableRulesProof (EQUIVALENT) 9.12/3.22 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (95) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 F200_IN(.(T37, T39)) -> F200_IN(T39) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all minimal (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (96) QDPSizeChangeProof (EQUIVALENT) 9.12/3.22 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. 9.12/3.22 9.12/3.22 From the DPs we obtained the following set of size-change graphs: 9.12/3.22 *F200_IN(.(T37, T39)) -> F200_IN(T39) 9.12/3.22 The graph contains the following edges 1 > 1 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (97) 9.12/3.22 YES 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (98) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 F2_IN(T14) -> F95_IN(T14) 9.12/3.22 F95_IN(T14) -> U3^1(f200_in(T14), T14) 9.12/3.22 U3^1(f200_out1(T16, T21), T14) -> F2_IN(T21) 9.12/3.22 9.12/3.22 The TRS R consists of the following rules: 9.12/3.22 9.12/3.22 f2_in([]) -> f2_out1([], 0) 9.12/3.22 f2_in(T14) -> U1(f95_in(T14), T14) 9.12/3.22 U1(f95_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) 9.12/3.22 f200_in(T30) -> f200_out1([], T30) 9.12/3.22 f200_in(.(T37, T39)) -> U2(f200_in(T39), .(T37, T39)) 9.12/3.22 U2(f200_out1(T40, X47), .(T37, T39)) -> f200_out1(.(T37, T40), X47) 9.12/3.22 f95_in(T14) -> U3(f200_in(T14), T14) 9.12/3.22 U3(f200_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) 9.12/3.22 U4(f2_out1(T22, T23), T14, T16, T21) -> f95_out1(T16, T21, T22, T23) 9.12/3.22 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all minimal (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (99) NonTerminationLoopProof (COMPLETE) 9.12/3.22 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 9.12/3.22 Found a loop by narrowing to the left: 9.12/3.22 9.12/3.22 s = F95_IN(T14) evaluates to t =F95_IN(T14) 9.12/3.22 9.12/3.22 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 9.12/3.22 * Matcher: [ ] 9.12/3.22 * Semiunifier: [ ] 9.12/3.22 9.12/3.22 -------------------------------------------------------------------------------- 9.12/3.22 Rewriting sequence 9.12/3.22 9.12/3.22 F95_IN(T14) -> U3^1(f200_in(T14), T14) 9.12/3.22 with rule F95_IN(T14') -> U3^1(f200_in(T14'), T14') at position [] and matcher [T14' / T14] 9.12/3.22 9.12/3.22 U3^1(f200_in(T14), T14) -> U3^1(f200_out1([], T14), T14) 9.12/3.22 with rule f200_in(T30) -> f200_out1([], T30) at position [0] and matcher [T30 / T14] 9.12/3.22 9.12/3.22 U3^1(f200_out1([], T14), T14) -> F2_IN(T14) 9.12/3.22 with rule U3^1(f200_out1(T16, T21), T14') -> F2_IN(T21) at position [] and matcher [T16 / [], T21 / T14, T14' / T14] 9.12/3.22 9.12/3.22 F2_IN(T14) -> F95_IN(T14) 9.12/3.22 with rule F2_IN(T14) -> F95_IN(T14) 9.12/3.22 9.12/3.22 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 9.12/3.22 9.12/3.22 9.12/3.22 All these steps are and every following step will be a correct step w.r.t to Q. 9.12/3.22 9.12/3.22 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (100) 9.12/3.22 NO 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (101) PrologToIRSwTTransformerProof (SOUND) 9.12/3.22 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 9.12/3.22 9.12/3.22 { 9.12/3.22 "root": 3, 9.12/3.22 "program": { 9.12/3.22 "directives": [], 9.12/3.22 "clauses": [ 9.12/3.22 [ 9.12/3.22 "(fl ([]) ([]) (0))", 9.12/3.22 null 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(fl (. E X) R (s Z))", 9.12/3.22 "(',' (append E Y R) (fl X Y Z))" 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(append ([]) X X)", 9.12/3.22 null 9.12/3.22 ], 9.12/3.22 [ 9.12/3.22 "(append (. X Xs) Ys (. X Zs))", 9.12/3.22 "(append Xs Ys Zs)" 9.12/3.22 ] 9.12/3.22 ] 9.12/3.22 }, 9.12/3.22 "graph": { 9.12/3.22 "nodes": { 9.12/3.22 "13": { 9.12/3.22 "goal": [ 9.12/3.22 { 9.12/3.22 "clause": 0, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "clause": 1, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "190": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "181": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "182": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(fl T22 T21 T23)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T21"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "type": "Nodes", 9.12/3.22 "172": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(',' (append T16 X14 T14) (fl T17 X14 T18))" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "183": { 9.12/3.22 "goal": [ 9.12/3.22 { 9.12/3.22 "clause": 2, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "clause": 3, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "184": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 2, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "185": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 3, 9.12/3.22 "scope": 2, 9.12/3.22 "term": "(append T16 X14 T14)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T14"], 9.12/3.22 "free": ["X14"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "175": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "186": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(true)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "187": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "188": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "189": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(append T40 X47 T39)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T39"], 9.12/3.22 "free": ["X47"], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "3": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "107": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": -1, 9.12/3.22 "scope": -1, 9.12/3.22 "term": "(true)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "108": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "109": { 9.12/3.22 "goal": [], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": [], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "97": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 0, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "98": { 9.12/3.22 "goal": [{ 9.12/3.22 "clause": 1, 9.12/3.22 "scope": 1, 9.12/3.22 "term": "(fl T1 T2 T3)" 9.12/3.22 }], 9.12/3.22 "kb": { 9.12/3.22 "nonunifying": [], 9.12/3.22 "intvars": {}, 9.12/3.22 "arithmetic": { 9.12/3.22 "type": "PlainIntegerRelationState", 9.12/3.22 "relations": [] 9.12/3.22 }, 9.12/3.22 "ground": ["T2"], 9.12/3.22 "free": [], 9.12/3.22 "exprvars": [] 9.12/3.22 } 9.12/3.22 } 9.12/3.22 }, 9.12/3.22 "edges": [ 9.12/3.22 { 9.12/3.22 "from": 3, 9.12/3.22 "to": 13, 9.12/3.22 "label": "CASE" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 13, 9.12/3.22 "to": 97, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 13, 9.12/3.22 "to": 98, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 97, 9.12/3.22 "to": 107, 9.12/3.22 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 97, 9.12/3.22 "to": 108, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 98, 9.12/3.22 "to": 172, 9.12/3.22 "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T17,\nT1 -> .(T16, T17),\nT2 -> T14,\nX12 -> T14,\nX13 -> T18,\nT3 -> s(T18),\nT12 -> T16,\nT13 -> T17,\nT15 -> T18" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 98, 9.12/3.22 "to": 175, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 107, 9.12/3.22 "to": 109, 9.12/3.22 "label": "SUCCESS" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 172, 9.12/3.22 "to": 181, 9.12/3.22 "label": "SPLIT 1" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 172, 9.12/3.22 "to": 182, 9.12/3.22 "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 181, 9.12/3.22 "to": 183, 9.12/3.22 "label": "CASE" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 182, 9.12/3.22 "to": 3, 9.12/3.22 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 183, 9.12/3.22 "to": 184, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 183, 9.12/3.22 "to": 185, 9.12/3.22 "label": "PARALLEL" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 184, 9.12/3.22 "to": 186, 9.12/3.22 "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 184, 9.12/3.22 "to": 187, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 185, 9.12/3.22 "to": 189, 9.12/3.22 "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T37,\nX44 -> T40,\nT16 -> .(T37, T40),\nX14 -> X47,\nX45 -> X47,\nX46 -> T39,\nT14 -> .(T37, T39),\nT38 -> T40" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 185, 9.12/3.22 "to": 190, 9.12/3.22 "label": "EVAL-BACKTRACK" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 186, 9.12/3.22 "to": 188, 9.12/3.22 "label": "SUCCESS" 9.12/3.22 }, 9.12/3.22 { 9.12/3.22 "from": 189, 9.12/3.22 "to": 181, 9.12/3.22 "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" 9.12/3.22 } 9.12/3.22 ], 9.12/3.22 "type": "Graph" 9.12/3.22 } 9.12/3.22 } 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (102) 9.12/3.22 Complex Obligation (AND) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (103) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f181_out(x) -> f189_out(x) :|: TRUE 9.12/3.22 f185_in(.(x1, x2)) -> f189_in(x2) :|: TRUE 9.12/3.22 f189_out(x3) -> f185_out(.(x4, x3)) :|: TRUE 9.12/3.22 f185_in(T14) -> f190_in :|: TRUE 9.12/3.22 f190_out -> f185_out(x5) :|: TRUE 9.12/3.22 f183_in(x6) -> f185_in(x6) :|: TRUE 9.12/3.22 f183_in(x7) -> f184_in(x7) :|: TRUE 9.12/3.22 f184_out(x8) -> f183_out(x8) :|: TRUE 9.12/3.22 f185_out(x9) -> f183_out(x9) :|: TRUE 9.12/3.22 f183_out(x10) -> f181_out(x10) :|: TRUE 9.12/3.22 f181_in(x11) -> f183_in(x11) :|: TRUE 9.12/3.22 f3_in(T2) -> f13_in(T2) :|: TRUE 9.12/3.22 f13_out(x12) -> f3_out(x12) :|: TRUE 9.12/3.22 f98_out(x13) -> f13_out(x13) :|: TRUE 9.12/3.22 f13_in(x14) -> f97_in(x14) :|: TRUE 9.12/3.22 f97_out(x15) -> f13_out(x15) :|: TRUE 9.12/3.22 f13_in(x16) -> f98_in(x16) :|: TRUE 9.12/3.22 f175_out -> f98_out(x17) :|: TRUE 9.12/3.22 f98_in(x18) -> f172_in(x18) :|: TRUE 9.12/3.22 f98_in(x19) -> f175_in :|: TRUE 9.12/3.22 f172_out(x20) -> f98_out(x20) :|: TRUE 9.12/3.22 f172_in(x21) -> f181_in(x21) :|: TRUE 9.12/3.22 f182_out(x22) -> f172_out(x23) :|: TRUE 9.12/3.22 f181_out(x24) -> f182_in(x25) :|: TRUE 9.12/3.22 Start term: f3_in(T2) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (104) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 9.12/3.22 Constructed simple dependency graph. 9.12/3.22 9.12/3.22 Simplified to the following IRSwTs: 9.12/3.22 9.12/3.22 intTRSProblem: 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f185_in(.(x1, x2)) -> f189_in(x2) :|: TRUE 9.12/3.22 f183_in(x6) -> f185_in(x6) :|: TRUE 9.12/3.22 f181_in(x11) -> f183_in(x11) :|: TRUE 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (105) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f185_in(.(x1, x2)) -> f189_in(x2) :|: TRUE 9.12/3.22 f183_in(x6) -> f185_in(x6) :|: TRUE 9.12/3.22 f181_in(x11) -> f183_in(x11) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (106) IntTRSCompressionProof (EQUIVALENT) 9.12/3.22 Compressed rules. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (107) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(.(x1:0, x2:0)) -> f183_in(x2:0) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (108) IRSFormatTransformerProof (EQUIVALENT) 9.12/3.22 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (109) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(.(x1:0, x2:0)) -> f183_in(x2:0) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (110) IRSwTTerminationDigraphProof (EQUIVALENT) 9.12/3.22 Constructed termination digraph! 9.12/3.22 Nodes: 9.12/3.22 (1) f183_in(.(x1:0, x2:0)) -> f183_in(x2:0) :|: TRUE 9.12/3.22 9.12/3.22 Arcs: 9.12/3.22 (1) -> (1) 9.12/3.22 9.12/3.22 This digraph is fully evaluated! 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (111) 9.12/3.22 Obligation: 9.12/3.22 9.12/3.22 Termination digraph: 9.12/3.22 Nodes: 9.12/3.22 (1) f183_in(.(x1:0, x2:0)) -> f183_in(x2:0) :|: TRUE 9.12/3.22 9.12/3.22 Arcs: 9.12/3.22 (1) -> (1) 9.12/3.22 9.12/3.22 This digraph is fully evaluated! 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (112) IntTRSUnneededArgumentFilterProof (EQUIVALENT) 9.12/3.22 Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: 9.12/3.22 9.12/3.22 .(x1, x2) -> .(x2) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (113) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(.(x2:0)) -> f183_in(x2:0) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (114) TempFilterProof (SOUND) 9.12/3.22 Used the following sort dictionary for filtering: 9.12/3.22 f183_in(VARIABLE) 9.12/3.22 .(VARIABLE) 9.12/3.22 Removed predefined arithmetic. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (115) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(.(x2:0)) -> f183_in(x2:0) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (116) IRSwTToQDPProof (SOUND) 9.12/3.22 Removed the integers and created a QDP-Problem. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (117) 9.12/3.22 Obligation: 9.12/3.22 Q DP problem: 9.12/3.22 The TRS P consists of the following rules: 9.12/3.22 9.12/3.22 f183_in(.(x2:0)) -> f183_in(x2:0) 9.12/3.22 9.12/3.22 R is empty. 9.12/3.22 Q is empty. 9.12/3.22 We have to consider all (P,Q,R)-chains. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (118) QDPSizeChangeProof (EQUIVALENT) 9.12/3.22 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. 9.12/3.22 9.12/3.22 From the DPs we obtained the following set of size-change graphs: 9.12/3.22 *f183_in(.(x2:0)) -> f183_in(x2:0) 9.12/3.22 The graph contains the following edges 1 > 1 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (119) 9.12/3.22 YES 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (120) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f3_in(T2) -> f13_in(T2) :|: TRUE 9.12/3.22 f13_out(x) -> f3_out(x) :|: TRUE 9.12/3.22 f186_in -> f186_out :|: TRUE 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f181_out(x1) -> f189_out(x1) :|: TRUE 9.12/3.22 f3_out(T21) -> f182_out(T21) :|: TRUE 9.12/3.22 f182_in(x2) -> f3_in(x2) :|: TRUE 9.12/3.22 f184_in(T30) -> f186_in :|: TRUE 9.12/3.22 f186_out -> f184_out(x3) :|: TRUE 9.12/3.22 f187_out -> f184_out(T14) :|: TRUE 9.12/3.22 f184_in(x4) -> f187_in :|: TRUE 9.12/3.22 f175_out -> f98_out(x5) :|: TRUE 9.12/3.22 f98_in(x6) -> f172_in(x6) :|: TRUE 9.12/3.22 f98_in(x7) -> f175_in :|: TRUE 9.12/3.22 f172_out(x8) -> f98_out(x8) :|: TRUE 9.12/3.22 f172_in(x9) -> f181_in(x9) :|: TRUE 9.12/3.22 f182_out(x10) -> f172_out(x11) :|: TRUE 9.12/3.22 f181_out(x12) -> f182_in(x13) :|: TRUE 9.12/3.22 f98_out(x14) -> f13_out(x14) :|: TRUE 9.12/3.22 f13_in(x15) -> f97_in(x15) :|: TRUE 9.12/3.22 f97_out(x16) -> f13_out(x16) :|: TRUE 9.12/3.22 f13_in(x17) -> f98_in(x17) :|: TRUE 9.12/3.22 f185_in(.(x18, x19)) -> f189_in(x19) :|: TRUE 9.12/3.22 f189_out(x20) -> f185_out(.(x21, x20)) :|: TRUE 9.12/3.22 f185_in(x22) -> f190_in :|: TRUE 9.12/3.22 f190_out -> f185_out(x23) :|: TRUE 9.12/3.22 f183_out(x24) -> f181_out(x24) :|: TRUE 9.12/3.22 f181_in(x25) -> f183_in(x25) :|: TRUE 9.12/3.22 f183_in(x26) -> f185_in(x26) :|: TRUE 9.12/3.22 f183_in(x27) -> f184_in(x27) :|: TRUE 9.12/3.22 f184_out(x28) -> f183_out(x28) :|: TRUE 9.12/3.22 f185_out(x29) -> f183_out(x29) :|: TRUE 9.12/3.22 Start term: f3_in(T2) 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (121) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 9.12/3.22 Constructed simple dependency graph. 9.12/3.22 9.12/3.22 Simplified to the following IRSwTs: 9.12/3.22 9.12/3.22 intTRSProblem: 9.12/3.22 f3_in(T2) -> f13_in(T2) :|: TRUE 9.12/3.22 f186_in -> f186_out :|: TRUE 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f181_out(x1) -> f189_out(x1) :|: TRUE 9.12/3.22 f182_in(x2) -> f3_in(x2) :|: TRUE 9.12/3.22 f184_in(T30) -> f186_in :|: TRUE 9.12/3.22 f186_out -> f184_out(x3) :|: TRUE 9.12/3.22 f98_in(x6) -> f172_in(x6) :|: TRUE 9.12/3.22 f172_in(x9) -> f181_in(x9) :|: TRUE 9.12/3.22 f181_out(x12) -> f182_in(x13) :|: TRUE 9.12/3.22 f13_in(x17) -> f98_in(x17) :|: TRUE 9.12/3.22 f185_in(.(x18, x19)) -> f189_in(x19) :|: TRUE 9.12/3.22 f189_out(x20) -> f185_out(.(x21, x20)) :|: TRUE 9.12/3.22 f183_out(x24) -> f181_out(x24) :|: TRUE 9.12/3.22 f181_in(x25) -> f183_in(x25) :|: TRUE 9.12/3.22 f183_in(x26) -> f185_in(x26) :|: TRUE 9.12/3.22 f183_in(x27) -> f184_in(x27) :|: TRUE 9.12/3.22 f184_out(x28) -> f183_out(x28) :|: TRUE 9.12/3.22 f185_out(x29) -> f183_out(x29) :|: TRUE 9.12/3.22 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (122) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f3_in(T2) -> f13_in(T2) :|: TRUE 9.12/3.22 f186_in -> f186_out :|: TRUE 9.12/3.22 f189_in(T39) -> f181_in(T39) :|: TRUE 9.12/3.22 f181_out(x1) -> f189_out(x1) :|: TRUE 9.12/3.22 f182_in(x2) -> f3_in(x2) :|: TRUE 9.12/3.22 f184_in(T30) -> f186_in :|: TRUE 9.12/3.22 f186_out -> f184_out(x3) :|: TRUE 9.12/3.22 f98_in(x6) -> f172_in(x6) :|: TRUE 9.12/3.22 f172_in(x9) -> f181_in(x9) :|: TRUE 9.12/3.22 f181_out(x12) -> f182_in(x13) :|: TRUE 9.12/3.22 f13_in(x17) -> f98_in(x17) :|: TRUE 9.12/3.22 f185_in(.(x18, x19)) -> f189_in(x19) :|: TRUE 9.12/3.22 f189_out(x20) -> f185_out(.(x21, x20)) :|: TRUE 9.12/3.22 f183_out(x24) -> f181_out(x24) :|: TRUE 9.12/3.22 f181_in(x25) -> f183_in(x25) :|: TRUE 9.12/3.22 f183_in(x26) -> f185_in(x26) :|: TRUE 9.12/3.22 f183_in(x27) -> f184_in(x27) :|: TRUE 9.12/3.22 f184_out(x28) -> f183_out(x28) :|: TRUE 9.12/3.22 f185_out(x29) -> f183_out(x29) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (123) IntTRSCompressionProof (EQUIVALENT) 9.12/3.22 Compressed rules. 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (124) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(x27:0) -> f183_out(x3:0) :|: TRUE 9.12/3.22 f183_out(x24:0) -> f183_out(.(x21:0, x24:0)) :|: TRUE 9.12/3.22 f183_out(x) -> f183_in(x1) :|: TRUE 9.12/3.22 f183_in(.(x18:0, x19:0)) -> f183_in(x19:0) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (125) IRSFormatTransformerProof (EQUIVALENT) 9.12/3.22 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (126) 9.12/3.22 Obligation: 9.12/3.22 Rules: 9.12/3.22 f183_in(x27:0) -> f183_out(x3:0) :|: TRUE 9.12/3.22 f183_out(x24:0) -> f183_out(.(x21:0, x24:0)) :|: TRUE 9.12/3.22 f183_out(x) -> f183_in(x1) :|: TRUE 9.12/3.22 f183_in(.(x18:0, x19:0)) -> f183_in(x19:0) :|: TRUE 9.12/3.22 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (127) IRSwTTerminationDigraphProof (EQUIVALENT) 9.12/3.22 Constructed termination digraph! 9.12/3.22 Nodes: 9.12/3.22 (1) f183_in(x27:0) -> f183_out(x3:0) :|: TRUE 9.12/3.22 (2) f183_out(x24:0) -> f183_out(.(x21:0, x24:0)) :|: TRUE 9.12/3.22 (3) f183_out(x) -> f183_in(x1) :|: TRUE 9.12/3.22 (4) f183_in(.(x18:0, x19:0)) -> f183_in(x19:0) :|: TRUE 9.12/3.22 9.12/3.22 Arcs: 9.12/3.22 (1) -> (2), (3) 9.12/3.22 (2) -> (2), (3) 9.12/3.22 (3) -> (1), (4) 9.12/3.22 (4) -> (1), (4) 9.12/3.22 9.12/3.22 This digraph is fully evaluated! 9.12/3.22 ---------------------------------------- 9.12/3.22 9.12/3.22 (128) 9.12/3.22 Obligation: 9.12/3.22 9.12/3.22 Termination digraph: 9.12/3.22 Nodes: 9.12/3.22 (1) f183_in(x27:0) -> f183_out(x3:0) :|: TRUE 9.12/3.22 (2) f183_in(.(x18:0, x19:0)) -> f183_in(x19:0) :|: TRUE 9.12/3.22 (3) f183_out(x) -> f183_in(x1) :|: TRUE 9.12/3.22 (4) f183_out(x24:0) -> f183_out(.(x21:0, x24:0)) :|: TRUE 9.12/3.22 9.12/3.22 Arcs: 9.12/3.22 (1) -> (3), (4) 9.12/3.22 (2) -> (1), (2) 9.12/3.22 (3) -> (1), (2) 9.12/3.22 (4) -> (3), (4) 9.12/3.22 9.12/3.22 This digraph is fully evaluated! 9.26/3.29 EOF