/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/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, 21 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 4 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 0 ms] (8) QTRS (9) AAECC Innermost [EQUIVALENT, 0 ms] (10) QTRS (11) DependencyPairsProof [EQUIVALENT, 0 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) AND (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QReductionProof [EQUIVALENT, 0 ms] (19) QDP (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] (21) YES (22) QDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) QDP (25) QReductionProof [EQUIVALENT, 0 ms] (26) QDP (27) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms] (28) 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)) -> a 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(a) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(a)) -> f_flat(down(a)) 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(a) = 0 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)) = x_1 POL(h_flat(x_1)) = 1 + 2*x_1 POL(i(x_1)) = x_1 POL(i_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: h_flat(up(x_1)) -> up(h(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(a) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(a)) -> f_flat(down(a)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) i_flat(up(x_1)) -> up(i(x_1)) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(a) = 0 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)) = x_1 POL(i(x_1)) = x_1 POL(i_flat(x_1)) = 2 + 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: i_flat(up(x_1)) -> up(i(x_1)) ---------------------------------------- (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)) down(f(i(x))) -> up(a) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(a)) -> f_flat(down(a)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(a) = 0 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)) = 2 + x_1 POL(i(x_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(a) ---------------------------------------- (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(a)) -> f_flat(down(a)) down(f(fresh_constant)) -> f_flat(down(fresh_constant)) f_flat(up(x_1)) -> up(f(x_1)) Q is empty. ---------------------------------------- (9) 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(a)) -> f_flat(down(a)) 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} ---------------------------------------- (10) 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(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) ---------------------------------------- (11) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (12) 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(a)) -> F_FLAT(down(a)) DOWN(f(a)) -> DOWN(a) 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(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (14) Complex Obligation (AND) ---------------------------------------- (15) 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(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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. ---------------------------------------- (17) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) ---------------------------------------- (19) 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. ---------------------------------------- (20) 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 ---------------------------------------- (21) YES ---------------------------------------- (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)) top(up(x)) -> top(down(x)) down(f(f(y4))) -> f_flat(down(f(y4))) down(f(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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. ---------------------------------------- (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(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) 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)) ---------------------------------------- (26) 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(a)) -> f_flat(down(a)) 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(a)) down(f(fresh_constant)) f_flat(up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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(a)) -> f_flat(down(a)) 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: 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 360, 361, 362, 363, 364, 365, 366, 367 Node 310 is start node and node 311 is final node. Those nodes are connected through the following edges: * 310 to 312 labelled TOP_1(0)* 310 to 317 labelled TOP_1(1)* 310 to 322 labelled TOP_1(2)* 310 to 327 labelled TOP_1(3)* 310 to 333 labelled TOP_1(4)* 311 to 311 labelled #_1(0)* 312 to 311 labelled down_1(0)* 312 to 313 labelled up_1(1)* 312 to 314 labelled up_1(1)* 312 to 315 labelled f_flat_1(1)* 312 to 318 labelled up_1(2)* 313 to 314 labelled f_1(1)* 314 to 311 labelled i_1(1), h_1(1)* 315 to 316 labelled down_1(1)* 315 to 313 labelled up_1(1)* 315 to 315 labelled f_flat_1(1)* 315 to 318 labelled up_1(2)* 316 to 311 labelled f_1(1), a(1), fresh_constant(1)* 317 to 313 labelled down_1(1)* 317 to 314 labelled down_1(1)* 317 to 319 labelled up_1(2)* 317 to 320 labelled up_1(2)* 317 to 318 labelled down_1(1)* 317 to 325 labelled f_flat_1(2)* 317 to 330 labelled up_1(3)* 318 to 313 labelled f_1(2)* 318 to 318 labelled f_1(2)* 319 to 311 labelled h_1(2)* 320 to 321 labelled f_1(2)* 321 to 311 labelled h_1(2), i_1(2)* 322 to 319 labelled down_1(2)* 322 to 320 labelled down_1(2)* 322 to 323 labelled up_1(3)* 322 to 330 labelled down_1(2)* 322 to 335 labelled f_flat_1(3)* 322 to 339 labelled up_1(4)* 323 to 324 labelled f_1(3)* 324 to 311 labelled h_1(3), i_1(3)* 325 to 326 labelled down_1(2)* 325 to 320 labelled up_1(2)* 325 to 325 labelled f_flat_1(2)* 325 to 328 labelled f_flat_1(3)* 325 to 330 labelled up_1(3)* 325 to 334 labelled up_1(4)* 326 to 314 labelled f_1(2)* 326 to 313 labelled f_1(2)* 326 to 318 labelled f_1(2)* 327 to 323 labelled down_1(3)* 327 to 331 labelled up_1(4)* 327 to 339 labelled down_1(3)* 327 to 344 labelled f_flat_1(4)* 327 to 348 labelled up_1(5)* 328 to 329 labelled down_1(3)* 328 to 325 labelled f_flat_1(2)* 328 to 328 labelled f_flat_1(3)* 328 to 330 labelled up_1(3)* 328 to 334 labelled up_1(4)* 329 to 313 labelled f_1(3)* 329 to 318 labelled f_1(3)* 330 to 320 labelled f_1(3)* 330 to 330 labelled f_1(3)* 330 to 334 labelled f_1(3)* 331 to 332 labelled f_1(4)* 332 to 311 labelled i_1(4)* 333 to 331 labelled down_1(4)* 333 to 348 labelled down_1(4)* 333 to 353 labelled f_flat_1(5)* 334 to 330 labelled f_1(4)* 334 to 334 labelled f_1(4)* 335 to 336 labelled down_1(3)* 335 to 323 labelled up_1(3)* 335 to 335 labelled f_flat_1(3)* 335 to 337 labelled f_flat_1(4)* 335 to 339 labelled up_1(4)* 335 to 343 labelled up_1(5)* 336 to 321 labelled f_1(3)* 336 to 320 labelled f_1(3)* 336 to 330 labelled f_1(3)* 336 to 334 labelled f_1(3)* 337 to 338 labelled down_1(4)* 337 to 335 labelled f_flat_1(3)* 337 to 337 labelled f_flat_1(4)* 337 to 339 labelled up_1(4)* 337 to 341 labelled f_flat_1(5)* 337 to 343 labelled up_1(5)* 337 to 349 labelled up_1(6)* 338 to 320 labelled f_1(4)* 338 to 330 labelled f_1(4)* 338 to 334 labelled f_1(4)* 339 to 323 labelled f_1(4)* 339 to 339 labelled f_1(4)* 339 to 343 labelled f_1(4)* 341 to 342 labelled down_1(5)* 341 to 337 labelled f_flat_1(4)* 341 to 341 labelled f_flat_1(5)* 341 to 343 labelled up_1(5)* 341 to 349 labelled up_1(6)* 342 to 330 labelled f_1(5)* 342 to 334 labelled f_1(5)* 343 to 339 labelled f_1(5)* 343 to 343 labelled f_1(5)* 343 to 349 labelled f_1(5)* 344 to 345 labelled down_1(4)* 344 to 331 labelled up_1(4)* 344 to 344 labelled f_flat_1(4)* 344 to 346 labelled f_flat_1(5)* 344 to 348 labelled up_1(5)* 344 to 352 labelled up_1(6)* 345 to 324 labelled f_1(4)* 345 to 323 labelled f_1(4)* 345 to 339 labelled f_1(4)* 345 to 343 labelled f_1(4)* 345 to 349 labelled f_1(4)* 346 to 347 labelled down_1(5)* 346 to 344 labelled f_flat_1(4)* 346 to 346 labelled f_flat_1(5)* 346 to 348 labelled up_1(5)* 346 to 350 labelled f_flat_1(6)* 346 to 352 labelled up_1(6)* 346 to 360 labelled up_1(7)* 347 to 323 labelled f_1(5)* 347 to 339 labelled f_1(5)* 347 to 343 labelled f_1(5)* 347 to 349 labelled f_1(5)* 348 to 331 labelled f_1(5)* 348 to 348 labelled f_1(5)* 348 to 352 labelled f_1(5)* 349 to 343 labelled f_1(6)* 349 to 349 labelled f_1(6)* 350 to 351 labelled down_1(6)* 350 to 346 labelled f_flat_1(5)* 350 to 350 labelled f_flat_1(6)* 350 to 352 labelled up_1(6)* 350 to 357 labelled f_flat_1(7)* 350 to 360 labelled up_1(7)* 350 to 363 labelled up_1(8)* 351 to 339 labelled f_1(6)* 351 to 343 labelled f_1(6)* 351 to 349 labelled f_1(6)* 352 to 348 labelled f_1(6)* 352 to 352 labelled f_1(6)* 352 to 360 labelled f_1(6)* 353 to 354 labelled down_1(5)* 353 to 353 labelled f_flat_1(5)* 353 to 355 labelled f_flat_1(6)* 354 to 332 labelled f_1(5)* 354 to 331 labelled f_1(5)* 354 to 348 labelled f_1(5)* 354 to 352 labelled f_1(5)* 354 to 360 labelled f_1(5)* 355 to 356 labelled down_1(6)* 355 to 353 labelled f_flat_1(5)* 355 to 355 labelled f_flat_1(6)* 355 to 361 labelled f_flat_1(7)* 356 to 331 labelled f_1(6)* 356 to 348 labelled f_1(6)* 356 to 352 labelled f_1(6)* 356 to 360 labelled f_1(6)* 356 to 363 labelled f_1(6)* 357 to 358 labelled down_1(7)* 357 to 350 labelled f_flat_1(6)* 357 to 357 labelled f_flat_1(7)* 357 to 360 labelled up_1(7)* 357 to 363 labelled up_1(8)* 358 to 343 labelled f_1(7)* 358 to 349 labelled f_1(7)* 360 to 352 labelled f_1(7)* 360 to 360 labelled f_1(7)* 360 to 363 labelled f_1(7)* 361 to 362 labelled down_1(7)* 361 to 355 labelled f_flat_1(6)* 361 to 361 labelled f_flat_1(7)* 361 to 364 labelled f_flat_1(8)* 362 to 348 labelled f_1(7)* 362 to 352 labelled f_1(7)* 362 to 360 labelled f_1(7)* 362 to 363 labelled f_1(7)* 363 to 360 labelled f_1(8)* 363 to 363 labelled f_1(8)* 364 to 365 labelled down_1(8)* 364 to 361 labelled f_flat_1(7)* 364 to 364 labelled f_flat_1(8)* 364 to 366 labelled f_flat_1(9)* 365 to 352 labelled f_1(8)* 365 to 360 labelled f_1(8)* 365 to 363 labelled f_1(8)* 366 to 367 labelled down_1(9)* 366 to 364 labelled f_flat_1(8)* 366 to 366 labelled f_flat_1(9)* 367 to 360 labelled f_1(9)* 367 to 363 labelled f_1(9) ---------------------------------------- (28) YES