5.51/2.24 MAYBE 5.51/2.26 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.51/2.26 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.51/2.26 5.51/2.26 5.51/2.26 Left Termination of the query pattern 5.51/2.26 5.51/2.26 append3(a,a,a,g) 5.51/2.26 5.51/2.26 w.r.t. the given Prolog program could not be shown: 5.51/2.26 5.51/2.26 (0) Prolog 5.51/2.26 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.51/2.26 (2) PiTRS 5.51/2.26 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.51/2.26 (4) PiDP 5.51/2.26 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (6) AND 5.51/2.26 (7) PiDP 5.51/2.26 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (9) PiDP 5.51/2.26 (10) PiDPToQDPProof [SOUND, 0 ms] 5.51/2.26 (11) QDP 5.51/2.26 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.51/2.26 (13) YES 5.51/2.26 (14) PiDP 5.51/2.26 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (16) PiDP 5.51/2.26 (17) PiDPToQDPProof [SOUND, 0 ms] 5.51/2.26 (18) QDP 5.51/2.26 (19) PrologToPiTRSProof [SOUND, 0 ms] 5.51/2.26 (20) PiTRS 5.51/2.26 (21) DependencyPairsProof [EQUIVALENT, 0 ms] 5.51/2.26 (22) PiDP 5.51/2.26 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (24) AND 5.51/2.26 (25) PiDP 5.51/2.26 (26) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (27) PiDP 5.51/2.26 (28) PiDPToQDPProof [SOUND, 0 ms] 5.51/2.26 (29) QDP 5.51/2.26 (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.51/2.26 (31) YES 5.51/2.26 (32) PiDP 5.51/2.26 (33) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (34) PiDP 5.51/2.26 (35) PiDPToQDPProof [SOUND, 0 ms] 5.51/2.26 (36) QDP 5.51/2.26 (37) PrologToTRSTransformerProof [SOUND, 0 ms] 5.51/2.26 (38) QTRS 5.51/2.26 (39) QTRSRRRProof [EQUIVALENT, 91 ms] 5.51/2.26 (40) QTRS 5.51/2.26 (41) QTRSRRRProof [EQUIVALENT, 0 ms] 5.51/2.26 (42) QTRS 5.51/2.26 (43) PrologToDTProblemTransformerProof [SOUND, 0 ms] 5.51/2.26 (44) TRIPLES 5.51/2.26 (45) TriplesToPiDPProof [SOUND, 0 ms] 5.51/2.26 (46) PiDP 5.51/2.26 (47) DependencyGraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (48) AND 5.51/2.26 (49) PiDP 5.51/2.26 (50) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (51) PiDP 5.51/2.26 (52) PiDPToQDPProof [SOUND, 0 ms] 5.51/2.26 (53) QDP 5.51/2.26 (54) PiDP 5.51/2.26 (55) UsableRulesProof [EQUIVALENT, 0 ms] 5.51/2.26 (56) PiDP 5.51/2.26 (57) PrologToIRSwTTransformerProof [SOUND, 16 ms] 5.51/2.26 (58) AND 5.51/2.26 (59) IRSwT 5.51/2.26 (60) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (61) TRUE 5.51/2.26 (62) IRSwT 5.51/2.26 (63) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (64) IRSwT 5.51/2.26 (65) IntTRSCompressionProof [EQUIVALENT, 21 ms] 5.51/2.26 (66) IRSwT 5.51/2.26 (67) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.51/2.26 (68) IRSwT 5.51/2.26 (69) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 5.51/2.26 (70) IRSwT 5.51/2.26 (71) FilterProof [EQUIVALENT, 0 ms] 5.51/2.26 (72) IntTRS 5.51/2.26 (73) IntTRSPeriodicNontermProof [COMPLETE, 6 ms] 5.51/2.26 (74) NO 5.51/2.26 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (0) 5.51/2.26 Obligation: 5.51/2.26 Clauses: 5.51/2.26 5.51/2.26 append([], L, L). 5.51/2.26 append(.(H, L1), L2, .(H, L3)) :- append(L1, L2, L3). 5.51/2.26 append3(A, B, C, D) :- ','(append(A, B, E), append(E, C, D)). 5.51/2.26 5.51/2.26 5.51/2.26 Query: append3(a,a,a,g) 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (1) PrologToPiTRSProof (SOUND) 5.51/2.26 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.51/2.26 5.51/2.26 append3_in_4: (f,f,f,b) 5.51/2.26 5.51/2.26 append_in_3: (f,f,f) (f,f,b) 5.51/2.26 5.51/2.26 Transforming Prolog into the following Term Rewriting System: 5.51/2.26 5.51/2.26 Pi-finite rewrite system: 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 5.51/2.26 5.51/2.26 5.51/2.26 5.51/2.26 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.51/2.26 5.51/2.26 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (2) 5.51/2.26 Obligation: 5.51/2.26 Pi-finite rewrite system: 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (3) DependencyPairsProof (EQUIVALENT) 5.51/2.26 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.51/2.26 Pi DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND3_IN_AAAG(A, B, C, D) -> U2_AAAG(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 APPEND3_IN_AAAG(A, B, C, D) -> APPEND_IN_AAA(A, B, E) 5.51/2.26 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.26 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> U3_AAAG(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> APPEND_IN_AAG(E, C, D) 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> U1_AAG(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.26 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 APPEND3_IN_AAAG(x1, x2, x3, x4) = APPEND3_IN_AAAG(x4) 5.51/2.26 5.51/2.26 U2_AAAG(x1, x2, x3, x4, x5) = U2_AAAG(x4, x5) 5.51/2.26 5.51/2.26 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.26 5.51/2.26 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 5.51/2.26 5.51/2.26 U3_AAAG(x1, x2, x3, x4, x5) = U3_AAAG(x1, x4, x5) 5.51/2.26 5.51/2.26 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.26 5.51/2.26 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 5.51/2.26 5.51/2.26 5.51/2.26 We have to consider all (P,R,Pi)-chains 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (4) 5.51/2.26 Obligation: 5.51/2.26 Pi DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND3_IN_AAAG(A, B, C, D) -> U2_AAAG(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 APPEND3_IN_AAAG(A, B, C, D) -> APPEND_IN_AAA(A, B, E) 5.51/2.26 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.26 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> U3_AAAG(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> APPEND_IN_AAG(E, C, D) 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> U1_AAG(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.26 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 APPEND3_IN_AAAG(x1, x2, x3, x4) = APPEND3_IN_AAAG(x4) 5.51/2.26 5.51/2.26 U2_AAAG(x1, x2, x3, x4, x5) = U2_AAAG(x4, x5) 5.51/2.26 5.51/2.26 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.26 5.51/2.26 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 5.51/2.26 5.51/2.26 U3_AAAG(x1, x2, x3, x4, x5) = U3_AAAG(x1, x4, x5) 5.51/2.26 5.51/2.26 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.26 5.51/2.26 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 5.51/2.26 5.51/2.26 5.51/2.26 We have to consider all (P,R,Pi)-chains 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (5) DependencyGraphProof (EQUIVALENT) 5.51/2.26 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (6) 5.51/2.26 Complex Obligation (AND) 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (7) 5.51/2.26 Obligation: 5.51/2.26 Pi DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.26 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.26 5.51/2.26 5.51/2.26 We have to consider all (P,R,Pi)-chains 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (8) UsableRulesProof (EQUIVALENT) 5.51/2.26 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (9) 5.51/2.26 Obligation: 5.51/2.26 Pi DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.26 5.51/2.26 R is empty. 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.26 5.51/2.26 5.51/2.26 We have to consider all (P,R,Pi)-chains 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (10) PiDPToQDPProof (SOUND) 5.51/2.26 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (11) 5.51/2.26 Obligation: 5.51/2.26 Q DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND_IN_AAG(.(L3)) -> APPEND_IN_AAG(L3) 5.51/2.26 5.51/2.26 R is empty. 5.51/2.26 Q is empty. 5.51/2.26 We have to consider all (P,Q,R)-chains. 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (12) QDPSizeChangeProof (EQUIVALENT) 5.51/2.26 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. 5.51/2.26 5.51/2.26 From the DPs we obtained the following set of size-change graphs: 5.51/2.26 *APPEND_IN_AAG(.(L3)) -> APPEND_IN_AAG(L3) 5.51/2.26 The graph contains the following edges 1 > 1 5.51/2.26 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (13) 5.51/2.26 YES 5.51/2.26 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (14) 5.51/2.26 Obligation: 5.51/2.26 Pi DP problem: 5.51/2.26 The TRS P consists of the following rules: 5.51/2.26 5.51/2.26 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.26 5.51/2.26 The TRS R consists of the following rules: 5.51/2.26 5.51/2.26 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.26 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.26 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.26 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.26 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.26 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.26 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.26 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.26 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.26 5.51/2.26 The argument filtering Pi contains the following mapping: 5.51/2.26 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.26 5.51/2.26 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.26 5.51/2.26 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.26 5.51/2.26 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.26 5.51/2.26 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.26 5.51/2.26 .(x1, x2) = .(x2) 5.51/2.26 5.51/2.26 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x4, x5) 5.51/2.26 5.51/2.26 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.26 5.51/2.26 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) 5.51/2.26 5.51/2.26 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 5.51/2.26 5.51/2.26 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3, x4) 5.51/2.26 5.51/2.26 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.26 5.51/2.26 5.51/2.26 We have to consider all (P,R,Pi)-chains 5.51/2.26 ---------------------------------------- 5.51/2.26 5.51/2.26 (15) UsableRulesProof (EQUIVALENT) 5.51/2.26 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.27 ---------------------------------------- 5.51/2.27 5.51/2.27 (16) 5.51/2.27 Obligation: 5.51/2.27 Pi DP problem: 5.51/2.27 The TRS P consists of the following rules: 5.51/2.27 5.51/2.27 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.27 5.51/2.27 R is empty. 5.51/2.27 The argument filtering Pi contains the following mapping: 5.51/2.27 .(x1, x2) = .(x2) 5.51/2.27 5.51/2.27 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.27 5.51/2.27 5.51/2.27 We have to consider all (P,R,Pi)-chains 5.51/2.27 ---------------------------------------- 5.51/2.27 5.51/2.27 (17) PiDPToQDPProof (SOUND) 5.51/2.27 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.51/2.27 ---------------------------------------- 5.51/2.27 5.51/2.27 (18) 5.51/2.27 Obligation: 5.51/2.27 Q DP problem: 5.51/2.27 The TRS P consists of the following rules: 5.51/2.27 5.51/2.27 APPEND_IN_AAA -> APPEND_IN_AAA 5.51/2.27 5.51/2.27 R is empty. 5.51/2.27 Q is empty. 5.51/2.27 We have to consider all (P,Q,R)-chains. 5.51/2.27 ---------------------------------------- 5.51/2.27 5.51/2.27 (19) PrologToPiTRSProof (SOUND) 5.51/2.27 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.51/2.27 5.51/2.27 append3_in_4: (f,f,f,b) 5.51/2.27 5.51/2.27 append_in_3: (f,f,f) (f,f,b) 5.51/2.27 5.51/2.27 Transforming Prolog into the following Term Rewriting System: 5.51/2.27 5.51/2.27 Pi-finite rewrite system: 5.51/2.27 The TRS R consists of the following rules: 5.51/2.27 5.51/2.27 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.27 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.27 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.27 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.27 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.27 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.27 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.27 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.27 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.27 5.51/2.27 The argument filtering Pi contains the following mapping: 5.51/2.27 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.27 5.51/2.27 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.27 5.51/2.27 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.27 5.51/2.27 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.27 5.51/2.27 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.27 5.51/2.27 .(x1, x2) = .(x2) 5.51/2.27 5.51/2.27 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.27 5.51/2.27 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.27 5.51/2.27 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.27 5.51/2.27 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.27 5.51/2.27 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.27 5.51/2.27 5.51/2.27 5.51/2.27 5.51/2.27 5.51/2.27 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.51/2.27 5.51/2.27 5.51/2.27 5.51/2.27 ---------------------------------------- 5.51/2.27 5.51/2.27 (20) 5.51/2.27 Obligation: 5.51/2.27 Pi-finite rewrite system: 5.51/2.27 The TRS R consists of the following rules: 5.51/2.27 5.51/2.27 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.27 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.27 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.27 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.28 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.28 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.28 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.28 5.51/2.28 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.28 5.51/2.28 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.28 5.51/2.28 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.28 5.51/2.28 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.28 5.51/2.28 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.28 5.51/2.28 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.28 5.51/2.28 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.28 5.51/2.28 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (21) DependencyPairsProof (EQUIVALENT) 5.51/2.28 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND3_IN_AAAG(A, B, C, D) -> U2_AAAG(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 APPEND3_IN_AAAG(A, B, C, D) -> APPEND_IN_AAA(A, B, E) 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.28 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> U3_AAAG(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> APPEND_IN_AAG(E, C, D) 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> U1_AAG(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.28 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.28 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.28 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.28 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.28 5.51/2.28 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.28 5.51/2.28 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.28 5.51/2.28 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.28 5.51/2.28 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.28 5.51/2.28 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.28 5.51/2.28 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.28 5.51/2.28 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.28 5.51/2.28 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.28 5.51/2.28 APPEND3_IN_AAAG(x1, x2, x3, x4) = APPEND3_IN_AAAG(x4) 5.51/2.28 5.51/2.28 U2_AAAG(x1, x2, x3, x4, x5) = U2_AAAG(x4, x5) 5.51/2.28 5.51/2.28 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.28 5.51/2.28 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 5.51/2.28 5.51/2.28 U3_AAAG(x1, x2, x3, x4, x5) = U3_AAAG(x1, x5) 5.51/2.28 5.51/2.28 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.28 5.51/2.28 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x5) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (22) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND3_IN_AAAG(A, B, C, D) -> U2_AAAG(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 APPEND3_IN_AAAG(A, B, C, D) -> APPEND_IN_AAA(A, B, E) 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.28 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> U3_AAAG(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 U2_AAAG(A, B, C, D, append_out_aaa(A, B, E)) -> APPEND_IN_AAG(E, C, D) 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> U1_AAG(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.28 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.28 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.28 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.28 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.28 5.51/2.28 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.28 5.51/2.28 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.28 5.51/2.28 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.28 5.51/2.28 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.28 5.51/2.28 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.28 5.51/2.28 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.28 5.51/2.28 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.28 5.51/2.28 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.28 5.51/2.28 APPEND3_IN_AAAG(x1, x2, x3, x4) = APPEND3_IN_AAAG(x4) 5.51/2.28 5.51/2.28 U2_AAAG(x1, x2, x3, x4, x5) = U2_AAAG(x4, x5) 5.51/2.28 5.51/2.28 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.28 5.51/2.28 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 5.51/2.28 5.51/2.28 U3_AAAG(x1, x2, x3, x4, x5) = U3_AAAG(x1, x5) 5.51/2.28 5.51/2.28 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.28 5.51/2.28 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x5) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (23) DependencyGraphProof (EQUIVALENT) 5.51/2.28 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (24) 5.51/2.28 Complex Obligation (AND) 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (25) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.28 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.28 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.28 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.28 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.28 5.51/2.28 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.28 5.51/2.28 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.28 5.51/2.28 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.28 5.51/2.28 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.28 5.51/2.28 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.28 5.51/2.28 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.28 5.51/2.28 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.28 5.51/2.28 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.28 5.51/2.28 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (26) UsableRulesProof (EQUIVALENT) 5.51/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (27) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAG(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAG(L1, L2, L3) 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (28) PiDPToQDPProof (SOUND) 5.51/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (29) 5.51/2.28 Obligation: 5.51/2.28 Q DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAG(.(L3)) -> APPEND_IN_AAG(L3) 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 Q is empty. 5.51/2.28 We have to consider all (P,Q,R)-chains. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (30) QDPSizeChangeProof (EQUIVALENT) 5.51/2.28 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. 5.51/2.28 5.51/2.28 From the DPs we obtained the following set of size-change graphs: 5.51/2.28 *APPEND_IN_AAG(.(L3)) -> APPEND_IN_AAG(L3) 5.51/2.28 The graph contains the following edges 1 > 1 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (31) 5.51/2.28 YES 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (32) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 append3_in_aaag(A, B, C, D) -> U2_aaag(A, B, C, D, append_in_aaa(A, B, E)) 5.51/2.28 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 5.51/2.28 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 5.51/2.28 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 5.51/2.28 U2_aaag(A, B, C, D, append_out_aaa(A, B, E)) -> U3_aaag(A, B, C, D, append_in_aag(E, C, D)) 5.51/2.28 append_in_aag([], L, L) -> append_out_aag([], L, L) 5.51/2.28 append_in_aag(.(H, L1), L2, .(H, L3)) -> U1_aag(H, L1, L2, L3, append_in_aag(L1, L2, L3)) 5.51/2.28 U1_aag(H, L1, L2, L3, append_out_aag(L1, L2, L3)) -> append_out_aag(.(H, L1), L2, .(H, L3)) 5.51/2.28 U3_aaag(A, B, C, D, append_out_aag(E, C, D)) -> append3_out_aaag(A, B, C, D) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 append3_in_aaag(x1, x2, x3, x4) = append3_in_aaag(x4) 5.51/2.28 5.51/2.28 U2_aaag(x1, x2, x3, x4, x5) = U2_aaag(x4, x5) 5.51/2.28 5.51/2.28 append_in_aaa(x1, x2, x3) = append_in_aaa 5.51/2.28 5.51/2.28 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 5.51/2.28 5.51/2.28 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 U3_aaag(x1, x2, x3, x4, x5) = U3_aaag(x1, x5) 5.51/2.28 5.51/2.28 append_in_aag(x1, x2, x3) = append_in_aag(x3) 5.51/2.28 5.51/2.28 append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) 5.51/2.28 5.51/2.28 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 5.51/2.28 5.51/2.28 append3_out_aaag(x1, x2, x3, x4) = append3_out_aaag(x1, x3) 5.51/2.28 5.51/2.28 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (33) UsableRulesProof (EQUIVALENT) 5.51/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (34) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (35) PiDPToQDPProof (SOUND) 5.51/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (36) 5.51/2.28 Obligation: 5.51/2.28 Q DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND_IN_AAA -> APPEND_IN_AAA 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 Q is empty. 5.51/2.28 We have to consider all (P,Q,R)-chains. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (37) PrologToTRSTransformerProof (SOUND) 5.51/2.28 Transformed Prolog program to TRS. 5.51/2.28 5.51/2.28 { 5.51/2.28 "root": 19, 5.51/2.28 "program": { 5.51/2.28 "directives": [], 5.51/2.28 "clauses": [ 5.51/2.28 [ 5.51/2.28 "(append ([]) L L)", 5.51/2.28 null 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append (. H L1) L2 (. H L3))", 5.51/2.28 "(append L1 L2 L3)" 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append3 A B C D)", 5.51/2.28 "(',' (append A B E) (append E C D))" 5.51/2.28 ] 5.51/2.28 ] 5.51/2.28 }, 5.51/2.28 "graph": { 5.51/2.28 "nodes": { 5.51/2.28 "22": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 2, 5.51/2.28 "scope": 1, 5.51/2.28 "term": "(append3 T1 T2 T3 T4)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T4"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "19": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append3 T1 T2 T3 T4)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T4"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "193": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "type": "Nodes", 5.51/2.28 "194": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "195": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "196": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "240": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(true)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "197": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "241": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "198": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(true)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "242": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "199": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "243": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T68 T69 T67)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T67"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "200": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "244": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "201": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T45 T46 X40)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X40"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "202": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "237": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "238": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "239": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "85": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(',' (append T22 T23 X16) (append X16 T24 T21))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "edges": [ 5.51/2.28 { 5.51/2.28 "from": 19, 5.51/2.28 "to": 22, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 22, 5.51/2.28 "to": 85, 5.51/2.28 "label": "ONLY EVAL with clause\nappend3(X12, X13, X14, X15) :- ','(append(X12, X13, X16), append(X16, X14, X15)).\nand substitutionT1 -> T22,\nX12 -> T22,\nT2 -> T23,\nX13 -> T23,\nT3 -> T24,\nX14 -> T24,\nT4 -> T21,\nX15 -> T21,\nT18 -> T22,\nT19 -> T23,\nT20 -> T24" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 85, 5.51/2.28 "to": 193, 5.51/2.28 "label": "SPLIT 1" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 85, 5.51/2.28 "to": 194, 5.51/2.28 "label": "SPLIT 2\nreplacements:X16 -> T27,\nT24 -> T28" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 193, 5.51/2.28 "to": 195, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 194, 5.51/2.28 "to": 237, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 195, 5.51/2.28 "to": 196, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 195, 5.51/2.28 "to": 197, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 196, 5.51/2.28 "to": 198, 5.51/2.28 "label": "EVAL with clause\nappend([], X25, X25).\nand substitutionT22 -> [],\nT23 -> T35,\nX25 -> T35,\nX16 -> T35" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 196, 5.51/2.28 "to": 199, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 197, 5.51/2.28 "to": 201, 5.51/2.28 "label": "EVAL with clause\nappend(.(X36, X37), X38, .(X36, X39)) :- append(X37, X38, X39).\nand substitutionX36 -> T42,\nX37 -> T45,\nT22 -> .(T42, T45),\nT23 -> T46,\nX38 -> T46,\nX39 -> X40,\nX16 -> .(T42, X40),\nT43 -> T45,\nT44 -> T46" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 197, 5.51/2.28 "to": 202, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 198, 5.51/2.28 "to": 200, 5.51/2.28 "label": "SUCCESS" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 201, 5.51/2.28 "to": 193, 5.51/2.28 "label": "INSTANCE with matching:\nT22 -> T45\nT23 -> T46\nX16 -> X40" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 237, 5.51/2.28 "to": 238, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 237, 5.51/2.28 "to": 239, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 238, 5.51/2.28 "to": 240, 5.51/2.28 "label": "EVAL with clause\nappend([], X49, X49).\nand substitutionT27 -> [],\nT28 -> T55,\nX49 -> T55,\nT21 -> T55" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 238, 5.51/2.28 "to": 241, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 239, 5.51/2.28 "to": 243, 5.51/2.28 "label": "EVAL with clause\nappend(.(X58, X59), X60, .(X58, X61)) :- append(X59, X60, X61).\nand substitutionX58 -> T64,\nX59 -> T68,\nT27 -> .(T64, T68),\nT28 -> T69,\nX60 -> T69,\nX61 -> T67,\nT21 -> .(T64, T67),\nT65 -> T68,\nT66 -> T69" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 239, 5.51/2.28 "to": 244, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 240, 5.51/2.28 "to": 242, 5.51/2.28 "label": "SUCCESS" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 243, 5.51/2.28 "to": 194, 5.51/2.28 "label": "INSTANCE with matching:\nT27 -> T68\nT28 -> T69\nT21 -> T67" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "type": "Graph" 5.51/2.28 } 5.51/2.28 } 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (38) 5.51/2.28 Obligation: 5.51/2.28 Q restricted rewrite system: 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 f19_in(T21) -> U1(f85_in(T21), T21) 5.51/2.28 U1(f85_out1(X16, T24), T21) -> f19_out1(T24) 5.51/2.28 f193_in -> f193_out1 5.51/2.28 f193_in -> U2(f193_in) 5.51/2.28 U2(f193_out1) -> f193_out1 5.51/2.28 f194_in(T55) -> f194_out1([], T55) 5.51/2.28 f194_in(.(T64, T67)) -> U3(f194_in(T67), .(T64, T67)) 5.51/2.28 U3(f194_out1(T68, T69), .(T64, T67)) -> f194_out1(.(T64, T68), T69) 5.51/2.28 f85_in(T21) -> U4(f193_in, T21) 5.51/2.28 U4(f193_out1, T21) -> U5(f194_in(T21), T21) 5.51/2.28 U5(f194_out1(T27, T28), T21) -> f85_out1(T27, T28) 5.51/2.28 5.51/2.28 Q is empty. 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (39) QTRSRRRProof (EQUIVALENT) 5.51/2.28 Used ordering: 5.51/2.28 f19_in/1(YES) 5.51/2.28 U1/2(YES,YES) 5.51/2.28 f85_in/1(YES) 5.51/2.28 f85_out1/2(YES,YES) 5.51/2.28 f19_out1/1)YES( 5.51/2.28 f193_in/0) 5.51/2.28 f193_out1/0) 5.51/2.28 U2/1)YES( 5.51/2.28 f194_in/1(YES) 5.51/2.28 f194_out1/2(YES,YES) 5.51/2.28 []/0) 5.51/2.28 ./2(YES,YES) 5.51/2.28 U3/2(YES,YES) 5.51/2.28 U4/2(YES,YES) 5.51/2.28 U5/2(YES,YES) 5.51/2.28 5.51/2.28 Quasi precedence: 5.51/2.28 f19_in_1 > U1_2 5.51/2.28 f19_in_1 > [f85_in_1, f193_in] > f193_out1 5.51/2.28 f19_in_1 > [f85_in_1, f193_in] > [f194_in_1, U4_2] > [] 5.51/2.28 f19_in_1 > [f85_in_1, f193_in] > [f194_in_1, U4_2] > [._2, U3_2] > f194_out1_2 5.51/2.28 f19_in_1 > [f85_in_1, f193_in] > [f194_in_1, U4_2] > U5_2 > f85_out1_2 5.51/2.28 5.51/2.28 5.51/2.28 Status: 5.51/2.28 f19_in_1: multiset status 5.51/2.28 U1_2: multiset status 5.51/2.28 f85_in_1: [1] 5.51/2.28 f85_out1_2: multiset status 5.51/2.28 f193_in: multiset status 5.51/2.28 f193_out1: multiset status 5.51/2.28 f194_in_1: multiset status 5.51/2.28 f194_out1_2: multiset status 5.51/2.28 []: multiset status 5.51/2.28 ._2: multiset status 5.51/2.28 U3_2: multiset status 5.51/2.28 U4_2: multiset status 5.51/2.28 U5_2: multiset status 5.51/2.28 5.51/2.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.51/2.28 5.51/2.28 f19_in(T21) -> U1(f85_in(T21), T21) 5.51/2.28 U1(f85_out1(X16, T24), T21) -> f19_out1(T24) 5.51/2.28 f193_in -> f193_out1 5.51/2.28 f194_in(T55) -> f194_out1([], T55) 5.51/2.28 f194_in(.(T64, T67)) -> U3(f194_in(T67), .(T64, T67)) 5.51/2.28 U3(f194_out1(T68, T69), .(T64, T67)) -> f194_out1(.(T64, T68), T69) 5.51/2.28 f85_in(T21) -> U4(f193_in, T21) 5.51/2.28 U4(f193_out1, T21) -> U5(f194_in(T21), T21) 5.51/2.28 U5(f194_out1(T27, T28), T21) -> f85_out1(T27, T28) 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (40) 5.51/2.28 Obligation: 5.51/2.28 Q restricted rewrite system: 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 f193_in -> U2(f193_in) 5.51/2.28 U2(f193_out1) -> f193_out1 5.51/2.28 5.51/2.28 Q is empty. 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (41) QTRSRRRProof (EQUIVALENT) 5.51/2.28 Used ordering: 5.51/2.28 Polynomial interpretation [POLO]: 5.51/2.28 5.51/2.28 POL(U2(x_1)) = 2*x_1 5.51/2.28 POL(f193_in) = 0 5.51/2.28 POL(f193_out1) = 1 5.51/2.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.51/2.28 5.51/2.28 U2(f193_out1) -> f193_out1 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (42) 5.51/2.28 Obligation: 5.51/2.28 Q restricted rewrite system: 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 f193_in -> U2(f193_in) 5.51/2.28 5.51/2.28 Q is empty. 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (43) PrologToDTProblemTransformerProof (SOUND) 5.51/2.28 Built DT problem from termination graph DT10. 5.51/2.28 5.51/2.28 { 5.51/2.28 "root": 2, 5.51/2.28 "program": { 5.51/2.28 "directives": [], 5.51/2.28 "clauses": [ 5.51/2.28 [ 5.51/2.28 "(append ([]) L L)", 5.51/2.28 null 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append (. H L1) L2 (. H L3))", 5.51/2.28 "(append L1 L2 L3)" 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append3 A B C D)", 5.51/2.28 "(',' (append A B E) (append E C D))" 5.51/2.28 ] 5.51/2.28 ] 5.51/2.28 }, 5.51/2.28 "graph": { 5.51/2.28 "nodes": { 5.51/2.28 "170": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(',' (append T13 T14 X9) (append X9 T15 T12))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": ["X9"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "171": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(',' (append T13 T14 X9) (append X9 T15 T12))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": ["X9"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "type": "Nodes", 5.51/2.28 "172": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T21 T22 T12)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "173": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "230": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "234": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T80 T81 X74)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X74"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "235": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "216": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(',' (append T55 T56 X50) (append (. T58 X50) T57 T12))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": ["X50"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "217": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "219": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T55 T56 X50)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X50"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "182": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T21 T22 T12)" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T21 T22 T12)" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "183": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T21 T22 T12)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "184": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 3, 5.51/2.28 "term": "(append T21 T22 T12)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "185": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(true)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "186": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "187": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "220": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append (. T62 T61) T63 T12)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "188": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T42 T43 T41)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T41"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "2": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append3 T1 T2 T3 T4)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T4"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "189": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "222": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 4, 5.51/2.28 "term": "(append T55 T56 X50)" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 4, 5.51/2.28 "term": "(append T55 T56 X50)" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X50"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "223": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 4, 5.51/2.28 "term": "(append T55 T56 X50)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X50"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "4": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 2, 5.51/2.28 "scope": 1, 5.51/2.28 "term": "(append3 T1 T2 T3 T4)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T4"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "169": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(',' (append T13 T14 X9) (append X9 T15 T12))" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(',' (append T13 T14 X9) (append X9 T15 T12))" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": ["X9"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "224": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 4, 5.51/2.28 "term": "(append T55 T56 X50)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X50"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "80": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(',' (append T13 T14 X9) (append X9 T15 T12))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T12"], 5.51/2.28 "free": ["X9"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "228": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(true)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "229": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "edges": [ 5.51/2.28 { 5.51/2.28 "from": 2, 5.51/2.28 "to": 4, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 4, 5.51/2.28 "to": 80, 5.51/2.28 "label": "ONLY EVAL with clause\nappend3(X5, X6, X7, X8) :- ','(append(X5, X6, X9), append(X9, X7, X8)).\nand substitutionT1 -> T13,\nX5 -> T13,\nT2 -> T14,\nX6 -> T14,\nT3 -> T15,\nX7 -> T15,\nT4 -> T12,\nX8 -> T12,\nT9 -> T13,\nT10 -> T14,\nT11 -> T15" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 80, 5.51/2.28 "to": 169, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 169, 5.51/2.28 "to": 170, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 169, 5.51/2.28 "to": 171, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 170, 5.51/2.28 "to": 172, 5.51/2.28 "label": "EVAL with clause\nappend([], X14, X14).\nand substitutionT13 -> [],\nT14 -> T21,\nX14 -> T21,\nX9 -> T21,\nT20 -> T21,\nT15 -> T22" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 170, 5.51/2.28 "to": 173, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 171, 5.51/2.28 "to": 216, 5.51/2.28 "label": "EVAL with clause\nappend(.(X46, X47), X48, .(X46, X49)) :- append(X47, X48, X49).\nand substitutionX46 -> T58,\nX47 -> T55,\nT13 -> .(T58, T55),\nT14 -> T56,\nX48 -> T56,\nX49 -> X50,\nX9 -> .(T58, X50),\nT53 -> T55,\nT54 -> T56,\nT15 -> T57,\nT52 -> T58" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 171, 5.51/2.28 "to": 217, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 172, 5.51/2.28 "to": 182, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 182, 5.51/2.28 "to": 183, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 182, 5.51/2.28 "to": 184, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 183, 5.51/2.28 "to": 185, 5.51/2.28 "label": "EVAL with clause\nappend([], X21, X21).\nand substitutionT21 -> [],\nT22 -> T29,\nX21 -> T29,\nT12 -> T29" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 183, 5.51/2.28 "to": 186, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 184, 5.51/2.28 "to": 188, 5.51/2.28 "label": "EVAL with clause\nappend(.(X30, X31), X32, .(X30, X33)) :- append(X31, X32, X33).\nand substitutionX30 -> T38,\nX31 -> T42,\nT21 -> .(T38, T42),\nT22 -> T43,\nX32 -> T43,\nX33 -> T41,\nT12 -> .(T38, T41),\nT39 -> T42,\nT40 -> T43" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 184, 5.51/2.28 "to": 189, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 185, 5.51/2.28 "to": 187, 5.51/2.28 "label": "SUCCESS" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 188, 5.51/2.28 "to": 172, 5.51/2.28 "label": "INSTANCE with matching:\nT21 -> T42\nT22 -> T43\nT12 -> T41" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 216, 5.51/2.28 "to": 219, 5.51/2.28 "label": "SPLIT 1" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 216, 5.51/2.28 "to": 220, 5.51/2.28 "label": "SPLIT 2\nreplacements:X50 -> T61,\nT58 -> T62,\nT57 -> T63" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 219, 5.51/2.28 "to": 222, 5.51/2.28 "label": "CASE" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 220, 5.51/2.28 "to": 172, 5.51/2.28 "label": "INSTANCE with matching:\nT21 -> .(T62, T61)\nT22 -> T63" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 222, 5.51/2.28 "to": 223, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 222, 5.51/2.28 "to": 224, 5.51/2.28 "label": "PARALLEL" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 223, 5.51/2.28 "to": 228, 5.51/2.28 "label": "EVAL with clause\nappend([], X59, X59).\nand substitutionT55 -> [],\nT56 -> T70,\nX59 -> T70,\nX50 -> T70" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 223, 5.51/2.28 "to": 229, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 224, 5.51/2.28 "to": 234, 5.51/2.28 "label": "EVAL with clause\nappend(.(X70, X71), X72, .(X70, X73)) :- append(X71, X72, X73).\nand substitutionX70 -> T77,\nX71 -> T80,\nT55 -> .(T77, T80),\nT56 -> T81,\nX72 -> T81,\nX73 -> X74,\nX50 -> .(T77, X74),\nT78 -> T80,\nT79 -> T81" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 224, 5.51/2.28 "to": 235, 5.51/2.28 "label": "EVAL-BACKTRACK" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 228, 5.51/2.28 "to": 230, 5.51/2.28 "label": "SUCCESS" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "from": 234, 5.51/2.28 "to": 219, 5.51/2.28 "label": "INSTANCE with matching:\nT55 -> T80\nT56 -> T81\nX50 -> X74" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "type": "Graph" 5.51/2.28 } 5.51/2.28 } 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (44) 5.51/2.28 Obligation: 5.51/2.28 Triples: 5.51/2.28 5.51/2.28 appendA(.(X1, X2), X3, .(X1, X4)) :- appendA(X2, X3, X4). 5.51/2.28 appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4). 5.51/2.28 append3C([], X1, X2, X3) :- appendA(X1, X2, X3). 5.51/2.28 append3C(.(X1, X2), X3, X4, X5) :- appendB(X2, X3, X6). 5.51/2.28 append3C(.(X1, X2), X3, X4, X5) :- ','(appendcB(X2, X3, X6), appendA(.(X1, X6), X4, X5)). 5.51/2.28 5.51/2.28 Clauses: 5.51/2.28 5.51/2.28 appendcA([], X1, X1). 5.51/2.28 appendcA(.(X1, X2), X3, .(X1, X4)) :- appendcA(X2, X3, X4). 5.51/2.28 appendcB([], X1, X1). 5.51/2.28 appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4). 5.51/2.28 5.51/2.28 Afs: 5.51/2.28 5.51/2.28 append3C(x1, x2, x3, x4) = append3C(x4) 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (45) TriplesToPiDPProof (SOUND) 5.51/2.28 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.51/2.28 5.51/2.28 append3C_in_4: (f,f,f,b) 5.51/2.28 5.51/2.28 appendA_in_3: (f,f,b) 5.51/2.28 5.51/2.28 appendB_in_3: (f,f,f) 5.51/2.28 5.51/2.28 appendcB_in_3: (f,f,f) 5.51/2.28 5.51/2.28 Transforming TRIPLES into the following Term Rewriting System: 5.51/2.28 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND3C_IN_AAAG([], X1, X2, X3) -> U3_AAAG(X1, X2, X3, appendA_in_aag(X1, X2, X3)) 5.51/2.28 APPEND3C_IN_AAAG([], X1, X2, X3) -> APPENDA_IN_AAG(X1, X2, X3) 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> U4_AAAG(X1, X2, X3, X4, X5, appendB_in_aaa(X2, X3, X6)) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> APPENDB_IN_AAA(X2, X3, X6) 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> U2_AAA(X1, X2, X3, X4, appendB_in_aaa(X2, X3, X4)) 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAA(X2, X3, X4) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> U5_AAAG(X1, X2, X3, X4, X5, appendcB_in_aaa(X2, X3, X6)) 5.51/2.28 U5_AAAG(X1, X2, X3, X4, X5, appendcB_out_aaa(X2, X3, X6)) -> U6_AAAG(X1, X2, X3, X4, X5, appendA_in_aag(.(X1, X6), X4, X5)) 5.51/2.28 U5_AAAG(X1, X2, X3, X4, X5, appendcB_out_aaa(X2, X3, X6)) -> APPENDA_IN_AAG(.(X1, X6), X4, X5) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 appendcB_in_aaa([], X1, X1) -> appendcB_out_aaa([], X1, X1) 5.51/2.28 appendcB_in_aaa(.(X1, X2), X3, .(X1, X4)) -> U9_aaa(X1, X2, X3, X4, appendcB_in_aaa(X2, X3, X4)) 5.51/2.28 U9_aaa(X1, X2, X3, X4, appendcB_out_aaa(X2, X3, X4)) -> appendcB_out_aaa(.(X1, X2), X3, .(X1, X4)) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 appendB_in_aaa(x1, x2, x3) = appendB_in_aaa 5.51/2.28 5.51/2.28 appendcB_in_aaa(x1, x2, x3) = appendcB_in_aaa 5.51/2.28 5.51/2.28 appendcB_out_aaa(x1, x2, x3) = appendcB_out_aaa(x1) 5.51/2.28 5.51/2.28 U9_aaa(x1, x2, x3, x4, x5) = U9_aaa(x5) 5.51/2.28 5.51/2.28 [] = [] 5.51/2.28 5.51/2.28 APPEND3C_IN_AAAG(x1, x2, x3, x4) = APPEND3C_IN_AAAG(x4) 5.51/2.28 5.51/2.28 U3_AAAG(x1, x2, x3, x4) = U3_AAAG(x3, x4) 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 5.51/2.28 5.51/2.28 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 5.51/2.28 5.51/2.28 U4_AAAG(x1, x2, x3, x4, x5, x6) = U4_AAAG(x5, x6) 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(x1, x2, x3) = APPENDB_IN_AAA 5.51/2.28 5.51/2.28 U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) 5.51/2.28 5.51/2.28 U5_AAAG(x1, x2, x3, x4, x5, x6) = U5_AAAG(x5, x6) 5.51/2.28 5.51/2.28 U6_AAAG(x1, x2, x3, x4, x5, x6) = U6_AAAG(x2, x5, x6) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 5.51/2.28 5.51/2.28 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 5.51/2.28 5.51/2.28 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (46) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPEND3C_IN_AAAG([], X1, X2, X3) -> U3_AAAG(X1, X2, X3, appendA_in_aag(X1, X2, X3)) 5.51/2.28 APPEND3C_IN_AAAG([], X1, X2, X3) -> APPENDA_IN_AAG(X1, X2, X3) 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> U4_AAAG(X1, X2, X3, X4, X5, appendB_in_aaa(X2, X3, X6)) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> APPENDB_IN_AAA(X2, X3, X6) 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> U2_AAA(X1, X2, X3, X4, appendB_in_aaa(X2, X3, X4)) 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAA(X2, X3, X4) 5.51/2.28 APPEND3C_IN_AAAG(.(X1, X2), X3, X4, X5) -> U5_AAAG(X1, X2, X3, X4, X5, appendcB_in_aaa(X2, X3, X6)) 5.51/2.28 U5_AAAG(X1, X2, X3, X4, X5, appendcB_out_aaa(X2, X3, X6)) -> U6_AAAG(X1, X2, X3, X4, X5, appendA_in_aag(.(X1, X6), X4, X5)) 5.51/2.28 U5_AAAG(X1, X2, X3, X4, X5, appendcB_out_aaa(X2, X3, X6)) -> APPENDA_IN_AAG(.(X1, X6), X4, X5) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 appendcB_in_aaa([], X1, X1) -> appendcB_out_aaa([], X1, X1) 5.51/2.28 appendcB_in_aaa(.(X1, X2), X3, .(X1, X4)) -> U9_aaa(X1, X2, X3, X4, appendcB_in_aaa(X2, X3, X4)) 5.51/2.28 U9_aaa(X1, X2, X3, X4, appendcB_out_aaa(X2, X3, X4)) -> appendcB_out_aaa(.(X1, X2), X3, .(X1, X4)) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) 5.51/2.28 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 appendB_in_aaa(x1, x2, x3) = appendB_in_aaa 5.51/2.28 5.51/2.28 appendcB_in_aaa(x1, x2, x3) = appendcB_in_aaa 5.51/2.28 5.51/2.28 appendcB_out_aaa(x1, x2, x3) = appendcB_out_aaa(x1) 5.51/2.28 5.51/2.28 U9_aaa(x1, x2, x3, x4, x5) = U9_aaa(x5) 5.51/2.28 5.51/2.28 [] = [] 5.51/2.28 5.51/2.28 APPEND3C_IN_AAAG(x1, x2, x3, x4) = APPEND3C_IN_AAAG(x4) 5.51/2.28 5.51/2.28 U3_AAAG(x1, x2, x3, x4) = U3_AAAG(x3, x4) 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 5.51/2.28 5.51/2.28 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 5.51/2.28 5.51/2.28 U4_AAAG(x1, x2, x3, x4, x5, x6) = U4_AAAG(x5, x6) 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(x1, x2, x3) = APPENDB_IN_AAA 5.51/2.28 5.51/2.28 U2_AAA(x1, x2, x3, x4, x5) = U2_AAA(x5) 5.51/2.28 5.51/2.28 U5_AAAG(x1, x2, x3, x4, x5, x6) = U5_AAAG(x5, x6) 5.51/2.28 5.51/2.28 U6_AAAG(x1, x2, x3, x4, x5, x6) = U6_AAAG(x2, x5, x6) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (47) DependencyGraphProof (EQUIVALENT) 5.51/2.28 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 9 less nodes. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (48) 5.51/2.28 Complex Obligation (AND) 5.51/2.28 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (49) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAA(X2, X3, X4) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 appendcB_in_aaa([], X1, X1) -> appendcB_out_aaa([], X1, X1) 5.51/2.28 appendcB_in_aaa(.(X1, X2), X3, .(X1, X4)) -> U9_aaa(X1, X2, X3, X4, appendcB_in_aaa(X2, X3, X4)) 5.51/2.28 U9_aaa(X1, X2, X3, X4, appendcB_out_aaa(X2, X3, X4)) -> appendcB_out_aaa(.(X1, X2), X3, .(X1, X4)) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 appendcB_in_aaa(x1, x2, x3) = appendcB_in_aaa 5.51/2.28 5.51/2.28 appendcB_out_aaa(x1, x2, x3) = appendcB_out_aaa(x1) 5.51/2.28 5.51/2.28 U9_aaa(x1, x2, x3, x4, x5) = U9_aaa(x5) 5.51/2.28 5.51/2.28 [] = [] 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(x1, x2, x3) = APPENDB_IN_AAA 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (50) UsableRulesProof (EQUIVALENT) 5.51/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (51) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAA(X2, X3, X4) 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 APPENDB_IN_AAA(x1, x2, x3) = APPENDB_IN_AAA 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (52) PiDPToQDPProof (SOUND) 5.51/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (53) 5.51/2.28 Obligation: 5.51/2.28 Q DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPENDB_IN_AAA -> APPENDB_IN_AAA 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 Q is empty. 5.51/2.28 We have to consider all (P,Q,R)-chains. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (54) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 5.51/2.28 5.51/2.28 The TRS R consists of the following rules: 5.51/2.28 5.51/2.28 appendcB_in_aaa([], X1, X1) -> appendcB_out_aaa([], X1, X1) 5.51/2.28 appendcB_in_aaa(.(X1, X2), X3, .(X1, X4)) -> U9_aaa(X1, X2, X3, X4, appendcB_in_aaa(X2, X3, X4)) 5.51/2.28 U9_aaa(X1, X2, X3, X4, appendcB_out_aaa(X2, X3, X4)) -> appendcB_out_aaa(.(X1, X2), X3, .(X1, X4)) 5.51/2.28 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 appendcB_in_aaa(x1, x2, x3) = appendcB_in_aaa 5.51/2.28 5.51/2.28 appendcB_out_aaa(x1, x2, x3) = appendcB_out_aaa(x1) 5.51/2.28 5.51/2.28 U9_aaa(x1, x2, x3, x4, x5) = U9_aaa(x5) 5.51/2.28 5.51/2.28 [] = [] 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (55) UsableRulesProof (EQUIVALENT) 5.51/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (56) 5.51/2.28 Obligation: 5.51/2.28 Pi DP problem: 5.51/2.28 The TRS P consists of the following rules: 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 5.51/2.28 5.51/2.28 R is empty. 5.51/2.28 The argument filtering Pi contains the following mapping: 5.51/2.28 .(x1, x2) = .(x2) 5.51/2.28 5.51/2.28 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 5.51/2.28 5.51/2.28 5.51/2.28 We have to consider all (P,R,Pi)-chains 5.51/2.28 ---------------------------------------- 5.51/2.28 5.51/2.28 (57) PrologToIRSwTTransformerProof (SOUND) 5.51/2.28 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 5.51/2.28 5.51/2.28 { 5.51/2.28 "root": 10, 5.51/2.28 "program": { 5.51/2.28 "directives": [], 5.51/2.28 "clauses": [ 5.51/2.28 [ 5.51/2.28 "(append ([]) L L)", 5.51/2.28 null 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append (. H L1) L2 (. H L3))", 5.51/2.28 "(append L1 L2 L3)" 5.51/2.28 ], 5.51/2.28 [ 5.51/2.28 "(append3 A B C D)", 5.51/2.28 "(',' (append A B E) (append E C D))" 5.51/2.28 ] 5.51/2.28 ] 5.51/2.28 }, 5.51/2.28 "graph": { 5.51/2.28 "nodes": { 5.51/2.28 "11": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": 2, 5.51/2.28 "scope": 1, 5.51/2.28 "term": "(append3 T1 T2 T3 T4)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T4"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "190": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "191": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(append T27 T28 T21)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "192": { 5.51/2.28 "goal": [ 5.51/2.28 { 5.51/2.28 "clause": 0, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 }, 5.51/2.28 { 5.51/2.28 "clause": 1, 5.51/2.28 "scope": 2, 5.51/2.28 "term": "(append T22 T23 X16)" 5.51/2.28 } 5.51/2.28 ], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "type": "Nodes", 5.51/2.28 "231": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(true)" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "221": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "232": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "233": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": [], 5.51/2.28 "free": [], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "168": { 5.51/2.28 "goal": [{ 5.51/2.28 "clause": -1, 5.51/2.28 "scope": -1, 5.51/2.28 "term": "(',' (append T22 T23 X16) (append X16 T24 T21))" 5.51/2.28 }], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.28 "relations": [] 5.51/2.28 }, 5.51/2.28 "ground": ["T21"], 5.51/2.28 "free": ["X16"], 5.51/2.28 "exprvars": [] 5.51/2.28 } 5.51/2.28 }, 5.51/2.28 "245": { 5.51/2.28 "goal": [], 5.51/2.28 "kb": { 5.51/2.28 "nonunifying": [], 5.51/2.28 "intvars": {}, 5.51/2.28 "arithmetic": { 5.51/2.28 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.51/2.29 "ground": [], 5.51/2.29 "free": [], 5.51/2.29 "exprvars": [] 5.51/2.29 } 5.51/2.29 }, 5.51/2.29 "203": { 5.51/2.29 "goal": [{ 5.51/2.29 "clause": 0, 5.51/2.29 "scope": 2, 5.51/2.29 "term": "(append T22 T23 X16)" 5.51/2.29 }], 5.51/2.29 "kb": { 5.51/2.29 "nonunifying": [], 5.51/2.29 "intvars": {}, 5.51/2.29 "arithmetic": { 5.51/2.29 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.51/2.29 "ground": [], 5.51/2.29 "free": ["X16"], 5.51/2.29 "exprvars": [] 5.51/2.29 } 5.51/2.29 }, 5.51/2.29 "214": { 5.51/2.29 "goal": [], 5.51/2.29 "kb": { 5.51/2.29 "nonunifying": [], 5.51/2.29 "intvars": {}, 5.51/2.29 "arithmetic": { 5.51/2.29 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.51/2.29 "ground": [], 5.51/2.29 "free": [], 5.51/2.29 "exprvars": [] 5.51/2.29 } 5.51/2.29 }, 5.51/2.29 "225": { 5.51/2.29 "goal": [ 5.51/2.29 { 5.51/2.29 "clause": 0, 5.51/2.29 "scope": 3, 5.51/2.29 "term": "(append T27 T28 T21)" 5.51/2.29 }, 5.51/2.29 { 5.51/2.29 "clause": 1, 5.51/2.29 "scope": 3, 5.51/2.29 "term": "(append T27 T28 T21)" 5.51/2.29 } 5.51/2.29 ], 5.51/2.29 "kb": { 5.51/2.29 "nonunifying": [], 5.51/2.29 "intvars": {}, 5.51/2.29 "arithmetic": { 5.51/2.29 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.51/2.29 "ground": ["T21"], 5.51/2.29 "free": [], 5.51/2.29 "exprvars": [] 5.51/2.29 } 5.51/2.29 }, 5.51/2.29 "236": { 5.51/2.29 "goal": [{ 5.51/2.29 "clause": -1, 5.51/2.29 "scope": -1, 5.51/2.29 "term": "(append T68 T69 T67)" 5.51/2.29 }], 5.51/2.29 "kb": { 5.51/2.29 "nonunifying": [], 5.51/2.29 "intvars": {}, 5.51/2.29 "arithmetic": { 5.51/2.29 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.51/2.29 "ground": ["T67"], 5.51/2.29 "free": [], 5.51/2.29 "exprvars": [] 5.51/2.29 } 5.51/2.29 }, 5.51/2.29 "204": { 5.51/2.29 "goal": [{ 5.51/2.29 "clause": 1, 5.51/2.29 "scope": 2, 5.51/2.29 "term": "(append T22 T23 X16)" 5.51/2.29 }], 5.51/2.29 "kb": { 5.51/2.29 "nonunifying": [], 5.51/2.29 "intvars": {}, 5.51/2.29 "arithmetic": { 5.51/2.29 "type": "PlainIntegerRelationState", 5.51/2.29 "relations": [] 5.51/2.29 }, 5.83/2.29 "ground": [], 5.83/2.29 "free": ["X16"], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "215": { 5.83/2.29 "goal": [], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": [], 5.83/2.29 "free": [], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "226": { 5.83/2.29 "goal": [{ 5.83/2.29 "clause": 0, 5.83/2.29 "scope": 3, 5.83/2.29 "term": "(append T27 T28 T21)" 5.83/2.29 }], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": ["T21"], 5.83/2.29 "free": [], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "205": { 5.83/2.29 "goal": [{ 5.83/2.29 "clause": -1, 5.83/2.29 "scope": -1, 5.83/2.29 "term": "(true)" 5.83/2.29 }], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": [], 5.83/2.29 "free": [], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "227": { 5.83/2.29 "goal": [{ 5.83/2.29 "clause": 1, 5.83/2.29 "scope": 3, 5.83/2.29 "term": "(append T27 T28 T21)" 5.83/2.29 }], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": ["T21"], 5.83/2.29 "free": [], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "218": { 5.83/2.29 "goal": [{ 5.83/2.29 "clause": -1, 5.83/2.29 "scope": -1, 5.83/2.29 "term": "(append T45 T46 X40)" 5.83/2.29 }], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": [], 5.83/2.29 "free": ["X40"], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "10": { 5.83/2.29 "goal": [{ 5.83/2.29 "clause": -1, 5.83/2.29 "scope": -1, 5.83/2.29 "term": "(append3 T1 T2 T3 T4)" 5.83/2.29 }], 5.83/2.29 "kb": { 5.83/2.29 "nonunifying": [], 5.83/2.29 "intvars": {}, 5.83/2.29 "arithmetic": { 5.83/2.29 "type": "PlainIntegerRelationState", 5.83/2.29 "relations": [] 5.83/2.29 }, 5.83/2.29 "ground": ["T4"], 5.83/2.29 "free": [], 5.83/2.29 "exprvars": [] 5.83/2.29 } 5.83/2.29 } 5.83/2.29 }, 5.83/2.29 "edges": [ 5.83/2.29 { 5.83/2.29 "from": 10, 5.83/2.29 "to": 11, 5.83/2.29 "label": "CASE" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 11, 5.83/2.29 "to": 168, 5.83/2.29 "label": "ONLY EVAL with clause\nappend3(X12, X13, X14, X15) :- ','(append(X12, X13, X16), append(X16, X14, X15)).\nand substitutionT1 -> T22,\nX12 -> T22,\nT2 -> T23,\nX13 -> T23,\nT3 -> T24,\nX14 -> T24,\nT4 -> T21,\nX15 -> T21,\nT18 -> T22,\nT19 -> T23,\nT20 -> T24" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 168, 5.83/2.29 "to": 190, 5.83/2.29 "label": "SPLIT 1" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 168, 5.83/2.29 "to": 191, 5.83/2.29 "label": "SPLIT 2\nreplacements:X16 -> T27,\nT24 -> T28" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 190, 5.83/2.29 "to": 192, 5.83/2.29 "label": "CASE" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 191, 5.83/2.29 "to": 225, 5.83/2.29 "label": "CASE" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 192, 5.83/2.29 "to": 203, 5.83/2.29 "label": "PARALLEL" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 192, 5.83/2.29 "to": 204, 5.83/2.29 "label": "PARALLEL" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 203, 5.83/2.29 "to": 205, 5.83/2.29 "label": "EVAL with clause\nappend([], X25, X25).\nand substitutionT22 -> [],\nT23 -> T35,\nX25 -> T35,\nX16 -> T35" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 203, 5.83/2.29 "to": 214, 5.83/2.29 "label": "EVAL-BACKTRACK" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 204, 5.83/2.29 "to": 218, 5.83/2.29 "label": "EVAL with clause\nappend(.(X36, X37), X38, .(X36, X39)) :- append(X37, X38, X39).\nand substitutionX36 -> T42,\nX37 -> T45,\nT22 -> .(T42, T45),\nT23 -> T46,\nX38 -> T46,\nX39 -> X40,\nX16 -> .(T42, X40),\nT43 -> T45,\nT44 -> T46" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 204, 5.83/2.29 "to": 221, 5.83/2.29 "label": "EVAL-BACKTRACK" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 205, 5.83/2.29 "to": 215, 5.83/2.29 "label": "SUCCESS" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 218, 5.83/2.29 "to": 190, 5.83/2.29 "label": "INSTANCE with matching:\nT22 -> T45\nT23 -> T46\nX16 -> X40" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 225, 5.83/2.29 "to": 226, 5.83/2.29 "label": "PARALLEL" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 225, 5.83/2.29 "to": 227, 5.83/2.29 "label": "PARALLEL" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 226, 5.83/2.29 "to": 231, 5.83/2.29 "label": "EVAL with clause\nappend([], X49, X49).\nand substitutionT27 -> [],\nT28 -> T55,\nX49 -> T55,\nT21 -> T55" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 226, 5.83/2.29 "to": 232, 5.83/2.29 "label": "EVAL-BACKTRACK" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 227, 5.83/2.29 "to": 236, 5.83/2.29 "label": "EVAL with clause\nappend(.(X58, X59), X60, .(X58, X61)) :- append(X59, X60, X61).\nand substitutionX58 -> T64,\nX59 -> T68,\nT27 -> .(T64, T68),\nT28 -> T69,\nX60 -> T69,\nX61 -> T67,\nT21 -> .(T64, T67),\nT65 -> T68,\nT66 -> T69" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 227, 5.83/2.29 "to": 245, 5.83/2.29 "label": "EVAL-BACKTRACK" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 231, 5.83/2.29 "to": 233, 5.83/2.29 "label": "SUCCESS" 5.83/2.29 }, 5.83/2.29 { 5.83/2.29 "from": 236, 5.83/2.29 "to": 191, 5.83/2.29 "label": "INSTANCE with matching:\nT27 -> T68\nT28 -> T69\nT21 -> T67" 5.83/2.29 } 5.83/2.29 ], 5.83/2.29 "type": "Graph" 5.83/2.29 } 5.83/2.29 } 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (58) 5.83/2.29 Complex Obligation (AND) 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (59) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f191_in(T21) -> f225_in(T21) :|: TRUE 5.83/2.29 f225_out(x) -> f191_out(x) :|: TRUE 5.83/2.29 f225_in(x1) -> f227_in(x1) :|: TRUE 5.83/2.29 f227_out(x2) -> f225_out(x2) :|: TRUE 5.83/2.29 f225_in(x3) -> f226_in(x3) :|: TRUE 5.83/2.29 f226_out(x4) -> f225_out(x4) :|: TRUE 5.83/2.29 f227_in(.(T64, T67)) -> f236_in(T67) :|: TRUE 5.83/2.29 f236_out(x5) -> f227_out(.(x6, x5)) :|: TRUE 5.83/2.29 f227_in(x7) -> f245_in :|: TRUE 5.83/2.29 f245_out -> f227_out(x8) :|: TRUE 5.83/2.29 f236_in(x9) -> f191_in(x9) :|: TRUE 5.83/2.29 f191_out(x10) -> f236_out(x10) :|: TRUE 5.83/2.29 f11_out(T4) -> f10_out(T4) :|: TRUE 5.83/2.29 f10_in(x11) -> f11_in(x11) :|: TRUE 5.83/2.29 f168_out(x12) -> f11_out(x12) :|: TRUE 5.83/2.29 f11_in(x13) -> f168_in(x13) :|: TRUE 5.83/2.29 f168_in(x14) -> f190_in :|: TRUE 5.83/2.29 f190_out -> f191_in(x15) :|: TRUE 5.83/2.29 f191_out(x16) -> f168_out(x16) :|: TRUE 5.83/2.29 Start term: f10_in(T4) 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (60) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.83/2.29 Constructed simple dependency graph. 5.83/2.29 5.83/2.29 Simplified to the following IRSwTs: 5.83/2.29 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (61) 5.83/2.29 TRUE 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (62) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f203_out -> f192_out :|: TRUE 5.83/2.29 f192_in -> f203_in :|: TRUE 5.83/2.29 f192_in -> f204_in :|: TRUE 5.83/2.29 f204_out -> f192_out :|: TRUE 5.83/2.29 f204_in -> f218_in :|: TRUE 5.83/2.29 f221_out -> f204_out :|: TRUE 5.83/2.29 f204_in -> f221_in :|: TRUE 5.83/2.29 f218_out -> f204_out :|: TRUE 5.83/2.29 f192_out -> f190_out :|: TRUE 5.83/2.29 f190_in -> f192_in :|: TRUE 5.83/2.29 f190_out -> f218_out :|: TRUE 5.83/2.29 f218_in -> f190_in :|: TRUE 5.83/2.29 f11_out(T4) -> f10_out(T4) :|: TRUE 5.83/2.29 f10_in(x) -> f11_in(x) :|: TRUE 5.83/2.29 f168_out(T21) -> f11_out(T21) :|: TRUE 5.83/2.29 f11_in(x1) -> f168_in(x1) :|: TRUE 5.83/2.29 f168_in(x2) -> f190_in :|: TRUE 5.83/2.29 f190_out -> f191_in(x3) :|: TRUE 5.83/2.29 f191_out(x4) -> f168_out(x4) :|: TRUE 5.83/2.29 Start term: f10_in(T4) 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (63) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.83/2.29 Constructed simple dependency graph. 5.83/2.29 5.83/2.29 Simplified to the following IRSwTs: 5.83/2.29 5.83/2.29 intTRSProblem: 5.83/2.29 f192_in -> f204_in :|: TRUE 5.83/2.29 f204_in -> f218_in :|: TRUE 5.83/2.29 f190_in -> f192_in :|: TRUE 5.83/2.29 f218_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (64) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f192_in -> f204_in :|: TRUE 5.83/2.29 f204_in -> f218_in :|: TRUE 5.83/2.29 f190_in -> f192_in :|: TRUE 5.83/2.29 f218_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (65) IntTRSCompressionProof (EQUIVALENT) 5.83/2.29 Compressed rules. 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (66) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f190_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (67) IRSFormatTransformerProof (EQUIVALENT) 5.83/2.29 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (68) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f190_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (69) IRSwTTerminationDigraphProof (EQUIVALENT) 5.83/2.29 Constructed termination digraph! 5.83/2.29 Nodes: 5.83/2.29 (1) f190_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 Arcs: 5.83/2.29 (1) -> (1) 5.83/2.29 5.83/2.29 This digraph is fully evaluated! 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (70) 5.83/2.29 Obligation: 5.83/2.29 5.83/2.29 Termination digraph: 5.83/2.29 Nodes: 5.83/2.29 (1) f190_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 Arcs: 5.83/2.29 (1) -> (1) 5.83/2.29 5.83/2.29 This digraph is fully evaluated! 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (71) FilterProof (EQUIVALENT) 5.83/2.29 Used the following sort dictionary for filtering: 5.83/2.29 f190_in() 5.83/2.29 Replaced non-predefined constructor symbols by 0. 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (72) 5.83/2.29 Obligation: 5.83/2.29 Rules: 5.83/2.29 f190_in -> f190_in :|: TRUE 5.83/2.29 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (73) IntTRSPeriodicNontermProof (COMPLETE) 5.83/2.29 Normalized system to the following form: 5.83/2.29 f(pc) -> f(1) :|: pc = 1 && TRUE 5.83/2.29 Witness term starting non-terminating reduction: f(1) 5.83/2.29 ---------------------------------------- 5.83/2.29 5.83/2.29 (74) 5.83/2.29 NO 5.83/2.31 EOF