/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, 19 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 21 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(h(x)) -> f(i(x)) h(x) -> f(h(x)) i(x) -> h(x) f(i(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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) down(f(i(x))) -> up(x) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) h_flat(up(x_1)) -> up(h(x_1)) i_flat(up(x_1)) -> up(i(x_1)) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(down(x_1)) = 2 + 2*x_1 POL(f(x_1)) = x_1 POL(f_flat(x_1)) = x_1 POL(fresh_constant) = 0 POL(h(x_1)) = x_1 POL(h_flat(x_1)) = 1 + 2*x_1 POL(i(x_1)) = x_1 POL(i_flat(x_1)) = 1 + 2*x_1 POL(top(x_1)) = 2*x_1 POL(up(x_1)) = 2 + 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: h_flat(up(x_1)) -> up(h(x_1)) i_flat(up(x_1)) -> up(i(x_1)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) down(f(i(x))) -> up(x) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(down(x_1)) = 2*x_1 POL(f(x_1)) = x_1 POL(f_flat(x_1)) = x_1 POL(fresh_constant) = 0 POL(h(x_1)) = 1 + 2*x_1 POL(i(x_1)) = 1 + 2*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(f(i(x))) -> up(x) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: down(f(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) Q is empty. ---------------------------------------- (7) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) down(f(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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(f(f(y4))) -> F_FLAT(down(f(y4))) DOWN(f(f(y4))) -> DOWN(f(y4)) DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) DOWN(f(fresh_constant)) -> DOWN(fresh_constant) The TRS R consists of the following rules: down(f(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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 4 less nodes. ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(f(y4))) -> DOWN(f(y4)) The TRS R consists of the following rules: down(f(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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(f(f(y4))) -> DOWN(f(y4)) R is empty. The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_flat(up(x0)) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: DOWN(f(f(y4))) -> DOWN(f(y4)) 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(f(f(y4))) -> DOWN(f(y4)) 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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) top(up(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) The set Q consists of the following terms: down(f(h(x0))) down(h(x0)) down(i(x0)) down(f(f(x0))) down(f(fresh_constant)) f_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 9. 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(h(x))) -> up(f(i(x))) down(h(x)) -> up(f(h(x))) down(i(x)) -> up(h(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(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: 265, 266, 267, 268, 269, 270, 271, 272, 276, 277, 278, 279, 280, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 311, 312, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332 Node 265 is start node and node 266 is final node. Those nodes are connected through the following edges: * 265 to 267 labelled TOP_1(0)* 265 to 272 labelled TOP_1(1)* 265 to 280 labelled TOP_1(2)* 265 to 289 labelled TOP_1(3)* 265 to 295 labelled TOP_1(4)* 266 to 266 labelled #_1(0)* 267 to 266 labelled down_1(0)* 267 to 268 labelled up_1(1)* 267 to 269 labelled up_1(1)* 267 to 270 labelled f_flat_1(1)* 267 to 276 labelled up_1(2)* 268 to 269 labelled f_1(1)* 269 to 266 labelled i_1(1), h_1(1)* 270 to 271 labelled down_1(1)* 270 to 268 labelled up_1(1)* 270 to 270 labelled f_flat_1(1)* 270 to 276 labelled up_1(2)* 271 to 266 labelled f_1(1), fresh_constant(1)* 272 to 268 labelled down_1(1)* 272 to 269 labelled down_1(1)* 272 to 277 labelled up_1(2)* 272 to 278 labelled up_1(2)* 272 to 276 labelled down_1(1)* 272 to 287 labelled f_flat_1(2)* 272 to 292 labelled up_1(3)* 276 to 268 labelled f_1(2)* 276 to 276 labelled f_1(2)* 277 to 266 labelled h_1(2)* 278 to 279 labelled f_1(2)* 279 to 266 labelled h_1(2), i_1(2)* 280 to 277 labelled down_1(2)* 280 to 278 labelled down_1(2)* 280 to 285 labelled up_1(3)* 280 to 292 labelled down_1(2)* 280 to 297 labelled f_flat_1(3)* 280 to 301 labelled up_1(4)* 285 to 286 labelled f_1(3)* 286 to 266 labelled h_1(3), i_1(3)* 287 to 288 labelled down_1(2)* 287 to 278 labelled up_1(2)* 287 to 287 labelled f_flat_1(2)* 287 to 290 labelled f_flat_1(3)* 287 to 292 labelled up_1(3)* 287 to 296 labelled up_1(4)* 288 to 269 labelled f_1(2)* 288 to 268 labelled f_1(2)* 288 to 276 labelled f_1(2)* 289 to 285 labelled down_1(3)* 289 to 293 labelled up_1(4)* 289 to 301 labelled down_1(3)* 289 to 305 labelled f_flat_1(4)* 289 to 311 labelled up_1(5)* 290 to 291 labelled down_1(3)* 290 to 287 labelled f_flat_1(2)* 290 to 290 labelled f_flat_1(3)* 290 to 292 labelled up_1(3)* 290 to 296 labelled up_1(4)* 291 to 268 labelled f_1(3)* 291 to 276 labelled f_1(3)* 292 to 278 labelled f_1(3)* 292 to 292 labelled f_1(3)* 292 to 296 labelled f_1(3)* 293 to 294 labelled f_1(4)* 294 to 266 labelled i_1(4)* 295 to 293 labelled down_1(4)* 295 to 311 labelled down_1(4)* 295 to 319 labelled f_flat_1(5)* 296 to 292 labelled f_1(4)* 296 to 296 labelled f_1(4)* 297 to 298 labelled down_1(3)* 297 to 285 labelled up_1(3)* 297 to 297 labelled f_flat_1(3)* 297 to 299 labelled f_flat_1(4)* 297 to 301 labelled up_1(4)* 297 to 304 labelled up_1(5)* 298 to 279 labelled f_1(3)* 298 to 278 labelled f_1(3)* 298 to 292 labelled f_1(3)* 298 to 296 labelled f_1(3)* 299 to 300 labelled down_1(4)* 299 to 297 labelled f_flat_1(3)* 299 to 299 labelled f_flat_1(4)* 299 to 301 labelled up_1(4)* 299 to 302 labelled f_flat_1(5)* 299 to 304 labelled up_1(5)* 299 to 312 labelled up_1(6)* 300 to 278 labelled f_1(4)* 300 to 292 labelled f_1(4)* 300 to 296 labelled f_1(4)* 301 to 285 labelled f_1(4)* 301 to 301 labelled f_1(4)* 301 to 304 labelled f_1(4)* 302 to 303 labelled down_1(5)* 302 to 299 labelled f_flat_1(4)* 302 to 302 labelled f_flat_1(5)* 302 to 304 labelled up_1(5)* 302 to 312 labelled up_1(6)* 303 to 292 labelled f_1(5)* 303 to 296 labelled f_1(5)* 304 to 301 labelled f_1(5)* 304 to 304 labelled f_1(5)* 304 to 312 labelled f_1(5)* 305 to 306 labelled down_1(4)* 305 to 293 labelled up_1(4)* 305 to 305 labelled f_flat_1(4)* 305 to 307 labelled f_flat_1(5)* 305 to 311 labelled up_1(5)* 305 to 318 labelled up_1(6)* 306 to 286 labelled f_1(4)* 306 to 285 labelled f_1(4)* 306 to 301 labelled f_1(4)* 306 to 304 labelled f_1(4)* 306 to 312 labelled f_1(4)* 307 to 308 labelled down_1(5)* 307 to 305 labelled f_flat_1(4)* 307 to 307 labelled f_flat_1(5)* 307 to 311 labelled up_1(5)* 307 to 316 labelled f_flat_1(6)* 307 to 318 labelled up_1(6)* 307 to 325 labelled up_1(7)* 308 to 285 labelled f_1(5)* 308 to 301 labelled f_1(5)* 308 to 304 labelled f_1(5)* 308 to 312 labelled f_1(5)* 311 to 293 labelled f_1(5)* 311 to 311 labelled f_1(5)* 311 to 318 labelled f_1(5)* 312 to 304 labelled f_1(6)* 312 to 312 labelled f_1(6)* 316 to 317 labelled down_1(6)* 316 to 307 labelled f_flat_1(5)* 316 to 316 labelled f_flat_1(6)* 316 to 318 labelled up_1(6)* 316 to 323 labelled f_flat_1(7)* 316 to 325 labelled up_1(7)* 316 to 328 labelled up_1(8)* 317 to 301 labelled f_1(6)* 317 to 304 labelled f_1(6)* 317 to 312 labelled f_1(6)* 318 to 311 labelled f_1(6)* 318 to 318 labelled f_1(6)* 318 to 325 labelled f_1(6)* 319 to 320 labelled down_1(5)* 319 to 319 labelled f_flat_1(5)* 319 to 321 labelled f_flat_1(6)* 320 to 294 labelled f_1(5)* 320 to 293 labelled f_1(5)* 320 to 311 labelled f_1(5)* 320 to 318 labelled f_1(5)* 320 to 325 labelled f_1(5)* 321 to 322 labelled down_1(6)* 321 to 319 labelled f_flat_1(5)* 321 to 321 labelled f_flat_1(6)* 321 to 326 labelled f_flat_1(7)* 322 to 293 labelled f_1(6)* 322 to 311 labelled f_1(6)* 322 to 318 labelled f_1(6)* 322 to 325 labelled f_1(6)* 322 to 328 labelled f_1(6)* 323 to 324 labelled down_1(7)* 323 to 316 labelled f_flat_1(6)* 323 to 323 labelled f_flat_1(7)* 323 to 325 labelled up_1(7)* 323 to 328 labelled up_1(8)* 324 to 304 labelled f_1(7)* 324 to 312 labelled f_1(7)* 325 to 318 labelled f_1(7)* 325 to 325 labelled f_1(7)* 325 to 328 labelled f_1(7)* 326 to 327 labelled down_1(7)* 326 to 321 labelled f_flat_1(6)* 326 to 326 labelled f_flat_1(7)* 326 to 329 labelled f_flat_1(8)* 327 to 311 labelled f_1(7)* 327 to 318 labelled f_1(7)* 327 to 325 labelled f_1(7)* 327 to 328 labelled f_1(7)* 328 to 325 labelled f_1(8)* 328 to 328 labelled f_1(8)* 329 to 330 labelled down_1(8)* 329 to 326 labelled f_flat_1(7)* 329 to 329 labelled f_flat_1(8)* 329 to 331 labelled f_flat_1(9)* 330 to 318 labelled f_1(8)* 330 to 325 labelled f_1(8)* 330 to 328 labelled f_1(8)* 331 to 332 labelled down_1(9)* 331 to 329 labelled f_flat_1(8)* 331 to 331 labelled f_flat_1(9)* 332 to 325 labelled f_1(9)* 332 to 328 labelled f_1(9) ---------------------------------------- (26) YES