/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 32 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 4 ms] (6) QTRS (7) AAECC Innermost [EQUIVALENT, 0 ms] (8) QTRS (9) DependencyPairsProof [EQUIVALENT, 0 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) AND (13) QDP (14) UsableRulesProof [EQUIVALENT, 0 ms] (15) QDP (16) QReductionProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QReductionProof [EQUIVALENT, 0 ms] (24) QDP (25) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms] (26) YES ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(x) -> g(f(x)) g(g(f(x))) -> x Outermost Strategy. ---------------------------------------- (1) Raffelsieper-Zantema-Transformation (SOUND) We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) down(g(g(f(x)))) -> up(x) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) f_flat(up(x_1)) -> up(f(x_1)) g_flat(up(x_1)) -> up(g(x_1)) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(down(x_1)) = 2*x_1 POL(f(x_1)) = 2*x_1 POL(f_flat(x_1)) = 1 + 2*x_1 POL(fresh_constant) = 0 POL(g(x_1)) = x_1 POL(g_flat(x_1)) = x_1 POL(top(x_1)) = 2*x_1 POL(up(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f_flat(up(x_1)) -> up(f(x_1)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) down(g(g(f(x)))) -> up(x) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(down(x_1)) = 2*x_1 POL(f(x_1)) = 2 + x_1 POL(fresh_constant) = 0 POL(g(x_1)) = x_1 POL(g_flat(x_1)) = x_1 POL(top(x_1)) = x_1 POL(up(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: down(g(g(f(x)))) -> up(x) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) Q is empty. ---------------------------------------- (7) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) down(f(x)) -> up(g(f(x))) The TRS R 2 is top(up(x)) -> top(down(x)) The signature Sigma is {top_1} ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) ---------------------------------------- (9) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) TOP(up(x)) -> DOWN(x) DOWN(g(f(y3))) -> G_FLAT(down(f(y3))) DOWN(g(f(y3))) -> DOWN(f(y3)) DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant)) DOWN(g(fresh_constant)) -> DOWN(fresh_constant) DOWN(g(g(g(y7)))) -> G_FLAT(down(g(g(y7)))) DOWN(g(g(g(y7)))) -> DOWN(g(g(y7))) DOWN(g(g(fresh_constant))) -> G_FLAT(down(g(fresh_constant))) DOWN(g(g(fresh_constant))) -> DOWN(g(fresh_constant)) The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(g(g(y7)))) -> DOWN(g(g(y7))) The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(g(g(y7)))) -> DOWN(g(g(y7))) R is empty. The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(g(g(g(y7)))) -> DOWN(g(g(y7))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *DOWN(g(g(g(y7)))) -> DOWN(g(g(y7))) The graph contains the following edges 1 > 1 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) top(up(x)) -> top(down(x)) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) top(up(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(up(x0)) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(up(x)) -> TOP(down(x)) The TRS R consists of the following rules: down(f(x)) -> up(g(f(x))) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) The set Q consists of the following terms: down(f(x0)) down(g(f(x0))) down(g(fresh_constant)) down(g(g(g(x0)))) down(g(g(fresh_constant))) g_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) RFCMatchBoundsDPProof (EQUIVALENT) Finiteness of the DP problem can be shown by a matchbound of 3. As the DP problem is minimal we only have to initialize the certificate graph by the rules of P: TOP(up(x)) -> TOP(down(x)) To find matches we regarded all rules of R and P: down(f(x)) -> up(g(f(x))) down(g(f(y3))) -> g_flat(down(f(y3))) down(g(fresh_constant)) -> g_flat(down(fresh_constant)) down(g(g(g(y7)))) -> g_flat(down(g(g(y7)))) down(g(g(fresh_constant))) -> g_flat(down(g(fresh_constant))) g_flat(up(x_1)) -> up(g(x_1)) TOP(up(x)) -> TOP(down(x)) The certificate found is represented by the following graph. The certificate consists of the following enumerated nodes: 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367 Node 346 is start node and node 347 is final node. Those nodes are connected through the following edges: * 346 to 348 labelled TOP_1(0)* 346 to 356 labelled TOP_1(1)* 346 to 367 labelled TOP_1(2)* 347 to 347 labelled #_1(0)* 348 to 347 labelled down_1(0)* 348 to 349 labelled up_1(1)* 348 to 351 labelled g_flat_1(1)* 348 to 353 labelled g_flat_1(1)* 348 to 361 labelled up_1(2)* 349 to 350 labelled g_1(1)* 350 to 347 labelled f_1(1)* 351 to 352 labelled down_1(1)* 351 to 357 labelled up_1(2)* 352 to 347 labelled f_1(1), fresh_constant(1)* 353 to 354 labelled down_1(1)* 353 to 359 labelled g_flat_1(2)* 353 to 353 labelled g_flat_1(1)* 354 to 355 labelled g_1(1)* 355 to 347 labelled g_1(1), fresh_constant(1)* 356 to 349 labelled down_1(1)* 356 to 362 labelled g_flat_1(2)* 356 to 361 labelled down_1(1)* 356 to 366 labelled up_1(3)* 357 to 358 labelled g_1(2)* 358 to 347 labelled f_1(2)* 359 to 360 labelled down_1(2)* 360 to 347 labelled fresh_constant(2)* 361 to 357 labelled g_1(2)* 362 to 363 labelled down_1(2)* 362 to 364 labelled up_1(3)* 363 to 347 labelled f_1(2)* 364 to 365 labelled g_1(3)* 365 to 347 labelled f_1(3)* 366 to 364 labelled g_1(3)* 367 to 366 labelled down_1(2) ---------------------------------------- (26) YES