39.31/11.48 WORST_CASE(Omega(n^1), O(n^1)) 39.51/11.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 39.51/11.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 39.51/11.51 39.51/11.51 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.51/11.51 39.51/11.51 (0) CpxTRS 39.51/11.51 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 39.51/11.51 (2) CpxTRS 39.51/11.51 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 39.51/11.51 (4) CpxTRS 39.51/11.51 (5) CpxTrsMatchBoundsTAProof [FINISHED, 373 ms] 39.51/11.51 (6) BOUNDS(1, n^1) 39.51/11.51 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 39.51/11.51 (8) TRS for Loop Detection 39.51/11.51 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 39.51/11.51 (10) BEST 39.51/11.51 (11) proven lower bound 39.51/11.51 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 39.51/11.51 (13) BOUNDS(n^1, INF) 39.51/11.51 (14) TRS for Loop Detection 39.51/11.51 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (0) 39.51/11.51 Obligation: 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) 39.51/11.51 active(sel(0, cons(X, Z))) -> mark(X) 39.51/11.51 active(first(0, Z)) -> mark(nil) 39.51/11.51 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 39.51/11.51 active(from(X)) -> mark(cons(X, from(s(X)))) 39.51/11.51 active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(sel1(0, cons(X, Z))) -> mark(quote(X)) 39.51/11.51 active(first1(0, Z)) -> mark(nil1) 39.51/11.51 active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) 39.51/11.51 active(quote(0)) -> mark(01) 39.51/11.51 active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) 39.51/11.51 active(quote1(nil)) -> mark(nil1) 39.51/11.51 active(quote(s(X))) -> mark(s1(quote(X))) 39.51/11.51 active(quote(sel(X, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(quote1(first(X, Z))) -> mark(first1(X, Z)) 39.51/11.51 active(unquote(01)) -> mark(0) 39.51/11.51 active(unquote(s1(X))) -> mark(s(unquote(X))) 39.51/11.51 active(unquote1(nil1)) -> mark(nil) 39.51/11.51 active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) 39.51/11.51 active(fcons(X, Z)) -> mark(cons(X, Z)) 39.51/11.51 active(sel(X1, X2)) -> sel(active(X1), X2) 39.51/11.51 active(sel(X1, X2)) -> sel(X1, active(X2)) 39.51/11.51 active(s(X)) -> s(active(X)) 39.51/11.51 active(cons(X1, X2)) -> cons(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(X1, active(X2)) 39.51/11.51 active(from(X)) -> from(active(X)) 39.51/11.51 active(sel1(X1, X2)) -> sel1(active(X1), X2) 39.51/11.51 active(sel1(X1, X2)) -> sel1(X1, active(X2)) 39.51/11.51 active(first1(X1, X2)) -> first1(active(X1), X2) 39.51/11.51 active(first1(X1, X2)) -> first1(X1, active(X2)) 39.51/11.51 active(cons1(X1, X2)) -> cons1(active(X1), X2) 39.51/11.51 active(cons1(X1, X2)) -> cons1(X1, active(X2)) 39.51/11.51 active(s1(X)) -> s1(active(X)) 39.51/11.51 active(unquote(X)) -> unquote(active(X)) 39.51/11.51 active(unquote1(X)) -> unquote1(active(X)) 39.51/11.51 active(fcons(X1, X2)) -> fcons(active(X1), X2) 39.51/11.51 active(fcons(X1, X2)) -> fcons(X1, active(X2)) 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 39.51/11.51 proper(s(X)) -> s(proper(X)) 39.51/11.51 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(from(X)) -> from(proper(X)) 39.51/11.51 proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) 39.51/11.51 proper(quote(X)) -> quote(proper(X)) 39.51/11.51 proper(first1(X1, X2)) -> first1(proper(X1), proper(X2)) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2)) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 proper(quote1(X)) -> quote1(proper(X)) 39.51/11.51 proper(s1(X)) -> s1(proper(X)) 39.51/11.51 proper(unquote(X)) -> unquote(proper(X)) 39.51/11.51 proper(unquote1(X)) -> unquote1(proper(X)) 39.51/11.51 proper(fcons(X1, X2)) -> fcons(proper(X1), proper(X2)) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 39.51/11.51 The following defined symbols can occur below the 0th argument of top: proper, active 39.51/11.51 The following defined symbols can occur below the 0th argument of proper: proper, active 39.51/11.51 The following defined symbols can occur below the 0th argument of active: proper, active 39.51/11.51 39.51/11.51 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 39.51/11.51 active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) 39.51/11.51 active(sel(0, cons(X, Z))) -> mark(X) 39.51/11.51 active(first(0, Z)) -> mark(nil) 39.51/11.51 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 39.51/11.51 active(from(X)) -> mark(cons(X, from(s(X)))) 39.51/11.51 active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(sel1(0, cons(X, Z))) -> mark(quote(X)) 39.51/11.51 active(first1(0, Z)) -> mark(nil1) 39.51/11.51 active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) 39.51/11.51 active(quote(0)) -> mark(01) 39.51/11.51 active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) 39.51/11.51 active(quote1(nil)) -> mark(nil1) 39.51/11.51 active(quote(s(X))) -> mark(s1(quote(X))) 39.51/11.51 active(quote(sel(X, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(quote1(first(X, Z))) -> mark(first1(X, Z)) 39.51/11.51 active(unquote(01)) -> mark(0) 39.51/11.51 active(unquote(s1(X))) -> mark(s(unquote(X))) 39.51/11.51 active(unquote1(nil1)) -> mark(nil) 39.51/11.51 active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) 39.51/11.51 active(fcons(X, Z)) -> mark(cons(X, Z)) 39.51/11.51 active(sel(X1, X2)) -> sel(active(X1), X2) 39.51/11.51 active(sel(X1, X2)) -> sel(X1, active(X2)) 39.51/11.51 active(s(X)) -> s(active(X)) 39.51/11.51 active(cons(X1, X2)) -> cons(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(X1, active(X2)) 39.51/11.51 active(from(X)) -> from(active(X)) 39.51/11.51 active(sel1(X1, X2)) -> sel1(active(X1), X2) 39.51/11.51 active(sel1(X1, X2)) -> sel1(X1, active(X2)) 39.51/11.51 active(first1(X1, X2)) -> first1(active(X1), X2) 39.51/11.51 active(first1(X1, X2)) -> first1(X1, active(X2)) 39.51/11.51 active(cons1(X1, X2)) -> cons1(active(X1), X2) 39.51/11.51 active(cons1(X1, X2)) -> cons1(X1, active(X2)) 39.51/11.51 active(s1(X)) -> s1(active(X)) 39.51/11.51 active(unquote(X)) -> unquote(active(X)) 39.51/11.51 active(unquote1(X)) -> unquote1(active(X)) 39.51/11.51 active(fcons(X1, X2)) -> fcons(active(X1), X2) 39.51/11.51 active(fcons(X1, X2)) -> fcons(X1, active(X2)) 39.51/11.51 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 39.51/11.51 proper(s(X)) -> s(proper(X)) 39.51/11.51 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 39.51/11.51 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 39.51/11.51 proper(from(X)) -> from(proper(X)) 39.51/11.51 proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) 39.51/11.51 proper(quote(X)) -> quote(proper(X)) 39.51/11.51 proper(first1(X1, X2)) -> first1(proper(X1), proper(X2)) 39.51/11.51 proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2)) 39.51/11.51 proper(quote1(X)) -> quote1(proper(X)) 39.51/11.51 proper(s1(X)) -> s1(proper(X)) 39.51/11.51 proper(unquote(X)) -> unquote(proper(X)) 39.51/11.51 proper(unquote1(X)) -> unquote1(proper(X)) 39.51/11.51 proper(fcons(X1, X2)) -> fcons(proper(X1), proper(X2)) 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (2) 39.51/11.51 Obligation: 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 39.51/11.51 transformed relative TRS to TRS 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (4) 39.51/11.51 Obligation: 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (5) CpxTrsMatchBoundsTAProof (FINISHED) 39.51/11.51 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 39.51/11.51 39.51/11.51 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 39.51/11.51 final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 39.51/11.51 transitions: 39.51/11.51 mark0(0) -> 0 39.51/11.51 00() -> 0 39.51/11.51 ok0(0) -> 0 39.51/11.51 nil0() -> 0 39.51/11.51 nil10() -> 0 39.51/11.51 010() -> 0 39.51/11.51 active0(0) -> 0 39.51/11.51 sel0(0, 0) -> 1 39.51/11.51 s0(0) -> 2 39.51/11.51 cons0(0, 0) -> 3 39.51/11.51 first0(0, 0) -> 4 39.51/11.51 from0(0) -> 5 39.51/11.51 sel10(0, 0) -> 6 39.51/11.51 first10(0, 0) -> 7 39.51/11.51 cons10(0, 0) -> 8 39.51/11.51 s10(0) -> 9 39.51/11.51 unquote0(0) -> 10 39.51/11.51 unquote10(0) -> 11 39.51/11.51 fcons0(0, 0) -> 12 39.51/11.51 proper0(0) -> 13 39.51/11.51 quote0(0) -> 14 39.51/11.51 quote10(0) -> 15 39.51/11.51 top0(0) -> 16 39.51/11.51 sel1(0, 0) -> 17 39.51/11.51 mark1(17) -> 1 39.51/11.51 s1(0) -> 18 39.51/11.51 mark1(18) -> 2 39.51/11.51 cons1(0, 0) -> 19 39.51/11.51 mark1(19) -> 3 39.51/11.51 first1(0, 0) -> 20 39.51/11.51 mark1(20) -> 4 39.51/11.51 from1(0) -> 21 39.51/11.51 mark1(21) -> 5 39.51/11.51 sel11(0, 0) -> 22 39.51/11.51 mark1(22) -> 6 39.51/11.51 first11(0, 0) -> 23 39.51/11.51 mark1(23) -> 7 39.51/11.51 cons11(0, 0) -> 24 39.51/11.51 mark1(24) -> 8 39.51/11.51 s11(0) -> 25 39.51/11.51 mark1(25) -> 9 39.51/11.51 unquote1(0) -> 26 39.51/11.51 mark1(26) -> 10 39.51/11.51 unquote11(0) -> 27 39.51/11.51 mark1(27) -> 11 39.51/11.51 fcons1(0, 0) -> 28 39.51/11.51 mark1(28) -> 12 39.51/11.51 01() -> 29 39.51/11.51 ok1(29) -> 13 39.51/11.51 nil1() -> 30 39.51/11.51 ok1(30) -> 13 39.51/11.51 nil11() -> 31 39.51/11.51 ok1(31) -> 13 39.51/11.51 011() -> 32 39.51/11.51 ok1(32) -> 13 39.51/11.51 sel1(0, 0) -> 33 39.51/11.51 ok1(33) -> 1 39.51/11.51 s1(0) -> 34 39.51/11.51 ok1(34) -> 2 39.51/11.51 cons1(0, 0) -> 35 39.51/11.51 ok1(35) -> 3 39.51/11.51 first1(0, 0) -> 36 39.51/11.51 ok1(36) -> 4 39.51/11.51 from1(0) -> 37 39.51/11.51 ok1(37) -> 5 39.51/11.51 sel11(0, 0) -> 38 39.51/11.51 ok1(38) -> 6 39.51/11.51 quote1(0) -> 39 39.51/11.51 ok1(39) -> 14 39.51/11.51 first11(0, 0) -> 40 39.51/11.51 ok1(40) -> 7 39.51/11.51 cons11(0, 0) -> 41 39.51/11.51 ok1(41) -> 8 39.51/11.51 quote11(0) -> 42 39.51/11.51 ok1(42) -> 15 39.51/11.51 s11(0) -> 43 39.51/11.51 ok1(43) -> 9 39.51/11.51 unquote1(0) -> 44 39.51/11.51 ok1(44) -> 10 39.51/11.51 unquote11(0) -> 45 39.51/11.51 ok1(45) -> 11 39.51/11.51 fcons1(0, 0) -> 46 39.51/11.51 ok1(46) -> 12 39.51/11.51 proper1(0) -> 47 39.51/11.51 top1(47) -> 16 39.51/11.51 active1(0) -> 48 39.51/11.51 top1(48) -> 16 39.51/11.51 mark1(17) -> 17 39.51/11.51 mark1(17) -> 33 39.51/11.51 mark1(18) -> 18 39.51/11.51 mark1(18) -> 34 39.51/11.51 mark1(19) -> 19 39.51/11.51 mark1(19) -> 35 39.51/11.51 mark1(20) -> 20 39.51/11.51 mark1(20) -> 36 39.51/11.51 mark1(21) -> 21 39.51/11.51 mark1(21) -> 37 39.51/11.51 mark1(22) -> 22 39.51/11.51 mark1(22) -> 38 39.51/11.51 mark1(23) -> 23 39.51/11.51 mark1(23) -> 40 39.51/11.51 mark1(24) -> 24 39.51/11.51 mark1(24) -> 41 39.51/11.51 mark1(25) -> 25 39.51/11.51 mark1(25) -> 43 39.51/11.51 mark1(26) -> 26 39.51/11.51 mark1(26) -> 44 39.51/11.51 mark1(27) -> 27 39.51/11.51 mark1(27) -> 45 39.51/11.51 mark1(28) -> 28 39.51/11.51 mark1(28) -> 46 39.51/11.51 ok1(29) -> 47 39.51/11.51 ok1(30) -> 47 39.51/11.51 ok1(31) -> 47 39.51/11.51 ok1(32) -> 47 39.51/11.51 ok1(33) -> 17 39.51/11.51 ok1(33) -> 33 39.51/11.51 ok1(34) -> 18 39.51/11.51 ok1(34) -> 34 39.51/11.51 ok1(35) -> 19 39.51/11.51 ok1(35) -> 35 39.51/11.51 ok1(36) -> 20 39.51/11.51 ok1(36) -> 36 39.51/11.51 ok1(37) -> 21 39.51/11.51 ok1(37) -> 37 39.51/11.51 ok1(38) -> 22 39.51/11.51 ok1(38) -> 38 39.51/11.51 ok1(39) -> 39 39.51/11.51 ok1(40) -> 23 39.51/11.51 ok1(40) -> 40 39.51/11.51 ok1(41) -> 24 39.51/11.51 ok1(41) -> 41 39.51/11.51 ok1(42) -> 42 39.51/11.51 ok1(43) -> 25 39.51/11.51 ok1(43) -> 43 39.51/11.51 ok1(44) -> 26 39.51/11.51 ok1(44) -> 44 39.51/11.51 ok1(45) -> 27 39.51/11.51 ok1(45) -> 45 39.51/11.51 ok1(46) -> 28 39.51/11.51 ok1(46) -> 46 39.51/11.51 active2(29) -> 49 39.51/11.51 top2(49) -> 16 39.51/11.51 active2(30) -> 49 39.51/11.51 active2(31) -> 49 39.51/11.51 active2(32) -> 49 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (6) 39.51/11.51 BOUNDS(1, n^1) 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 39.51/11.51 Transformed a relative TRS into a decreasing-loop problem. 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (8) 39.51/11.51 Obligation: 39.51/11.51 Analyzing the following TRS for decreasing loops: 39.51/11.51 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) 39.51/11.51 active(sel(0, cons(X, Z))) -> mark(X) 39.51/11.51 active(first(0, Z)) -> mark(nil) 39.51/11.51 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 39.51/11.51 active(from(X)) -> mark(cons(X, from(s(X)))) 39.51/11.51 active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(sel1(0, cons(X, Z))) -> mark(quote(X)) 39.51/11.51 active(first1(0, Z)) -> mark(nil1) 39.51/11.51 active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) 39.51/11.51 active(quote(0)) -> mark(01) 39.51/11.51 active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) 39.51/11.51 active(quote1(nil)) -> mark(nil1) 39.51/11.51 active(quote(s(X))) -> mark(s1(quote(X))) 39.51/11.51 active(quote(sel(X, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(quote1(first(X, Z))) -> mark(first1(X, Z)) 39.51/11.51 active(unquote(01)) -> mark(0) 39.51/11.51 active(unquote(s1(X))) -> mark(s(unquote(X))) 39.51/11.51 active(unquote1(nil1)) -> mark(nil) 39.51/11.51 active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) 39.51/11.51 active(fcons(X, Z)) -> mark(cons(X, Z)) 39.51/11.51 active(sel(X1, X2)) -> sel(active(X1), X2) 39.51/11.51 active(sel(X1, X2)) -> sel(X1, active(X2)) 39.51/11.51 active(s(X)) -> s(active(X)) 39.51/11.51 active(cons(X1, X2)) -> cons(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(X1, active(X2)) 39.51/11.51 active(from(X)) -> from(active(X)) 39.51/11.51 active(sel1(X1, X2)) -> sel1(active(X1), X2) 39.51/11.51 active(sel1(X1, X2)) -> sel1(X1, active(X2)) 39.51/11.51 active(first1(X1, X2)) -> first1(active(X1), X2) 39.51/11.51 active(first1(X1, X2)) -> first1(X1, active(X2)) 39.51/11.51 active(cons1(X1, X2)) -> cons1(active(X1), X2) 39.51/11.51 active(cons1(X1, X2)) -> cons1(X1, active(X2)) 39.51/11.51 active(s1(X)) -> s1(active(X)) 39.51/11.51 active(unquote(X)) -> unquote(active(X)) 39.51/11.51 active(unquote1(X)) -> unquote1(active(X)) 39.51/11.51 active(fcons(X1, X2)) -> fcons(active(X1), X2) 39.51/11.51 active(fcons(X1, X2)) -> fcons(X1, active(X2)) 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 39.51/11.51 proper(s(X)) -> s(proper(X)) 39.51/11.51 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(from(X)) -> from(proper(X)) 39.51/11.51 proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) 39.51/11.51 proper(quote(X)) -> quote(proper(X)) 39.51/11.51 proper(first1(X1, X2)) -> first1(proper(X1), proper(X2)) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2)) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 proper(quote1(X)) -> quote1(proper(X)) 39.51/11.51 proper(s1(X)) -> s1(proper(X)) 39.51/11.51 proper(unquote(X)) -> unquote(proper(X)) 39.51/11.51 proper(unquote1(X)) -> unquote1(proper(X)) 39.51/11.51 proper(fcons(X1, X2)) -> fcons(proper(X1), proper(X2)) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (9) DecreasingLoopProof (LOWER BOUND(ID)) 39.51/11.51 The following loop(s) give(s) rise to the lower bound Omega(n^1): 39.51/11.51 39.51/11.51 The rewrite sequence 39.51/11.51 39.51/11.51 first1(mark(X1), X2) ->^+ mark(first1(X1, X2)) 39.51/11.51 39.51/11.51 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 39.51/11.51 39.51/11.51 The pumping substitution is [X1 / mark(X1)]. 39.51/11.51 39.51/11.51 The result substitution is [ ]. 39.51/11.51 39.51/11.51 39.51/11.51 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (10) 39.51/11.51 Complex Obligation (BEST) 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (11) 39.51/11.51 Obligation: 39.51/11.51 Proved the lower bound n^1 for the following obligation: 39.51/11.51 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) 39.51/11.51 active(sel(0, cons(X, Z))) -> mark(X) 39.51/11.51 active(first(0, Z)) -> mark(nil) 39.51/11.51 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 39.51/11.51 active(from(X)) -> mark(cons(X, from(s(X)))) 39.51/11.51 active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(sel1(0, cons(X, Z))) -> mark(quote(X)) 39.51/11.51 active(first1(0, Z)) -> mark(nil1) 39.51/11.51 active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) 39.51/11.51 active(quote(0)) -> mark(01) 39.51/11.51 active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) 39.51/11.51 active(quote1(nil)) -> mark(nil1) 39.51/11.51 active(quote(s(X))) -> mark(s1(quote(X))) 39.51/11.51 active(quote(sel(X, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(quote1(first(X, Z))) -> mark(first1(X, Z)) 39.51/11.51 active(unquote(01)) -> mark(0) 39.51/11.51 active(unquote(s1(X))) -> mark(s(unquote(X))) 39.51/11.51 active(unquote1(nil1)) -> mark(nil) 39.51/11.51 active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) 39.51/11.51 active(fcons(X, Z)) -> mark(cons(X, Z)) 39.51/11.51 active(sel(X1, X2)) -> sel(active(X1), X2) 39.51/11.51 active(sel(X1, X2)) -> sel(X1, active(X2)) 39.51/11.51 active(s(X)) -> s(active(X)) 39.51/11.51 active(cons(X1, X2)) -> cons(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(X1, active(X2)) 39.51/11.51 active(from(X)) -> from(active(X)) 39.51/11.51 active(sel1(X1, X2)) -> sel1(active(X1), X2) 39.51/11.51 active(sel1(X1, X2)) -> sel1(X1, active(X2)) 39.51/11.51 active(first1(X1, X2)) -> first1(active(X1), X2) 39.51/11.51 active(first1(X1, X2)) -> first1(X1, active(X2)) 39.51/11.51 active(cons1(X1, X2)) -> cons1(active(X1), X2) 39.51/11.51 active(cons1(X1, X2)) -> cons1(X1, active(X2)) 39.51/11.51 active(s1(X)) -> s1(active(X)) 39.51/11.51 active(unquote(X)) -> unquote(active(X)) 39.51/11.51 active(unquote1(X)) -> unquote1(active(X)) 39.51/11.51 active(fcons(X1, X2)) -> fcons(active(X1), X2) 39.51/11.51 active(fcons(X1, X2)) -> fcons(X1, active(X2)) 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 39.51/11.51 proper(s(X)) -> s(proper(X)) 39.51/11.51 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(from(X)) -> from(proper(X)) 39.51/11.51 proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) 39.51/11.51 proper(quote(X)) -> quote(proper(X)) 39.51/11.51 proper(first1(X1, X2)) -> first1(proper(X1), proper(X2)) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2)) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 proper(quote1(X)) -> quote1(proper(X)) 39.51/11.51 proper(s1(X)) -> s1(proper(X)) 39.51/11.51 proper(unquote(X)) -> unquote(proper(X)) 39.51/11.51 proper(unquote1(X)) -> unquote1(proper(X)) 39.51/11.51 proper(fcons(X1, X2)) -> fcons(proper(X1), proper(X2)) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (12) LowerBoundPropagationProof (FINISHED) 39.51/11.51 Propagated lower bound. 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (13) 39.51/11.51 BOUNDS(n^1, INF) 39.51/11.51 39.51/11.51 ---------------------------------------- 39.51/11.51 39.51/11.51 (14) 39.51/11.51 Obligation: 39.51/11.51 Analyzing the following TRS for decreasing loops: 39.51/11.51 39.51/11.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.51/11.51 39.51/11.51 39.51/11.51 The TRS R consists of the following rules: 39.51/11.51 39.51/11.51 active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) 39.51/11.51 active(sel(0, cons(X, Z))) -> mark(X) 39.51/11.51 active(first(0, Z)) -> mark(nil) 39.51/11.51 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 39.51/11.51 active(from(X)) -> mark(cons(X, from(s(X)))) 39.51/11.51 active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(sel1(0, cons(X, Z))) -> mark(quote(X)) 39.51/11.51 active(first1(0, Z)) -> mark(nil1) 39.51/11.51 active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) 39.51/11.51 active(quote(0)) -> mark(01) 39.51/11.51 active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) 39.51/11.51 active(quote1(nil)) -> mark(nil1) 39.51/11.51 active(quote(s(X))) -> mark(s1(quote(X))) 39.51/11.51 active(quote(sel(X, Z))) -> mark(sel1(X, Z)) 39.51/11.51 active(quote1(first(X, Z))) -> mark(first1(X, Z)) 39.51/11.51 active(unquote(01)) -> mark(0) 39.51/11.51 active(unquote(s1(X))) -> mark(s(unquote(X))) 39.51/11.51 active(unquote1(nil1)) -> mark(nil) 39.51/11.51 active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) 39.51/11.51 active(fcons(X, Z)) -> mark(cons(X, Z)) 39.51/11.51 active(sel(X1, X2)) -> sel(active(X1), X2) 39.51/11.51 active(sel(X1, X2)) -> sel(X1, active(X2)) 39.51/11.51 active(s(X)) -> s(active(X)) 39.51/11.51 active(cons(X1, X2)) -> cons(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(active(X1), X2) 39.51/11.51 active(first(X1, X2)) -> first(X1, active(X2)) 39.51/11.51 active(from(X)) -> from(active(X)) 39.51/11.51 active(sel1(X1, X2)) -> sel1(active(X1), X2) 39.51/11.51 active(sel1(X1, X2)) -> sel1(X1, active(X2)) 39.51/11.51 active(first1(X1, X2)) -> first1(active(X1), X2) 39.51/11.51 active(first1(X1, X2)) -> first1(X1, active(X2)) 39.51/11.51 active(cons1(X1, X2)) -> cons1(active(X1), X2) 39.51/11.51 active(cons1(X1, X2)) -> cons1(X1, active(X2)) 39.51/11.51 active(s1(X)) -> s1(active(X)) 39.51/11.51 active(unquote(X)) -> unquote(active(X)) 39.51/11.51 active(unquote1(X)) -> unquote1(active(X)) 39.51/11.51 active(fcons(X1, X2)) -> fcons(active(X1), X2) 39.51/11.51 active(fcons(X1, X2)) -> fcons(X1, active(X2)) 39.51/11.51 sel(mark(X1), X2) -> mark(sel(X1, X2)) 39.51/11.51 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 39.51/11.51 s(mark(X)) -> mark(s(X)) 39.51/11.51 cons(mark(X1), X2) -> mark(cons(X1, X2)) 39.51/11.51 first(mark(X1), X2) -> mark(first(X1, X2)) 39.51/11.51 first(X1, mark(X2)) -> mark(first(X1, X2)) 39.51/11.51 from(mark(X)) -> mark(from(X)) 39.51/11.51 sel1(mark(X1), X2) -> mark(sel1(X1, X2)) 39.51/11.51 sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) 39.51/11.51 first1(mark(X1), X2) -> mark(first1(X1, X2)) 39.51/11.51 first1(X1, mark(X2)) -> mark(first1(X1, X2)) 39.51/11.51 cons1(mark(X1), X2) -> mark(cons1(X1, X2)) 39.51/11.51 cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) 39.51/11.51 s1(mark(X)) -> mark(s1(X)) 39.51/11.51 unquote(mark(X)) -> mark(unquote(X)) 39.51/11.51 unquote1(mark(X)) -> mark(unquote1(X)) 39.51/11.51 fcons(mark(X1), X2) -> mark(fcons(X1, X2)) 39.51/11.51 fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) 39.51/11.51 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 39.51/11.51 proper(s(X)) -> s(proper(X)) 39.51/11.51 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 39.51/11.51 proper(0) -> ok(0) 39.51/11.51 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 39.51/11.51 proper(nil) -> ok(nil) 39.51/11.51 proper(from(X)) -> from(proper(X)) 39.51/11.51 proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) 39.51/11.51 proper(quote(X)) -> quote(proper(X)) 39.51/11.51 proper(first1(X1, X2)) -> first1(proper(X1), proper(X2)) 39.51/11.51 proper(nil1) -> ok(nil1) 39.51/11.51 proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2)) 39.51/11.51 proper(01) -> ok(01) 39.51/11.51 proper(quote1(X)) -> quote1(proper(X)) 39.51/11.51 proper(s1(X)) -> s1(proper(X)) 39.51/11.51 proper(unquote(X)) -> unquote(proper(X)) 39.51/11.51 proper(unquote1(X)) -> unquote1(proper(X)) 39.51/11.51 proper(fcons(X1, X2)) -> fcons(proper(X1), proper(X2)) 39.51/11.51 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 39.51/11.51 s(ok(X)) -> ok(s(X)) 39.51/11.51 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 39.51/11.51 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 39.51/11.51 from(ok(X)) -> ok(from(X)) 39.51/11.51 sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) 39.51/11.51 quote(ok(X)) -> ok(quote(X)) 39.51/11.51 first1(ok(X1), ok(X2)) -> ok(first1(X1, X2)) 39.51/11.51 cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2)) 39.51/11.51 quote1(ok(X)) -> ok(quote1(X)) 39.51/11.51 s1(ok(X)) -> ok(s1(X)) 39.51/11.51 unquote(ok(X)) -> ok(unquote(X)) 39.51/11.51 unquote1(ok(X)) -> ok(unquote1(X)) 39.51/11.51 fcons(ok(X1), ok(X2)) -> ok(fcons(X1, X2)) 39.51/11.51 top(mark(X)) -> top(proper(X)) 39.51/11.51 top(ok(X)) -> top(active(X)) 39.51/11.51 39.51/11.51 S is empty. 39.51/11.51 Rewrite Strategy: FULL 39.51/11.54 EOF