8.79/3.04 WORST_CASE(Omega(n^1), O(n^1)) 8.79/3.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.79/3.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.79/3.05 8.79/3.05 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.79/3.05 8.79/3.05 (0) CpxTRS 8.79/3.05 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 8.79/3.05 (2) CpxTRS 8.79/3.05 (3) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 8.79/3.05 (4) BOUNDS(1, n^1) 8.79/3.05 (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 8.79/3.05 (6) TRS for Loop Detection 8.79/3.05 (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 8.79/3.05 (8) BEST 8.79/3.05 (9) proven lower bound 8.79/3.05 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 8.79/3.05 (11) BOUNDS(n^1, INF) 8.79/3.05 (12) TRS for Loop Detection 8.79/3.05 8.79/3.05 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (0) 8.79/3.05 Obligation: 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.79/3.05 8.79/3.05 8.79/3.05 The TRS R consists of the following rules: 8.79/3.05 8.79/3.05 a__f(f(X)) -> a__c(f(g(f(X)))) 8.79/3.05 a__c(X) -> d(X) 8.79/3.05 a__h(X) -> a__c(d(X)) 8.79/3.05 mark(f(X)) -> a__f(mark(X)) 8.79/3.05 mark(c(X)) -> a__c(X) 8.79/3.05 mark(h(X)) -> a__h(mark(X)) 8.79/3.05 mark(g(X)) -> g(X) 8.79/3.05 mark(d(X)) -> d(X) 8.79/3.05 a__f(X) -> f(X) 8.79/3.05 a__c(X) -> c(X) 8.79/3.05 a__h(X) -> h(X) 8.79/3.05 8.79/3.05 S is empty. 8.79/3.05 Rewrite Strategy: INNERMOST 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 8.79/3.05 transformed relative TRS to TRS 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (2) 8.79/3.05 Obligation: 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 8.79/3.05 8.79/3.05 8.79/3.05 The TRS R consists of the following rules: 8.79/3.05 8.79/3.05 a__f(f(X)) -> a__c(f(g(f(X)))) 8.79/3.05 a__c(X) -> d(X) 8.79/3.05 a__h(X) -> a__c(d(X)) 8.79/3.05 mark(f(X)) -> a__f(mark(X)) 8.79/3.05 mark(c(X)) -> a__c(X) 8.79/3.05 mark(h(X)) -> a__h(mark(X)) 8.79/3.05 mark(g(X)) -> g(X) 8.79/3.05 mark(d(X)) -> d(X) 8.79/3.05 a__f(X) -> f(X) 8.79/3.05 a__c(X) -> c(X) 8.79/3.05 a__h(X) -> h(X) 8.79/3.05 8.79/3.05 S is empty. 8.79/3.05 Rewrite Strategy: INNERMOST 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (3) CpxTrsMatchBoundsProof (FINISHED) 8.79/3.05 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3. 8.79/3.05 The certificate found is represented by the following graph. 8.79/3.05 8.79/3.05 "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 8.79/3.05 {(1,2,[a__f_1|0, a__c_1|0, a__h_1|0, mark_1|0, f_1|1, d_1|1, c_1|1, h_1|1, a__c_1|1, g_1|1, d_1|2, c_1|2]), (1,3,[a__c_1|1, d_1|2, c_1|2]), (1,6,[a__c_1|1, d_1|2, c_1|2]), (1,7,[a__f_1|1, f_1|2]), (1,8,[a__h_1|1, h_1|2]), (1,9,[a__c_1|2, d_1|3, c_1|3]), (1,10,[a__c_1|2, d_1|3, c_1|3]), (2,2,[f_1|0, g_1|0, d_1|0, c_1|0, h_1|0]), (3,4,[f_1|1]), (4,5,[g_1|1]), (5,2,[f_1|1]), (6,2,[d_1|1]), (7,2,[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]), (7,7,[a__f_1|1, f_1|2]), (7,8,[a__h_1|1, h_1|2]), (7,9,[a__c_1|2, d_1|3, c_1|3]), (7,10,[a__c_1|2, d_1|3, c_1|3]), (8,2,[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]), (8,7,[a__f_1|1, f_1|2]), (8,8,[a__h_1|1, h_1|2]), (8,9,[a__c_1|2, d_1|3, c_1|3]), (8,10,[a__c_1|2, d_1|3, c_1|3]), (9,8,[d_1|2]), (10,11,[f_1|2]), (11,12,[g_1|2]), (12,7,[f_1|2])}" 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (4) 8.79/3.05 BOUNDS(1, n^1) 8.79/3.05 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 8.79/3.05 Transformed a relative TRS into a decreasing-loop problem. 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (6) 8.79/3.05 Obligation: 8.79/3.05 Analyzing the following TRS for decreasing loops: 8.79/3.05 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.79/3.05 8.79/3.05 8.79/3.05 The TRS R consists of the following rules: 8.79/3.05 8.79/3.05 a__f(f(X)) -> a__c(f(g(f(X)))) 8.79/3.05 a__c(X) -> d(X) 8.79/3.05 a__h(X) -> a__c(d(X)) 8.79/3.05 mark(f(X)) -> a__f(mark(X)) 8.79/3.05 mark(c(X)) -> a__c(X) 8.79/3.05 mark(h(X)) -> a__h(mark(X)) 8.79/3.05 mark(g(X)) -> g(X) 8.79/3.05 mark(d(X)) -> d(X) 8.79/3.05 a__f(X) -> f(X) 8.79/3.05 a__c(X) -> c(X) 8.79/3.05 a__h(X) -> h(X) 8.79/3.05 8.79/3.05 S is empty. 8.79/3.05 Rewrite Strategy: INNERMOST 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (7) DecreasingLoopProof (LOWER BOUND(ID)) 8.79/3.05 The following loop(s) give(s) rise to the lower bound Omega(n^1): 8.79/3.05 8.79/3.05 The rewrite sequence 8.79/3.05 8.79/3.05 mark(f(X)) ->^+ a__f(mark(X)) 8.79/3.05 8.79/3.05 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 8.79/3.05 8.79/3.05 The pumping substitution is [X / f(X)]. 8.79/3.05 8.79/3.05 The result substitution is [ ]. 8.79/3.05 8.79/3.05 8.79/3.05 8.79/3.05 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (8) 8.79/3.05 Complex Obligation (BEST) 8.79/3.05 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (9) 8.79/3.05 Obligation: 8.79/3.05 Proved the lower bound n^1 for the following obligation: 8.79/3.05 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.79/3.05 8.79/3.05 8.79/3.05 The TRS R consists of the following rules: 8.79/3.05 8.79/3.05 a__f(f(X)) -> a__c(f(g(f(X)))) 8.79/3.05 a__c(X) -> d(X) 8.79/3.05 a__h(X) -> a__c(d(X)) 8.79/3.05 mark(f(X)) -> a__f(mark(X)) 8.79/3.05 mark(c(X)) -> a__c(X) 8.79/3.05 mark(h(X)) -> a__h(mark(X)) 8.79/3.05 mark(g(X)) -> g(X) 8.79/3.05 mark(d(X)) -> d(X) 8.79/3.05 a__f(X) -> f(X) 8.79/3.05 a__c(X) -> c(X) 8.79/3.05 a__h(X) -> h(X) 8.79/3.05 8.79/3.05 S is empty. 8.79/3.05 Rewrite Strategy: INNERMOST 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (10) LowerBoundPropagationProof (FINISHED) 8.79/3.05 Propagated lower bound. 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (11) 8.79/3.05 BOUNDS(n^1, INF) 8.79/3.05 8.79/3.05 ---------------------------------------- 8.79/3.05 8.79/3.05 (12) 8.79/3.05 Obligation: 8.79/3.05 Analyzing the following TRS for decreasing loops: 8.79/3.05 8.79/3.05 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.79/3.05 8.79/3.05 8.79/3.05 The TRS R consists of the following rules: 8.79/3.05 8.79/3.05 a__f(f(X)) -> a__c(f(g(f(X)))) 8.79/3.05 a__c(X) -> d(X) 8.79/3.05 a__h(X) -> a__c(d(X)) 8.79/3.05 mark(f(X)) -> a__f(mark(X)) 8.79/3.05 mark(c(X)) -> a__c(X) 8.79/3.05 mark(h(X)) -> a__h(mark(X)) 8.79/3.05 mark(g(X)) -> g(X) 8.79/3.05 mark(d(X)) -> d(X) 8.79/3.05 a__f(X) -> f(X) 8.79/3.05 a__c(X) -> c(X) 8.79/3.05 a__h(X) -> h(X) 8.79/3.05 8.79/3.05 S is empty. 8.79/3.05 Rewrite Strategy: INNERMOST 8.79/3.08 EOF