4.73/2.06 YES 4.79/2.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.79/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.79/2.07 4.79/2.07 4.79/2.07 Left Termination of the query pattern 4.79/2.07 4.79/2.07 flat(g,a) 4.79/2.07 4.79/2.07 w.r.t. the given Prolog program could successfully be proven: 4.79/2.07 4.79/2.07 (0) Prolog 4.79/2.07 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.79/2.07 (2) PiTRS 4.79/2.07 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.79/2.07 (4) PiDP 4.79/2.07 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.79/2.07 (6) PiDP 4.79/2.07 (7) UsableRulesProof [EQUIVALENT, 0 ms] 4.79/2.07 (8) PiDP 4.79/2.07 (9) PiDPToQDPProof [SOUND, 0 ms] 4.79/2.07 (10) QDP 4.79/2.07 (11) UsableRulesReductionPairsProof [EQUIVALENT, 3 ms] 4.79/2.07 (12) QDP 4.79/2.07 (13) PisEmptyProof [EQUIVALENT, 0 ms] 4.79/2.07 (14) YES 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (0) 4.79/2.07 Obligation: 4.79/2.07 Clauses: 4.79/2.07 4.79/2.07 flat(niltree, nil). 4.79/2.07 flat(tree(X, niltree, T), cons(X, Xs)) :- flat(T, Xs). 4.79/2.07 flat(tree(X, tree(Y, T1, T2), T3), Xs) :- flat(tree(Y, T1, tree(X, T2, T3)), Xs). 4.79/2.07 4.79/2.07 4.79/2.07 Query: flat(g,a) 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (1) PrologToPiTRSProof (SOUND) 4.79/2.07 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.79/2.07 4.79/2.07 flat_in_2: (b,f) 4.79/2.07 4.79/2.07 Transforming Prolog into the following Term Rewriting System: 4.79/2.07 4.79/2.07 Pi-finite rewrite system: 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 flat_in_ga(niltree, nil) -> flat_out_ga(niltree, nil) 4.79/2.07 flat_in_ga(tree(X, niltree, T), cons(X, Xs)) -> U1_ga(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 flat_in_ga(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_ga(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 U2_ga(X, Y, T1, T2, T3, Xs, flat_out_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) -> flat_out_ga(tree(X, tree(Y, T1, T2), T3), Xs) 4.79/2.07 U1_ga(X, T, Xs, flat_out_ga(T, Xs)) -> flat_out_ga(tree(X, niltree, T), cons(X, Xs)) 4.79/2.07 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.79/2.07 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 flat_out_ga(x1, x2) = flat_out_ga(x2) 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.79/2.07 4.79/2.07 U2_ga(x1, x2, x3, x4, x5, x6, x7) = U2_ga(x7) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (2) 4.79/2.07 Obligation: 4.79/2.07 Pi-finite rewrite system: 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 flat_in_ga(niltree, nil) -> flat_out_ga(niltree, nil) 4.79/2.07 flat_in_ga(tree(X, niltree, T), cons(X, Xs)) -> U1_ga(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 flat_in_ga(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_ga(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 U2_ga(X, Y, T1, T2, T3, Xs, flat_out_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) -> flat_out_ga(tree(X, tree(Y, T1, T2), T3), Xs) 4.79/2.07 U1_ga(X, T, Xs, flat_out_ga(T, Xs)) -> flat_out_ga(tree(X, niltree, T), cons(X, Xs)) 4.79/2.07 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.79/2.07 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 flat_out_ga(x1, x2) = flat_out_ga(x2) 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.79/2.07 4.79/2.07 U2_ga(x1, x2, x3, x4, x5, x6, x7) = U2_ga(x7) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (3) DependencyPairsProof (EQUIVALENT) 4.79/2.07 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.79/2.07 Pi DP problem: 4.79/2.07 The TRS P consists of the following rules: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> U1_GA(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> FLAT_IN_GA(T, Xs) 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_GA(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3)), Xs) 4.79/2.07 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 flat_in_ga(niltree, nil) -> flat_out_ga(niltree, nil) 4.79/2.07 flat_in_ga(tree(X, niltree, T), cons(X, Xs)) -> U1_ga(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 flat_in_ga(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_ga(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 U2_ga(X, Y, T1, T2, T3, Xs, flat_out_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) -> flat_out_ga(tree(X, tree(Y, T1, T2), T3), Xs) 4.79/2.07 U1_ga(X, T, Xs, flat_out_ga(T, Xs)) -> flat_out_ga(tree(X, niltree, T), cons(X, Xs)) 4.79/2.07 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.79/2.07 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 flat_out_ga(x1, x2) = flat_out_ga(x2) 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.79/2.07 4.79/2.07 U2_ga(x1, x2, x3, x4, x5, x6, x7) = U2_ga(x7) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.79/2.07 4.79/2.07 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.79/2.07 4.79/2.07 U2_GA(x1, x2, x3, x4, x5, x6, x7) = U2_GA(x7) 4.79/2.07 4.79/2.07 4.79/2.07 We have to consider all (P,R,Pi)-chains 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (4) 4.79/2.07 Obligation: 4.79/2.07 Pi DP problem: 4.79/2.07 The TRS P consists of the following rules: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> U1_GA(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> FLAT_IN_GA(T, Xs) 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_GA(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3)), Xs) 4.79/2.07 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 flat_in_ga(niltree, nil) -> flat_out_ga(niltree, nil) 4.79/2.07 flat_in_ga(tree(X, niltree, T), cons(X, Xs)) -> U1_ga(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 flat_in_ga(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_ga(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 U2_ga(X, Y, T1, T2, T3, Xs, flat_out_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) -> flat_out_ga(tree(X, tree(Y, T1, T2), T3), Xs) 4.79/2.07 U1_ga(X, T, Xs, flat_out_ga(T, Xs)) -> flat_out_ga(tree(X, niltree, T), cons(X, Xs)) 4.79/2.07 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.79/2.07 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 flat_out_ga(x1, x2) = flat_out_ga(x2) 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.79/2.07 4.79/2.07 U2_ga(x1, x2, x3, x4, x5, x6, x7) = U2_ga(x7) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.79/2.07 4.79/2.07 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.79/2.07 4.79/2.07 U2_GA(x1, x2, x3, x4, x5, x6, x7) = U2_GA(x7) 4.79/2.07 4.79/2.07 4.79/2.07 We have to consider all (P,R,Pi)-chains 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (5) DependencyGraphProof (EQUIVALENT) 4.79/2.07 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (6) 4.79/2.07 Obligation: 4.79/2.07 Pi DP problem: 4.79/2.07 The TRS P consists of the following rules: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3)), Xs) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> FLAT_IN_GA(T, Xs) 4.79/2.07 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 flat_in_ga(niltree, nil) -> flat_out_ga(niltree, nil) 4.79/2.07 flat_in_ga(tree(X, niltree, T), cons(X, Xs)) -> U1_ga(X, T, Xs, flat_in_ga(T, Xs)) 4.79/2.07 flat_in_ga(tree(X, tree(Y, T1, T2), T3), Xs) -> U2_ga(X, Y, T1, T2, T3, Xs, flat_in_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) 4.79/2.07 U2_ga(X, Y, T1, T2, T3, Xs, flat_out_ga(tree(Y, T1, tree(X, T2, T3)), Xs)) -> flat_out_ga(tree(X, tree(Y, T1, T2), T3), Xs) 4.79/2.07 U1_ga(X, T, Xs, flat_out_ga(T, Xs)) -> flat_out_ga(tree(X, niltree, T), cons(X, Xs)) 4.79/2.07 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 flat_in_ga(x1, x2) = flat_in_ga(x1) 4.79/2.07 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 flat_out_ga(x1, x2) = flat_out_ga(x2) 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.79/2.07 4.79/2.07 U2_ga(x1, x2, x3, x4, x5, x6, x7) = U2_ga(x7) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.79/2.07 4.79/2.07 4.79/2.07 We have to consider all (P,R,Pi)-chains 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (7) UsableRulesProof (EQUIVALENT) 4.79/2.07 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (8) 4.79/2.07 Obligation: 4.79/2.07 Pi DP problem: 4.79/2.07 The TRS P consists of the following rules: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3), Xs) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3)), Xs) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T), cons(X, Xs)) -> FLAT_IN_GA(T, Xs) 4.79/2.07 4.79/2.07 R is empty. 4.79/2.07 The argument filtering Pi contains the following mapping: 4.79/2.07 niltree = niltree 4.79/2.07 4.79/2.07 tree(x1, x2, x3) = tree(x1, x2, x3) 4.79/2.07 4.79/2.07 cons(x1, x2) = cons(x1, x2) 4.79/2.07 4.79/2.07 FLAT_IN_GA(x1, x2) = FLAT_IN_GA(x1) 4.79/2.07 4.79/2.07 4.79/2.07 We have to consider all (P,R,Pi)-chains 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (9) PiDPToQDPProof (SOUND) 4.79/2.07 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (10) 4.79/2.07 Obligation: 4.79/2.07 Q DP problem: 4.79/2.07 The TRS P consists of the following rules: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3)) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3))) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T)) -> FLAT_IN_GA(T) 4.79/2.07 4.79/2.07 R is empty. 4.79/2.07 Q is empty. 4.79/2.07 We have to consider all (P,Q,R)-chains. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (11) UsableRulesReductionPairsProof (EQUIVALENT) 4.79/2.07 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.79/2.07 4.79/2.07 The following dependency pairs can be deleted: 4.79/2.07 4.79/2.07 FLAT_IN_GA(tree(X, tree(Y, T1, T2), T3)) -> FLAT_IN_GA(tree(Y, T1, tree(X, T2, T3))) 4.79/2.07 FLAT_IN_GA(tree(X, niltree, T)) -> FLAT_IN_GA(T) 4.79/2.07 No rules are removed from R. 4.79/2.07 4.79/2.07 Used ordering: POLO with Polynomial interpretation [POLO]: 4.79/2.07 4.79/2.07 POL(FLAT_IN_GA(x_1)) = 2*x_1 4.79/2.07 POL(niltree) = 0 4.79/2.07 POL(tree(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (12) 4.79/2.07 Obligation: 4.79/2.07 Q DP problem: 4.79/2.07 P is empty. 4.79/2.07 R is empty. 4.79/2.07 Q is empty. 4.79/2.07 We have to consider all (P,Q,R)-chains. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (13) PisEmptyProof (EQUIVALENT) 4.79/2.07 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (14) 4.79/2.07 YES 4.79/2.10 EOF