5.54/2.31 MAYBE 5.86/2.34 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.86/2.34 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.86/2.34 5.86/2.34 5.86/2.34 Left Termination of the query pattern 5.86/2.34 5.86/2.34 sublist(g,a) 5.86/2.34 5.86/2.34 w.r.t. the given Prolog program could not be shown: 5.86/2.34 5.86/2.34 (0) Prolog 5.86/2.34 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.86/2.34 (2) PiTRS 5.86/2.34 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.86/2.34 (4) PiDP 5.86/2.34 (5) DependencyGraphProof [EQUIVALENT, 1 ms] 5.86/2.34 (6) AND 5.86/2.34 (7) PiDP 5.86/2.34 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.34 (9) PiDP 5.86/2.34 (10) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (11) QDP 5.86/2.34 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.86/2.34 (13) YES 5.86/2.34 (14) PiDP 5.86/2.34 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.34 (16) PiDP 5.86/2.34 (17) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (18) QDP 5.86/2.34 (19) PrologToPiTRSProof [SOUND, 0 ms] 5.86/2.34 (20) PiTRS 5.86/2.34 (21) DependencyPairsProof [EQUIVALENT, 0 ms] 5.86/2.34 (22) PiDP 5.86/2.34 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.34 (24) AND 5.86/2.34 (25) PiDP 5.86/2.34 (26) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.34 (27) PiDP 5.86/2.34 (28) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (29) QDP 5.86/2.34 (30) QDPSizeChangeProof [EQUIVALENT, 2 ms] 5.86/2.34 (31) YES 5.86/2.34 (32) PiDP 5.86/2.34 (33) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.34 (34) PiDP 5.86/2.34 (35) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (36) QDP 5.86/2.34 (37) PrologToDTProblemTransformerProof [SOUND, 0 ms] 5.86/2.34 (38) TRIPLES 5.86/2.34 (39) TriplesToPiDPProof [SOUND, 1 ms] 5.86/2.34 (40) PiDP 5.86/2.34 (41) DependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.34 (42) AND 5.86/2.34 (43) PiDP 5.86/2.34 (44) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (45) QDP 5.86/2.34 (46) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.86/2.34 (47) YES 5.86/2.34 (48) PiDP 5.86/2.34 (49) PiDPToQDPProof [SOUND, 0 ms] 5.86/2.34 (50) QDP 5.86/2.34 (51) PrologToIRSwTTransformerProof [SOUND, 0 ms] 5.86/2.34 (52) AND 5.86/2.34 (53) IRSwT 5.86/2.34 (54) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.34 (55) TRUE 5.86/2.34 (56) IRSwT 5.86/2.34 (57) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 5.86/2.34 (58) IRSwT 5.86/2.34 (59) IntTRSCompressionProof [EQUIVALENT, 0 ms] 5.86/2.34 (60) IRSwT 5.86/2.34 (61) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.86/2.34 (62) IRSwT 5.86/2.34 (63) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 5.86/2.34 (64) IRSwT 5.86/2.34 (65) FilterProof [EQUIVALENT, 0 ms] 5.86/2.34 (66) IntTRS 5.86/2.34 (67) IntTRSNonPeriodicNontermProof [COMPLETE, 0 ms] 5.86/2.34 (68) NO 5.86/2.34 (69) PrologToTRSTransformerProof [SOUND, 0 ms] 5.86/2.34 (70) QTRS 5.86/2.34 (71) QTRSRRRProof [EQUIVALENT, 68 ms] 5.86/2.34 (72) QTRS 5.86/2.34 (73) QTRSRRRProof [EQUIVALENT, 0 ms] 5.86/2.34 (74) QTRS 5.86/2.34 (75) Overlay + Local Confluence [EQUIVALENT, 0 ms] 5.86/2.34 (76) QTRS 5.86/2.34 (77) DependencyPairsProof [EQUIVALENT, 0 ms] 5.86/2.34 (78) QDP 5.86/2.34 (79) UsableRulesProof [EQUIVALENT, 0 ms] 5.86/2.34 (80) QDP 5.86/2.34 (81) QReductionProof [EQUIVALENT, 0 ms] 5.86/2.34 (82) QDP 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (0) 5.86/2.34 Obligation: 5.86/2.34 Clauses: 5.86/2.34 5.86/2.34 sublist(Xs, Ys) :- ','(app(X1, Zs, Ys), app(Xs, X2, Zs)). 5.86/2.34 app([], X, X). 5.86/2.34 app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). 5.86/2.34 5.86/2.34 5.86/2.34 Query: sublist(g,a) 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (1) PrologToPiTRSProof (SOUND) 5.86/2.34 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.86/2.34 5.86/2.34 sublist_in_2: (b,f) 5.86/2.34 5.86/2.34 app_in_3: (f,f,f) (b,f,f) 5.86/2.34 5.86/2.34 Transforming Prolog into the following Term Rewriting System: 5.86/2.34 5.86/2.34 Pi-finite rewrite system: 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (2) 5.86/2.34 Obligation: 5.86/2.34 Pi-finite rewrite system: 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (3) DependencyPairsProof (EQUIVALENT) 5.86/2.34 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) 5.86/2.34 5.86/2.34 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 5.86/2.34 5.86/2.34 U2_GA(x1, x2, x3) = U2_GA(x3) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x5) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (4) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) 5.86/2.34 5.86/2.34 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 5.86/2.34 5.86/2.34 U2_GA(x1, x2, x3) = U2_GA(x3) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x5) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (5) DependencyGraphProof (EQUIVALENT) 5.86/2.34 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (6) 5.86/2.34 Complex Obligation (AND) 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (7) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (8) UsableRulesProof (EQUIVALENT) 5.86/2.34 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (9) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (10) PiDPToQDPProof (SOUND) 5.86/2.34 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (11) 5.86/2.34 Obligation: 5.86/2.34 Q DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 Q is empty. 5.86/2.34 We have to consider all (P,Q,R)-chains. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (12) QDPSizeChangeProof (EQUIVALENT) 5.86/2.34 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.86/2.34 5.86/2.34 From the DPs we obtained the following set of size-change graphs: 5.86/2.34 *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) 5.86/2.34 The graph contains the following edges 1 > 1 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (13) 5.86/2.34 YES 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (14) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (15) UsableRulesProof (EQUIVALENT) 5.86/2.34 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (16) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (17) PiDPToQDPProof (SOUND) 5.86/2.34 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (18) 5.86/2.34 Obligation: 5.86/2.34 Q DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA -> APP_IN_AAA 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 Q is empty. 5.86/2.34 We have to consider all (P,Q,R)-chains. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (19) PrologToPiTRSProof (SOUND) 5.86/2.34 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.86/2.34 5.86/2.34 sublist_in_2: (b,f) 5.86/2.34 5.86/2.34 app_in_3: (f,f,f) (b,f,f) 5.86/2.34 5.86/2.34 Transforming Prolog into the following Term Rewriting System: 5.86/2.34 5.86/2.34 Pi-finite rewrite system: 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (20) 5.86/2.34 Obligation: 5.86/2.34 Pi-finite rewrite system: 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (21) DependencyPairsProof (EQUIVALENT) 5.86/2.34 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) 5.86/2.34 5.86/2.34 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 5.86/2.34 5.86/2.34 U2_GA(x1, x2, x3) = U2_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x2, x5) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (22) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) 5.86/2.34 5.86/2.34 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 5.86/2.34 5.86/2.34 U2_GA(x1, x2, x3) = U2_GA(x1, x3) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x2, x5) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (23) DependencyGraphProof (EQUIVALENT) 5.86/2.34 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (24) 5.86/2.34 Complex Obligation (AND) 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (25) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (26) UsableRulesProof (EQUIVALENT) 5.86/2.34 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (27) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (28) PiDPToQDPProof (SOUND) 5.86/2.34 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (29) 5.86/2.34 Obligation: 5.86/2.34 Q DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 Q is empty. 5.86/2.34 We have to consider all (P,Q,R)-chains. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (30) QDPSizeChangeProof (EQUIVALENT) 5.86/2.34 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.86/2.34 5.86/2.34 From the DPs we obtained the following set of size-change graphs: 5.86/2.34 *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) 5.86/2.34 The graph contains the following edges 1 > 1 5.86/2.34 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (31) 5.86/2.34 YES 5.86/2.34 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (32) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 The TRS R consists of the following rules: 5.86/2.34 5.86/2.34 sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) 5.86/2.34 app_in_aaa([], X, X) -> app_out_aaa([], X, X) 5.86/2.34 app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) 5.86/2.34 U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) 5.86/2.34 app_in_gaa([], X, X) -> app_out_gaa([], X, X) 5.86/2.34 app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) 5.86/2.34 U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) 5.86/2.34 U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) 5.86/2.34 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 sublist_in_ga(x1, x2) = sublist_in_ga(x1) 5.86/2.34 5.86/2.34 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_aaa(x1, x2, x3) = app_in_aaa 5.86/2.34 5.86/2.34 app_out_aaa(x1, x2, x3) = app_out_aaa(x1) 5.86/2.34 5.86/2.34 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 5.86/2.34 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 U2_ga(x1, x2, x3) = U2_ga(x1, x3) 5.86/2.34 5.86/2.34 app_in_gaa(x1, x2, x3) = app_in_gaa(x1) 5.86/2.34 5.86/2.34 [] = [] 5.86/2.34 5.86/2.34 app_out_gaa(x1, x2, x3) = app_out_gaa(x1) 5.86/2.34 5.86/2.34 U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) 5.86/2.34 5.86/2.34 sublist_out_ga(x1, x2) = sublist_out_ga(x1) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (33) UsableRulesProof (EQUIVALENT) 5.86/2.34 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (34) 5.86/2.34 Obligation: 5.86/2.34 Pi DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 The argument filtering Pi contains the following mapping: 5.86/2.34 .(x1, x2) = .(x2) 5.86/2.34 5.86/2.34 APP_IN_AAA(x1, x2, x3) = APP_IN_AAA 5.86/2.34 5.86/2.34 5.86/2.34 We have to consider all (P,R,Pi)-chains 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (35) PiDPToQDPProof (SOUND) 5.86/2.34 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (36) 5.86/2.34 Obligation: 5.86/2.34 Q DP problem: 5.86/2.34 The TRS P consists of the following rules: 5.86/2.34 5.86/2.34 APP_IN_AAA -> APP_IN_AAA 5.86/2.34 5.86/2.34 R is empty. 5.86/2.34 Q is empty. 5.86/2.34 We have to consider all (P,Q,R)-chains. 5.86/2.34 ---------------------------------------- 5.86/2.34 5.86/2.34 (37) PrologToDTProblemTransformerProof (SOUND) 5.86/2.34 Built DT problem from termination graph DT10. 5.86/2.34 5.86/2.34 { 5.86/2.34 "root": 3, 5.86/2.34 "program": { 5.86/2.34 "directives": [], 5.86/2.34 "clauses": [ 5.86/2.34 [ 5.86/2.34 "(sublist Xs Ys)", 5.86/2.34 "(',' (app X1 Zs Ys) (app Xs X2 Zs))" 5.86/2.34 ], 5.86/2.34 [ 5.86/2.34 "(app ([]) X X)", 5.86/2.34 null 5.86/2.34 ], 5.86/2.34 [ 5.86/2.34 "(app (. X Xs) Ys (. X Zs))", 5.86/2.34 "(app Xs Ys Zs)" 5.86/2.34 ] 5.86/2.34 ] 5.86/2.34 }, 5.86/2.34 "graph": { 5.86/2.34 "nodes": { 5.86/2.34 "22": { 5.86/2.34 "goal": [ 5.86/2.34 { 5.86/2.34 "clause": 1, 5.86/2.34 "scope": 2, 5.86/2.34 "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "clause": 2, 5.86/2.34 "scope": 2, 5.86/2.34 "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" 5.86/2.34 } 5.86/2.34 ], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": [ 5.86/2.34 "X7", 5.86/2.34 "X8", 5.86/2.34 "X9" 5.86/2.34 ], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "33": { 5.86/2.34 "goal": [], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": [], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "44": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(',' (app X80 X81 T45) (app T5 X9 X81))" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": [ 5.86/2.34 "X9", 5.86/2.34 "X80", 5.86/2.34 "X81" 5.86/2.34 ], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "12": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": 0, 5.86/2.34 "scope": 1, 5.86/2.34 "term": "(sublist T1 T2)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T1"], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "24": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": 1, 5.86/2.34 "scope": 2, 5.86/2.34 "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": [ 5.86/2.34 "X7", 5.86/2.34 "X8", 5.86/2.34 "X9" 5.86/2.34 ], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "35": { 5.86/2.34 "goal": [], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": [], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "46": { 5.86/2.34 "goal": [], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": [], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "25": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": 2, 5.86/2.34 "scope": 2, 5.86/2.34 "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": [ 5.86/2.34 "X7", 5.86/2.34 "X8", 5.86/2.34 "X9" 5.86/2.34 ], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "26": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(app T5 X9 T19)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": ["X9"], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "27": { 5.86/2.34 "goal": [ 5.86/2.34 { 5.86/2.34 "clause": 1, 5.86/2.34 "scope": 3, 5.86/2.34 "term": "(app T5 X9 T19)" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "clause": 2, 5.86/2.34 "scope": 3, 5.86/2.34 "term": "(app T5 X9 T19)" 5.86/2.34 } 5.86/2.34 ], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": ["X9"], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "29": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": 1, 5.86/2.34 "scope": 3, 5.86/2.34 "term": "(app T5 X9 T19)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": ["X9"], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "type": "Nodes", 5.86/2.34 "3": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(sublist T1 T2)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T1"], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "40": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(app T34 X56 T36)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T34"], 5.86/2.34 "free": ["X56"], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "30": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": 2, 5.86/2.34 "scope": 3, 5.86/2.34 "term": "(app T5 X9 T19)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": ["X9"], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "41": { 5.86/2.34 "goal": [], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": [], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "21": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": ["T5"], 5.86/2.34 "free": [ 5.86/2.34 "X7", 5.86/2.34 "X8", 5.86/2.34 "X9" 5.86/2.34 ], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "32": { 5.86/2.34 "goal": [{ 5.86/2.34 "clause": -1, 5.86/2.34 "scope": -1, 5.86/2.34 "term": "(true)" 5.86/2.34 }], 5.86/2.34 "kb": { 5.86/2.34 "nonunifying": [], 5.86/2.34 "intvars": {}, 5.86/2.34 "arithmetic": { 5.86/2.34 "type": "PlainIntegerRelationState", 5.86/2.34 "relations": [] 5.86/2.34 }, 5.86/2.34 "ground": [], 5.86/2.34 "free": [], 5.86/2.34 "exprvars": [] 5.86/2.34 } 5.86/2.34 } 5.86/2.34 }, 5.86/2.34 "edges": [ 5.86/2.34 { 5.86/2.34 "from": 3, 5.86/2.34 "to": 12, 5.86/2.34 "label": "CASE" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "from": 12, 5.86/2.34 "to": 21, 5.86/2.34 "label": "ONLY EVAL with clause\nsublist(X5, X6) :- ','(app(X7, X8, X6), app(X5, X9, X8)).\nand substitutionT1 -> T5,\nX5 -> T5,\nT2 -> T7,\nX6 -> T7,\nT6 -> T7" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "from": 21, 5.86/2.34 "to": 22, 5.86/2.34 "label": "CASE" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "from": 22, 5.86/2.34 "to": 24, 5.86/2.34 "label": "PARALLEL" 5.86/2.34 }, 5.86/2.34 { 5.86/2.34 "from": 22, 5.86/2.34 "to": 25, 5.86/2.34 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 24, 5.86/2.35 "to": 26, 5.86/2.35 "label": "ONLY EVAL with clause\napp([], X26, X26).\nand substitutionX7 -> [],\nX8 -> T19,\nX26 -> T19,\nT7 -> T19,\nX27 -> T19,\nT18 -> T19" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 25, 5.86/2.35 "to": 44, 5.86/2.35 "label": "EVAL with clause\napp(.(X75, X76), X77, .(X75, X78)) :- app(X76, X77, X78).\nand substitutionX75 -> T43,\nX76 -> X80,\nX7 -> .(T43, X80),\nX8 -> X81,\nX77 -> X81,\nX79 -> T43,\nX78 -> T45,\nT7 -> .(T43, T45),\nT44 -> T45" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 25, 5.86/2.35 "to": 46, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 26, 5.86/2.35 "to": 27, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 27, 5.86/2.35 "to": 29, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 27, 5.86/2.35 "to": 30, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 29, 5.86/2.35 "to": 32, 5.86/2.35 "label": "EVAL with clause\napp([], X40, X40).\nand substitutionT5 -> [],\nX9 -> T26,\nX40 -> T26,\nT19 -> T26,\nX41 -> T26" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 29, 5.86/2.35 "to": 33, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 30, 5.86/2.35 "to": 40, 5.86/2.35 "label": "EVAL with clause\napp(.(X52, X53), X54, .(X52, X55)) :- app(X53, X54, X55).\nand substitutionX52 -> T33,\nX53 -> T34,\nT5 -> .(T33, T34),\nX9 -> X56,\nX54 -> X56,\nX55 -> T36,\nT19 -> .(T33, T36),\nT35 -> T36" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 30, 5.86/2.35 "to": 41, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 32, 5.86/2.35 "to": 35, 5.86/2.35 "label": "SUCCESS" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 40, 5.86/2.35 "to": 26, 5.86/2.35 "label": "INSTANCE with matching:\nT5 -> T34\nX9 -> X56\nT19 -> T36" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 44, 5.86/2.35 "to": 21, 5.86/2.35 "label": "INSTANCE with matching:\nX7 -> X80\nX8 -> X81\nT7 -> T45" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "type": "Graph" 5.86/2.35 } 5.86/2.35 } 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (38) 5.86/2.35 Obligation: 5.86/2.35 Triples: 5.86/2.35 5.86/2.35 appA(.(X1, X2), X3, .(X1, X4)) :- appA(X2, X3, X4). 5.86/2.35 pB([], X1, X1, X2, X3) :- appA(X2, X3, X1). 5.86/2.35 pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). 5.86/2.35 sublistC(X1, X2) :- pB(X3, X4, X2, X1, X5). 5.86/2.35 5.86/2.35 Clauses: 5.86/2.35 5.86/2.35 appcA([], X1, X1). 5.86/2.35 appcA(.(X1, X2), X3, .(X1, X4)) :- appcA(X2, X3, X4). 5.86/2.35 qcB([], X1, X1, X2, X3) :- appcA(X2, X3, X1). 5.86/2.35 qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). 5.86/2.35 5.86/2.35 Afs: 5.86/2.35 5.86/2.35 sublistC(x1, x2) = sublistC(x1) 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (39) TriplesToPiDPProof (SOUND) 5.86/2.35 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.86/2.35 5.86/2.35 sublistC_in_2: (b,f) 5.86/2.35 5.86/2.35 pB_in_5: (f,f,f,b,f) 5.86/2.35 5.86/2.35 appA_in_3: (b,f,f) 5.86/2.35 5.86/2.35 Transforming TRIPLES into the following Term Rewriting System: 5.86/2.35 5.86/2.35 Pi DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 SUBLISTC_IN_GA(X1, X2) -> U4_GA(X1, X2, pB_in_aaaga(X3, X4, X2, X1, X5)) 5.86/2.35 SUBLISTC_IN_GA(X1, X2) -> PB_IN_AAAGA(X3, X4, X2, X1, X5) 5.86/2.35 PB_IN_AAAGA([], X1, X1, X2, X3) -> U2_AAAGA(X1, X2, X3, appA_in_gaa(X2, X3, X1)) 5.86/2.35 PB_IN_AAAGA([], X1, X1, X2, X3) -> APPA_IN_GAA(X2, X3, X1) 5.86/2.35 APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) 5.86/2.35 APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) 5.86/2.35 PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U3_AAAGA(X1, X2, X3, X4, X5, X6, pB_in_aaaga(X2, X3, X4, X5, X6)) 5.86/2.35 PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 The argument filtering Pi contains the following mapping: 5.86/2.35 pB_in_aaaga(x1, x2, x3, x4, x5) = pB_in_aaaga(x4) 5.86/2.35 5.86/2.35 appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) 5.86/2.35 5.86/2.35 .(x1, x2) = .(x2) 5.86/2.35 5.86/2.35 [] = [] 5.86/2.35 5.86/2.35 SUBLISTC_IN_GA(x1, x2) = SUBLISTC_IN_GA(x1) 5.86/2.35 5.86/2.35 U4_GA(x1, x2, x3) = U4_GA(x1, x3) 5.86/2.35 5.86/2.35 PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) 5.86/2.35 5.86/2.35 U2_AAAGA(x1, x2, x3, x4) = U2_AAAGA(x2, x4) 5.86/2.35 5.86/2.35 APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) 5.86/2.35 5.86/2.35 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x2, x5) 5.86/2.35 5.86/2.35 U3_AAAGA(x1, x2, x3, x4, x5, x6, x7) = U3_AAAGA(x5, x7) 5.86/2.35 5.86/2.35 5.86/2.35 We have to consider all (P,R,Pi)-chains 5.86/2.35 5.86/2.35 5.86/2.35 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 5.86/2.35 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (40) 5.86/2.35 Obligation: 5.86/2.35 Pi DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 SUBLISTC_IN_GA(X1, X2) -> U4_GA(X1, X2, pB_in_aaaga(X3, X4, X2, X1, X5)) 5.86/2.35 SUBLISTC_IN_GA(X1, X2) -> PB_IN_AAAGA(X3, X4, X2, X1, X5) 5.86/2.35 PB_IN_AAAGA([], X1, X1, X2, X3) -> U2_AAAGA(X1, X2, X3, appA_in_gaa(X2, X3, X1)) 5.86/2.35 PB_IN_AAAGA([], X1, X1, X2, X3) -> APPA_IN_GAA(X2, X3, X1) 5.86/2.35 APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) 5.86/2.35 APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) 5.86/2.35 PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U3_AAAGA(X1, X2, X3, X4, X5, X6, pB_in_aaaga(X2, X3, X4, X5, X6)) 5.86/2.35 PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 The argument filtering Pi contains the following mapping: 5.86/2.35 pB_in_aaaga(x1, x2, x3, x4, x5) = pB_in_aaaga(x4) 5.86/2.35 5.86/2.35 appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) 5.86/2.35 5.86/2.35 .(x1, x2) = .(x2) 5.86/2.35 5.86/2.35 [] = [] 5.86/2.35 5.86/2.35 SUBLISTC_IN_GA(x1, x2) = SUBLISTC_IN_GA(x1) 5.86/2.35 5.86/2.35 U4_GA(x1, x2, x3) = U4_GA(x1, x3) 5.86/2.35 5.86/2.35 PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) 5.86/2.35 5.86/2.35 U2_AAAGA(x1, x2, x3, x4) = U2_AAAGA(x2, x4) 5.86/2.35 5.86/2.35 APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) 5.86/2.35 5.86/2.35 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x2, x5) 5.86/2.35 5.86/2.35 U3_AAAGA(x1, x2, x3, x4, x5, x6, x7) = U3_AAAGA(x5, x7) 5.86/2.35 5.86/2.35 5.86/2.35 We have to consider all (P,R,Pi)-chains 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (41) DependencyGraphProof (EQUIVALENT) 5.86/2.35 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (42) 5.86/2.35 Complex Obligation (AND) 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (43) 5.86/2.35 Obligation: 5.86/2.35 Pi DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 The argument filtering Pi contains the following mapping: 5.86/2.35 .(x1, x2) = .(x2) 5.86/2.35 5.86/2.35 APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) 5.86/2.35 5.86/2.35 5.86/2.35 We have to consider all (P,R,Pi)-chains 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (44) PiDPToQDPProof (SOUND) 5.86/2.35 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (45) 5.86/2.35 Obligation: 5.86/2.35 Q DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 Q is empty. 5.86/2.35 We have to consider all (P,Q,R)-chains. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (46) QDPSizeChangeProof (EQUIVALENT) 5.86/2.35 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.86/2.35 5.86/2.35 From the DPs we obtained the following set of size-change graphs: 5.86/2.35 *APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) 5.86/2.35 The graph contains the following edges 1 > 1 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (47) 5.86/2.35 YES 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (48) 5.86/2.35 Obligation: 5.86/2.35 Pi DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 The argument filtering Pi contains the following mapping: 5.86/2.35 .(x1, x2) = .(x2) 5.86/2.35 5.86/2.35 PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) 5.86/2.35 5.86/2.35 5.86/2.35 We have to consider all (P,R,Pi)-chains 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (49) PiDPToQDPProof (SOUND) 5.86/2.35 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (50) 5.86/2.35 Obligation: 5.86/2.35 Q DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 PB_IN_AAAGA(X5) -> PB_IN_AAAGA(X5) 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 Q is empty. 5.86/2.35 We have to consider all (P,Q,R)-chains. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (51) PrologToIRSwTTransformerProof (SOUND) 5.86/2.35 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 5.86/2.35 5.86/2.35 { 5.86/2.35 "root": 2, 5.86/2.35 "program": { 5.86/2.35 "directives": [], 5.86/2.35 "clauses": [ 5.86/2.35 [ 5.86/2.35 "(sublist Xs Ys)", 5.86/2.35 "(',' (app X1 Zs Ys) (app Xs X2 Zs))" 5.86/2.35 ], 5.86/2.35 [ 5.86/2.35 "(app ([]) X X)", 5.86/2.35 null 5.86/2.35 ], 5.86/2.35 [ 5.86/2.35 "(app (. X Xs) Ys (. X Zs))", 5.86/2.35 "(app Xs Ys Zs)" 5.86/2.35 ] 5.86/2.35 ] 5.86/2.35 }, 5.86/2.35 "graph": { 5.86/2.35 "nodes": { 5.86/2.35 "23": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(',' (app X18 X19 T11) (app T9 X20 X19))" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19", 5.86/2.35 "X20" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "34": { 5.86/2.35 "goal": [ 5.86/2.35 { 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "45": { 5.86/2.35 "goal": [ 5.86/2.35 { 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "13": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 0, 5.86/2.35 "scope": 1, 5.86/2.35 "term": "(sublist T1 T2)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T1"], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "36": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "47": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "37": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "48": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "38": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(true)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "49": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(true)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "28": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "39": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "type": "Nodes", 5.86/2.35 "2": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(sublist T1 T2)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T1"], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "50": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "51": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "52": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app T43 X90 T45)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T43"], 5.86/2.35 "free": ["X90"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "31": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "42": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app X58 X59 T27)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X58", 5.86/2.35 "X59" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "53": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "43": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "edges": [ 5.86/2.35 { 5.86/2.35 "from": 2, 5.86/2.35 "to": 13, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 13, 5.86/2.35 "to": 23, 5.86/2.35 "label": "ONLY EVAL with clause\nsublist(X16, X17) :- ','(app(X18, X19, X17), app(X16, X20, X19)).\nand substitutionT1 -> T9,\nX16 -> T9,\nT2 -> T11,\nX17 -> T11,\nT10 -> T11" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 23, 5.86/2.35 "to": 28, 5.86/2.35 "label": "SPLIT 1" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 23, 5.86/2.35 "to": 31, 5.86/2.35 "label": "SPLIT 2\nreplacements:X18 -> T13,\nX19 -> T14" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 28, 5.86/2.35 "to": 34, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 31, 5.86/2.35 "to": 45, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 34, 5.86/2.35 "to": 36, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 34, 5.86/2.35 "to": 37, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 36, 5.86/2.35 "to": 38, 5.86/2.35 "label": "ONLY EVAL with clause\napp([], X37, X37).\nand substitutionX18 -> [],\nX19 -> T20,\nX37 -> T20,\nT11 -> T20,\nX38 -> T20" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 37, 5.86/2.35 "to": 42, 5.86/2.35 "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T25,\nX54 -> X58,\nX18 -> .(T25, X58),\nX19 -> X59,\nX55 -> X59,\nX57 -> T25,\nX56 -> T27,\nT11 -> .(T25, T27),\nT26 -> T27" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 37, 5.86/2.35 "to": 43, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 38, 5.86/2.35 "to": 39, 5.86/2.35 "label": "SUCCESS" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 42, 5.86/2.35 "to": 28, 5.86/2.35 "label": "INSTANCE with matching:\nX18 -> X58\nX19 -> X59\nT11 -> T27" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 45, 5.86/2.35 "to": 47, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 45, 5.86/2.35 "to": 48, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 47, 5.86/2.35 "to": 49, 5.86/2.35 "label": "EVAL with clause\napp([], X74, X74).\nand substitutionT9 -> [],\nX20 -> T35,\nX74 -> T35,\nT14 -> T35,\nX75 -> T35" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 47, 5.86/2.35 "to": 50, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 48, 5.86/2.35 "to": 52, 5.86/2.35 "label": "EVAL with clause\napp(.(X86, X87), X88, .(X86, X89)) :- app(X87, X88, X89).\nand substitutionX86 -> T42,\nX87 -> T43,\nT9 -> .(T42, T43),\nX20 -> X90,\nX88 -> X90,\nX89 -> T45,\nT14 -> .(T42, T45),\nT44 -> T45" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 48, 5.86/2.35 "to": 53, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 49, 5.86/2.35 "to": 51, 5.86/2.35 "label": "SUCCESS" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 52, 5.86/2.35 "to": 31, 5.86/2.35 "label": "INSTANCE with matching:\nT9 -> T43\nX20 -> X90\nT14 -> T45" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "type": "Graph" 5.86/2.35 } 5.86/2.35 } 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (52) 5.86/2.35 Complex Obligation (AND) 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (53) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f48_in(.(T42, T43)) -> f52_in(T43) :|: TRUE 5.86/2.35 f53_out -> f48_out(T9) :|: TRUE 5.86/2.35 f48_in(x) -> f53_in :|: TRUE 5.86/2.35 f52_out(x1) -> f48_out(.(x2, x1)) :|: TRUE 5.86/2.35 f31_in(x3) -> f45_in(x3) :|: TRUE 5.86/2.35 f45_out(x4) -> f31_out(x4) :|: TRUE 5.86/2.35 f45_in(x5) -> f48_in(x5) :|: TRUE 5.86/2.35 f47_out(x6) -> f45_out(x6) :|: TRUE 5.86/2.35 f48_out(x7) -> f45_out(x7) :|: TRUE 5.86/2.35 f45_in(x8) -> f47_in(x8) :|: TRUE 5.86/2.35 f31_out(x9) -> f52_out(x9) :|: TRUE 5.86/2.35 f52_in(x10) -> f31_in(x10) :|: TRUE 5.86/2.35 f2_in(T1) -> f13_in(T1) :|: TRUE 5.86/2.35 f13_out(x11) -> f2_out(x11) :|: TRUE 5.86/2.35 f13_in(x12) -> f23_in(x12) :|: TRUE 5.86/2.35 f23_out(x13) -> f13_out(x13) :|: TRUE 5.86/2.35 f28_out -> f31_in(x14) :|: TRUE 5.86/2.35 f31_out(x15) -> f23_out(x15) :|: TRUE 5.86/2.35 f23_in(x16) -> f28_in :|: TRUE 5.86/2.35 Start term: f2_in(T1) 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (54) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.86/2.35 Constructed simple dependency graph. 5.86/2.35 5.86/2.35 Simplified to the following IRSwTs: 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (55) 5.86/2.35 TRUE 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (56) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f34_in -> f36_in :|: TRUE 5.86/2.35 f34_in -> f37_in :|: TRUE 5.86/2.35 f37_out -> f34_out :|: TRUE 5.86/2.35 f36_out -> f34_out :|: TRUE 5.86/2.35 f34_out -> f28_out :|: TRUE 5.86/2.35 f28_in -> f34_in :|: TRUE 5.86/2.35 f43_out -> f37_out :|: TRUE 5.86/2.35 f37_in -> f43_in :|: TRUE 5.86/2.35 f37_in -> f42_in :|: TRUE 5.86/2.35 f42_out -> f37_out :|: TRUE 5.86/2.35 f28_out -> f42_out :|: TRUE 5.86/2.35 f42_in -> f28_in :|: TRUE 5.86/2.35 f2_in(T1) -> f13_in(T1) :|: TRUE 5.86/2.35 f13_out(x) -> f2_out(x) :|: TRUE 5.86/2.35 f13_in(T9) -> f23_in(T9) :|: TRUE 5.86/2.35 f23_out(x1) -> f13_out(x1) :|: TRUE 5.86/2.35 f28_out -> f31_in(x2) :|: TRUE 5.86/2.35 f31_out(x3) -> f23_out(x3) :|: TRUE 5.86/2.35 f23_in(x4) -> f28_in :|: TRUE 5.86/2.35 Start term: f2_in(T1) 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (57) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 5.86/2.35 Constructed simple dependency graph. 5.86/2.35 5.86/2.35 Simplified to the following IRSwTs: 5.86/2.35 5.86/2.35 intTRSProblem: 5.86/2.35 f34_in -> f37_in :|: TRUE 5.86/2.35 f28_in -> f34_in :|: TRUE 5.86/2.35 f37_in -> f42_in :|: TRUE 5.86/2.35 f42_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (58) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f34_in -> f37_in :|: TRUE 5.86/2.35 f28_in -> f34_in :|: TRUE 5.86/2.35 f37_in -> f42_in :|: TRUE 5.86/2.35 f42_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (59) IntTRSCompressionProof (EQUIVALENT) 5.86/2.35 Compressed rules. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (60) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f28_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (61) IRSFormatTransformerProof (EQUIVALENT) 5.86/2.35 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (62) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f28_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (63) IRSwTTerminationDigraphProof (EQUIVALENT) 5.86/2.35 Constructed termination digraph! 5.86/2.35 Nodes: 5.86/2.35 (1) f28_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 Arcs: 5.86/2.35 (1) -> (1) 5.86/2.35 5.86/2.35 This digraph is fully evaluated! 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (64) 5.86/2.35 Obligation: 5.86/2.35 5.86/2.35 Termination digraph: 5.86/2.35 Nodes: 5.86/2.35 (1) f28_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 Arcs: 5.86/2.35 (1) -> (1) 5.86/2.35 5.86/2.35 This digraph is fully evaluated! 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (65) FilterProof (EQUIVALENT) 5.86/2.35 Used the following sort dictionary for filtering: 5.86/2.35 f28_in() 5.86/2.35 Replaced non-predefined constructor symbols by 0. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (66) 5.86/2.35 Obligation: 5.86/2.35 Rules: 5.86/2.35 f28_in -> f28_in :|: TRUE 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (67) IntTRSNonPeriodicNontermProof (COMPLETE) 5.86/2.35 Normalized system to the following form: 5.86/2.35 f(pc) -> f(1) :|: pc = 1 && TRUE 5.86/2.35 Proved unsatisfiability of the following formula, indicating that the system is never left after entering: 5.86/2.35 ((run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) 5.86/2.35 Proved satisfiability of the following formula, indicating that the system is entered at least once: 5.86/2.35 (run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (68) 5.86/2.35 NO 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (69) PrologToTRSTransformerProof (SOUND) 5.86/2.35 Transformed Prolog program to TRS. 5.86/2.35 5.86/2.35 { 5.86/2.35 "root": 1, 5.86/2.35 "program": { 5.86/2.35 "directives": [], 5.86/2.35 "clauses": [ 5.86/2.35 [ 5.86/2.35 "(sublist Xs Ys)", 5.86/2.35 "(',' (app X1 Zs Ys) (app Xs X2 Zs))" 5.86/2.35 ], 5.86/2.35 [ 5.86/2.35 "(app ([]) X X)", 5.86/2.35 null 5.86/2.35 ], 5.86/2.35 [ 5.86/2.35 "(app (. X Xs) Ys (. X Zs))", 5.86/2.35 "(app Xs Ys Zs)" 5.86/2.35 ] 5.86/2.35 ] 5.86/2.35 }, 5.86/2.35 "graph": { 5.86/2.35 "nodes": { 5.86/2.35 "66": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(',' (app X18 X19 T11) (app T9 X20 X19))" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19", 5.86/2.35 "X20" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "67": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "68": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "79": { 5.86/2.35 "goal": [ 5.86/2.35 { 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "type": "Nodes", 5.86/2.35 "131": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "142": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app T43 X90 T45)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T43"], 5.86/2.35 "free": ["X90"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "1": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(sublist T1 T2)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T1"], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "122": { 5.86/2.35 "goal": [ 5.86/2.35 { 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "144": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "113": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "124": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "125": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 2, 5.86/2.35 "scope": 3, 5.86/2.35 "term": "(app T9 X20 T14)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T9"], 5.86/2.35 "free": ["X20"], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "115": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(true)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "116": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "127": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(true)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "117": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": -1, 5.86/2.35 "scope": -1, 5.86/2.35 "term": "(app X58 X59 T27)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X58", 5.86/2.35 "X59" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "118": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "129": { 5.86/2.35 "goal": [], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "9": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 0, 5.86/2.35 "scope": 1, 5.86/2.35 "term": "(sublist T1 T2)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": ["T1"], 5.86/2.35 "free": [], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "109": { 5.86/2.35 "goal": [{ 5.86/2.35 "clause": 1, 5.86/2.35 "scope": 2, 5.86/2.35 "term": "(app X18 X19 T11)" 5.86/2.35 }], 5.86/2.35 "kb": { 5.86/2.35 "nonunifying": [], 5.86/2.35 "intvars": {}, 5.86/2.35 "arithmetic": { 5.86/2.35 "type": "PlainIntegerRelationState", 5.86/2.35 "relations": [] 5.86/2.35 }, 5.86/2.35 "ground": [], 5.86/2.35 "free": [ 5.86/2.35 "X18", 5.86/2.35 "X19" 5.86/2.35 ], 5.86/2.35 "exprvars": [] 5.86/2.35 } 5.86/2.35 } 5.86/2.35 }, 5.86/2.35 "edges": [ 5.86/2.35 { 5.86/2.35 "from": 1, 5.86/2.35 "to": 9, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 9, 5.86/2.35 "to": 66, 5.86/2.35 "label": "ONLY EVAL with clause\nsublist(X16, X17) :- ','(app(X18, X19, X17), app(X16, X20, X19)).\nand substitutionT1 -> T9,\nX16 -> T9,\nT2 -> T11,\nX17 -> T11,\nT10 -> T11" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 66, 5.86/2.35 "to": 67, 5.86/2.35 "label": "SPLIT 1" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 66, 5.86/2.35 "to": 68, 5.86/2.35 "label": "SPLIT 2\nreplacements:X18 -> T13,\nX19 -> T14" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 67, 5.86/2.35 "to": 79, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 68, 5.86/2.35 "to": 122, 5.86/2.35 "label": "CASE" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 79, 5.86/2.35 "to": 109, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 79, 5.86/2.35 "to": 113, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 109, 5.86/2.35 "to": 115, 5.86/2.35 "label": "ONLY EVAL with clause\napp([], X37, X37).\nand substitutionX18 -> [],\nX19 -> T20,\nX37 -> T20,\nT11 -> T20,\nX38 -> T20" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 113, 5.86/2.35 "to": 117, 5.86/2.35 "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T25,\nX54 -> X58,\nX18 -> .(T25, X58),\nX19 -> X59,\nX55 -> X59,\nX57 -> T25,\nX56 -> T27,\nT11 -> .(T25, T27),\nT26 -> T27" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 113, 5.86/2.35 "to": 118, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 115, 5.86/2.35 "to": 116, 5.86/2.35 "label": "SUCCESS" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 117, 5.86/2.35 "to": 67, 5.86/2.35 "label": "INSTANCE with matching:\nX18 -> X58\nX19 -> X59\nT11 -> T27" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 122, 5.86/2.35 "to": 124, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 122, 5.86/2.35 "to": 125, 5.86/2.35 "label": "PARALLEL" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 124, 5.86/2.35 "to": 127, 5.86/2.35 "label": "EVAL with clause\napp([], X74, X74).\nand substitutionT9 -> [],\nX20 -> T35,\nX74 -> T35,\nT14 -> T35,\nX75 -> T35" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 124, 5.86/2.35 "to": 129, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 125, 5.86/2.35 "to": 142, 5.86/2.35 "label": "EVAL with clause\napp(.(X86, X87), X88, .(X86, X89)) :- app(X87, X88, X89).\nand substitutionX86 -> T42,\nX87 -> T43,\nT9 -> .(T42, T43),\nX20 -> X90,\nX88 -> X90,\nX89 -> T45,\nT14 -> .(T42, T45),\nT44 -> T45" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 125, 5.86/2.35 "to": 144, 5.86/2.35 "label": "EVAL-BACKTRACK" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 127, 5.86/2.35 "to": 131, 5.86/2.35 "label": "SUCCESS" 5.86/2.35 }, 5.86/2.35 { 5.86/2.35 "from": 142, 5.86/2.35 "to": 68, 5.86/2.35 "label": "INSTANCE with matching:\nT9 -> T43\nX20 -> X90\nT14 -> T45" 5.86/2.35 } 5.86/2.35 ], 5.86/2.35 "type": "Graph" 5.86/2.35 } 5.86/2.35 } 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (70) 5.86/2.35 Obligation: 5.86/2.35 Q restricted rewrite system: 5.86/2.35 The TRS R consists of the following rules: 5.86/2.35 5.86/2.35 f1_in(T9) -> U1(f66_in(T9), T9) 5.86/2.35 U1(f66_out1, T9) -> f1_out1 5.86/2.35 f67_in -> f67_out1 5.86/2.35 f67_in -> U2(f67_in) 5.86/2.35 U2(f67_out1) -> f67_out1 5.86/2.35 f68_in([]) -> f68_out1 5.86/2.35 f68_in(.(T42, T43)) -> U3(f68_in(T43), .(T42, T43)) 5.86/2.35 U3(f68_out1, .(T42, T43)) -> f68_out1 5.86/2.35 f66_in(T9) -> U4(f67_in, T9) 5.86/2.35 U4(f67_out1, T9) -> U5(f68_in(T9), T9) 5.86/2.35 U5(f68_out1, T9) -> f66_out1 5.86/2.35 5.86/2.35 Q is empty. 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (71) QTRSRRRProof (EQUIVALENT) 5.86/2.35 Used ordering: 5.86/2.35 f1_in/1(YES) 5.86/2.35 U1/2(YES,YES) 5.86/2.35 f66_in/1(YES) 5.86/2.35 f66_out1/0) 5.86/2.35 f1_out1/0) 5.86/2.35 f67_in/0) 5.86/2.35 f67_out1/0) 5.86/2.35 U2/1)YES( 5.86/2.35 f68_in/1(YES) 5.86/2.35 []/0) 5.86/2.35 f68_out1/0) 5.86/2.35 ./2(YES,YES) 5.86/2.35 U3/2(YES,YES) 5.86/2.35 U4/2(YES,YES) 5.86/2.35 U5/2(YES,YES) 5.86/2.35 5.86/2.35 Quasi precedence: 5.86/2.35 f1_in_1 > U1_2 > f1_out1 5.86/2.35 f1_in_1 > [f66_in_1, f67_in] > U4_2 > [f66_out1, f67_out1, f68_in_1, [], f68_out1, ._2] > U3_2 5.86/2.35 f1_in_1 > [f66_in_1, f67_in] > U4_2 > [f66_out1, f67_out1, f68_in_1, [], f68_out1, ._2] > U5_2 5.86/2.35 5.86/2.35 5.86/2.35 Status: 5.86/2.35 f1_in_1: multiset status 5.86/2.35 U1_2: [1,2] 5.86/2.35 f66_in_1: [1] 5.86/2.35 f66_out1: multiset status 5.86/2.35 f1_out1: multiset status 5.86/2.35 f67_in: multiset status 5.86/2.35 f67_out1: multiset status 5.86/2.35 f68_in_1: multiset status 5.86/2.35 []: multiset status 5.86/2.35 f68_out1: multiset status 5.86/2.35 ._2: multiset status 5.86/2.35 U3_2: multiset status 5.86/2.35 U4_2: multiset status 5.86/2.35 U5_2: multiset status 5.86/2.35 5.86/2.35 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.35 5.86/2.35 f1_in(T9) -> U1(f66_in(T9), T9) 5.86/2.35 U1(f66_out1, T9) -> f1_out1 5.86/2.35 f67_in -> f67_out1 5.86/2.35 f68_in([]) -> f68_out1 5.86/2.35 f68_in(.(T42, T43)) -> U3(f68_in(T43), .(T42, T43)) 5.86/2.35 U3(f68_out1, .(T42, T43)) -> f68_out1 5.86/2.35 f66_in(T9) -> U4(f67_in, T9) 5.86/2.35 U4(f67_out1, T9) -> U5(f68_in(T9), T9) 5.86/2.35 U5(f68_out1, T9) -> f66_out1 5.86/2.35 5.86/2.35 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (72) 5.86/2.35 Obligation: 5.86/2.35 Q restricted rewrite system: 5.86/2.35 The TRS R consists of the following rules: 5.86/2.35 5.86/2.35 f67_in -> U2(f67_in) 5.86/2.35 U2(f67_out1) -> f67_out1 5.86/2.35 5.86/2.35 Q is empty. 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (73) QTRSRRRProof (EQUIVALENT) 5.86/2.35 Used ordering: 5.86/2.35 Polynomial interpretation [POLO]: 5.86/2.35 5.86/2.35 POL(U2(x_1)) = 2*x_1 5.86/2.35 POL(f67_in) = 0 5.86/2.35 POL(f67_out1) = 1 5.86/2.35 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.35 5.86/2.35 U2(f67_out1) -> f67_out1 5.86/2.35 5.86/2.35 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (74) 5.86/2.35 Obligation: 5.86/2.35 Q restricted rewrite system: 5.86/2.35 The TRS R consists of the following rules: 5.86/2.35 5.86/2.35 f67_in -> U2(f67_in) 5.86/2.35 5.86/2.35 Q is empty. 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (75) Overlay + Local Confluence (EQUIVALENT) 5.86/2.35 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (76) 5.86/2.35 Obligation: 5.86/2.35 Q restricted rewrite system: 5.86/2.35 The TRS R consists of the following rules: 5.86/2.35 5.86/2.35 f67_in -> U2(f67_in) 5.86/2.35 5.86/2.35 The set Q consists of the following terms: 5.86/2.35 5.86/2.35 f67_in 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (77) DependencyPairsProof (EQUIVALENT) 5.86/2.35 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (78) 5.86/2.35 Obligation: 5.86/2.35 Q DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 F67_IN -> F67_IN 5.86/2.35 5.86/2.35 The TRS R consists of the following rules: 5.86/2.35 5.86/2.35 f67_in -> U2(f67_in) 5.86/2.35 5.86/2.35 The set Q consists of the following terms: 5.86/2.35 5.86/2.35 f67_in 5.86/2.35 5.86/2.35 We have to consider all minimal (P,Q,R)-chains. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (79) UsableRulesProof (EQUIVALENT) 5.86/2.35 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (80) 5.86/2.35 Obligation: 5.86/2.35 Q DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 F67_IN -> F67_IN 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 The set Q consists of the following terms: 5.86/2.35 5.86/2.35 f67_in 5.86/2.35 5.86/2.35 We have to consider all minimal (P,Q,R)-chains. 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (81) QReductionProof (EQUIVALENT) 5.86/2.35 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.86/2.35 5.86/2.35 f67_in 5.86/2.35 5.86/2.35 5.86/2.35 ---------------------------------------- 5.86/2.35 5.86/2.35 (82) 5.86/2.35 Obligation: 5.86/2.35 Q DP problem: 5.86/2.35 The TRS P consists of the following rules: 5.86/2.35 5.86/2.35 F67_IN -> F67_IN 5.86/2.35 5.86/2.35 R is empty. 5.86/2.35 Q is empty. 5.86/2.35 We have to consider all minimal (P,Q,R)-chains. 5.86/2.39 EOF