4.62/1.98 YES 4.62/1.99 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.62/1.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.62/1.99 4.62/1.99 4.62/1.99 Left Termination of the query pattern 4.62/1.99 4.62/1.99 flat(g,a) 4.62/1.99 4.62/1.99 w.r.t. the given Prolog program could successfully be proven: 4.62/1.99 4.62/1.99 (0) Prolog 4.62/1.99 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.62/1.99 (2) PiTRS 4.62/1.99 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.62/1.99 (4) PiDP 4.62/1.99 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.62/1.99 (6) PiDP 4.62/1.99 (7) UsableRulesProof [EQUIVALENT, 0 ms] 4.62/1.99 (8) PiDP 4.62/1.99 (9) PiDPToQDPProof [SOUND, 0 ms] 4.62/1.99 (10) QDP 4.62/1.99 (11) UsableRulesReductionPairsProof [EQUIVALENT, 9 ms] 4.62/1.99 (12) QDP 4.62/1.99 (13) MRRProof [EQUIVALENT, 0 ms] 4.62/1.99 (14) QDP 4.62/1.99 (15) PisEmptyProof [EQUIVALENT, 0 ms] 4.62/1.99 (16) YES 4.62/1.99 4.62/1.99 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (0) 4.62/1.99 Obligation: 4.62/1.99 Clauses: 4.62/1.99 4.62/1.99 flat([], []). 4.62/1.99 flat(.([], T), R) :- flat(T, R). 4.62/1.99 flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R). 4.62/1.99 4.62/1.99 4.62/1.99 Query: flat(g,a) 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (1) PrologToPiTRSProof (SOUND) 4.62/1.99 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.62/1.99 4.62/1.99 flat_in_2: (b,f) 4.62/1.99 4.62/1.99 Transforming Prolog into the following Term Rewriting System: 4.62/1.99 4.62/1.99 Pi-finite rewrite system: 4.62/1.99 The TRS R consists of the following rules: 4.62/1.99 4.62/1.99 flat_in_ga([], []) -> flat_out_ga([], []) 4.62/1.99 flat_in_ga(.([], T), R) -> U1_ga(T, R, flat_in_ga(T, R)) 4.62/1.99 flat_in_ga(.(.(H, T), TT), .(H, R)) -> U2_ga(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 U2_ga(H, T, TT, R, flat_out_ga(.(T, TT), R)) -> flat_out_ga(.(.(H, T), TT), .(H, R)) 4.62/1.99 U1_ga(T, R, flat_out_ga(T, R)) -> flat_out_ga(.([], T), R) 4.62/1.99 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.62/1.99 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 flat_out_ga(x1, x2) = flat_out_ga(x1, x2) 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 4.62/1.99 4.62/1.99 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 4.62/1.99 4.62/1.99 4.62/1.99 4.62/1.99 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.62/1.99 4.62/1.99 4.62/1.99 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (2) 4.62/1.99 Obligation: 4.62/1.99 Pi-finite rewrite system: 4.62/1.99 The TRS R consists of the following rules: 4.62/1.99 4.62/1.99 flat_in_ga([], []) -> flat_out_ga([], []) 4.62/1.99 flat_in_ga(.([], T), R) -> U1_ga(T, R, flat_in_ga(T, R)) 4.62/1.99 flat_in_ga(.(.(H, T), TT), .(H, R)) -> U2_ga(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 U2_ga(H, T, TT, R, flat_out_ga(.(T, TT), R)) -> flat_out_ga(.(.(H, T), TT), .(H, R)) 4.62/1.99 U1_ga(T, R, flat_out_ga(T, R)) -> flat_out_ga(.([], T), R) 4.62/1.99 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.62/1.99 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 flat_out_ga(x1, x2) = flat_out_ga(x1, x2) 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 4.62/1.99 4.62/1.99 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 4.62/1.99 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (3) DependencyPairsProof (EQUIVALENT) 4.62/1.99 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.62/1.99 Pi DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.([], T), R) -> U1_GA(T, R, flat_in_ga(T, R)) 4.62/1.99 FLAT_IN_GA(.([], T), R) -> FLAT_IN_GA(T, R) 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> U2_GA(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> FLAT_IN_GA(.(T, TT), R) 4.62/1.99 4.62/1.99 The TRS R consists of the following rules: 4.62/1.99 4.62/1.99 flat_in_ga([], []) -> flat_out_ga([], []) 4.62/1.99 flat_in_ga(.([], T), R) -> U1_ga(T, R, flat_in_ga(T, R)) 4.62/1.99 flat_in_ga(.(.(H, T), TT), .(H, R)) -> U2_ga(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 U2_ga(H, T, TT, R, flat_out_ga(.(T, TT), R)) -> flat_out_ga(.(.(H, T), TT), .(H, R)) 4.62/1.99 U1_ga(T, R, flat_out_ga(T, R)) -> flat_out_ga(.([], T), R) 4.62/1.99 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.62/1.99 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 flat_out_ga(x1, x2) = flat_out_ga(x1, x2) 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 4.62/1.99 4.62/1.99 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.62/1.99 4.62/1.99 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 4.62/1.99 4.62/1.99 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 4.62/1.99 We have to consider all (P,R,Pi)-chains 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (4) 4.62/1.99 Obligation: 4.62/1.99 Pi DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.([], T), R) -> U1_GA(T, R, flat_in_ga(T, R)) 4.62/1.99 FLAT_IN_GA(.([], T), R) -> FLAT_IN_GA(T, R) 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> U2_GA(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> FLAT_IN_GA(.(T, TT), R) 4.62/1.99 4.62/1.99 The TRS R consists of the following rules: 4.62/1.99 4.62/1.99 flat_in_ga([], []) -> flat_out_ga([], []) 4.62/1.99 flat_in_ga(.([], T), R) -> U1_ga(T, R, flat_in_ga(T, R)) 4.62/1.99 flat_in_ga(.(.(H, T), TT), .(H, R)) -> U2_ga(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 U2_ga(H, T, TT, R, flat_out_ga(.(T, TT), R)) -> flat_out_ga(.(.(H, T), TT), .(H, R)) 4.62/1.99 U1_ga(T, R, flat_out_ga(T, R)) -> flat_out_ga(.([], T), R) 4.62/1.99 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.62/1.99 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 flat_out_ga(x1, x2) = flat_out_ga(x1, x2) 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 4.62/1.99 4.62/1.99 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.62/1.99 4.62/1.99 U1_GA(x1, x2, x3) = U1_GA(x1, x3) 4.62/1.99 4.62/1.99 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 4.62/1.99 We have to consider all (P,R,Pi)-chains 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (5) DependencyGraphProof (EQUIVALENT) 4.62/1.99 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (6) 4.62/1.99 Obligation: 4.62/1.99 Pi DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> FLAT_IN_GA(.(T, TT), R) 4.62/1.99 FLAT_IN_GA(.([], T), R) -> FLAT_IN_GA(T, R) 4.62/1.99 4.62/1.99 The TRS R consists of the following rules: 4.62/1.99 4.62/1.99 flat_in_ga([], []) -> flat_out_ga([], []) 4.62/1.99 flat_in_ga(.([], T), R) -> U1_ga(T, R, flat_in_ga(T, R)) 4.62/1.99 flat_in_ga(.(.(H, T), TT), .(H, R)) -> U2_ga(H, T, TT, R, flat_in_ga(.(T, TT), R)) 4.62/1.99 U2_ga(H, T, TT, R, flat_out_ga(.(T, TT), R)) -> flat_out_ga(.(.(H, T), TT), .(H, R)) 4.62/1.99 U1_ga(T, R, flat_out_ga(T, R)) -> flat_out_ga(.([], T), R) 4.62/1.99 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.62/1.99 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 flat_out_ga(x1, x2) = flat_out_ga(x1, x2) 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 U1_ga(x1, x2, x3) = U1_ga(x1, x3) 4.62/1.99 4.62/1.99 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) 4.62/1.99 4.62/1.99 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.62/1.99 4.62/1.99 4.62/1.99 We have to consider all (P,R,Pi)-chains 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (7) UsableRulesProof (EQUIVALENT) 4.62/1.99 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (8) 4.62/1.99 Obligation: 4.62/1.99 Pi DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT), .(H, R)) -> FLAT_IN_GA(.(T, TT), R) 4.62/1.99 FLAT_IN_GA(.([], T), R) -> FLAT_IN_GA(T, R) 4.62/1.99 4.62/1.99 R is empty. 4.62/1.99 The argument filtering Pi contains the following mapping: 4.62/1.99 [] = [] 4.62/1.99 4.62/1.99 .(x1, x2) = .(x1, x2) 4.62/1.99 4.62/1.99 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.62/1.99 4.62/1.99 4.62/1.99 We have to consider all (P,R,Pi)-chains 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (9) PiDPToQDPProof (SOUND) 4.62/1.99 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (10) 4.62/1.99 Obligation: 4.62/1.99 Q DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.(.(H, T), TT)) -> FLAT_IN_GA(.(T, TT)) 4.62/1.99 FLAT_IN_GA(.([], T)) -> FLAT_IN_GA(T) 4.62/1.99 4.62/1.99 R is empty. 4.62/1.99 Q is empty. 4.62/1.99 We have to consider all (P,Q,R)-chains. 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (11) UsableRulesReductionPairsProof (EQUIVALENT) 4.62/1.99 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 4.62/1.99 4.62/1.99 The following dependency pairs can be deleted: 4.62/1.99 4.62/1.99 FLAT_IN_GA(.([], T)) -> FLAT_IN_GA(T) 4.62/1.99 No rules are removed from R. 4.62/1.99 4.62/1.99 Used ordering: POLO with Polynomial interpretation [POLO]: 4.62/1.99 4.62/1.99 POL(.(x_1, x_2)) = x_1 + 2*x_2 4.62/1.99 POL(FLAT_IN_GA(x_1)) = 2*x_1 4.62/1.99 POL([]) = 0 4.62/1.99 4.62/1.99 4.62/1.99 ---------------------------------------- 4.62/1.99 4.62/1.99 (12) 4.62/1.99 Obligation: 4.62/1.99 Q DP problem: 4.62/1.99 The TRS P consists of the following rules: 4.62/2.00 4.62/2.00 FLAT_IN_GA(.(.(H, T), TT)) -> FLAT_IN_GA(.(T, TT)) 4.62/2.00 4.62/2.00 R is empty. 4.62/2.00 Q is empty. 4.62/2.00 We have to consider all (P,Q,R)-chains. 4.62/2.00 ---------------------------------------- 4.62/2.00 4.62/2.00 (13) MRRProof (EQUIVALENT) 4.62/2.00 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 4.62/2.00 4.62/2.00 Strictly oriented dependency pairs: 4.62/2.00 4.62/2.00 FLAT_IN_GA(.(.(H, T), TT)) -> FLAT_IN_GA(.(T, TT)) 4.62/2.00 4.62/2.00 4.62/2.00 Used ordering: Knuth-Bendix order [KBO] with precedence:._2 > FLAT_IN_GA_1 4.62/2.00 4.62/2.00 and weight map: 4.62/2.00 4.62/2.00 FLAT_IN_GA_1=1 4.62/2.00 ._2=0 4.62/2.00 4.62/2.00 The variable weight is 1 4.62/2.00 4.62/2.00 ---------------------------------------- 4.62/2.00 4.62/2.00 (14) 4.62/2.00 Obligation: 4.62/2.00 Q DP problem: 4.62/2.00 P is empty. 4.62/2.00 R is empty. 4.62/2.00 Q is empty. 4.62/2.00 We have to consider all (P,Q,R)-chains. 4.62/2.00 ---------------------------------------- 4.62/2.00 4.62/2.00 (15) PisEmptyProof (EQUIVALENT) 4.62/2.00 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.62/2.00 ---------------------------------------- 4.62/2.00 4.62/2.00 (16) 4.62/2.00 YES 4.62/2.02 EOF