YES(?,O(n^1))
889.84/297.11	YES(?,O(n^1))
889.84/297.11	
889.84/297.11	We are left with following problem, upon which TcT provides the
889.84/297.11	certificate YES(?,O(n^1)).
889.84/297.11	
889.84/297.11	Strict Trs:
889.84/297.11	  { active(zeros()) -> mark(cons(0(), zeros()))
889.84/297.11	  , active(cons(X1, X2)) -> cons(active(X1), X2)
889.84/297.11	  , active(U11(X1, X2)) -> U11(active(X1), X2)
889.84/297.11	  , active(U11(tt(), L)) -> mark(U12(tt(), L))
889.84/297.11	  , active(U12(X1, X2)) -> U12(active(X1), X2)
889.84/297.11	  , active(U12(tt(), L)) -> mark(s(length(L)))
889.84/297.11	  , active(s(X)) -> s(active(X))
889.84/297.11	  , active(length(X)) -> length(active(X))
889.84/297.11	  , active(length(cons(N, L))) -> mark(U11(tt(), L))
889.84/297.11	  , active(length(nil())) -> mark(0())
889.84/297.11	  , cons(mark(X1), X2) -> mark(cons(X1, X2))
889.84/297.11	  , cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
889.84/297.11	  , U11(mark(X1), X2) -> mark(U11(X1, X2))
889.84/297.11	  , U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
889.84/297.11	  , U12(mark(X1), X2) -> mark(U12(X1, X2))
889.84/297.11	  , U12(ok(X1), ok(X2)) -> ok(U12(X1, X2))
889.84/297.11	  , s(mark(X)) -> mark(s(X))
889.84/297.11	  , s(ok(X)) -> ok(s(X))
889.84/297.11	  , length(mark(X)) -> mark(length(X))
889.84/297.11	  , length(ok(X)) -> ok(length(X))
889.84/297.11	  , proper(zeros()) -> ok(zeros())
889.84/297.11	  , proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
889.84/297.11	  , proper(0()) -> ok(0())
889.84/297.11	  , proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
889.84/297.11	  , proper(tt()) -> ok(tt())
889.84/297.11	  , proper(U12(X1, X2)) -> U12(proper(X1), proper(X2))
889.84/297.11	  , proper(s(X)) -> s(proper(X))
889.84/297.11	  , proper(length(X)) -> length(proper(X))
889.84/297.11	  , proper(nil()) -> ok(nil())
889.84/297.11	  , top(mark(X)) -> top(proper(X))
889.84/297.11	  , top(ok(X)) -> top(active(X)) }
889.84/297.11	Obligation:
889.84/297.11	  innermost runtime complexity
889.84/297.11	Answer:
889.84/297.11	  YES(?,O(n^1))
889.84/297.11	
889.84/297.11	The problem is match-bounded by 5. The enriched problem is
889.84/297.11	compatible with the following automaton.
889.84/297.11	{ active_0(2) -> 1
889.84/297.11	, active_0(3) -> 1
889.84/297.11	, active_0(5) -> 1
889.84/297.11	, active_0(7) -> 1
889.84/297.11	, active_0(11) -> 1
889.84/297.11	, active_0(13) -> 1
889.84/297.11	, active_1(2) -> 23
889.84/297.11	, active_1(3) -> 23
889.84/297.11	, active_1(5) -> 23
889.84/297.11	, active_1(7) -> 23
889.84/297.11	, active_1(11) -> 23
889.84/297.11	, active_1(13) -> 23
889.84/297.11	, active_2(16) -> 24
889.84/297.11	, active_2(17) -> 24
889.84/297.11	, active_3(34) -> 30
889.84/297.11	, active_4(26) -> 36
889.84/297.11	, active_4(37) -> 38
889.84/297.11	, active_5(33) -> 39
889.84/297.11	, zeros_0() -> 2
889.84/297.11	, zeros_1() -> 17
889.84/297.11	, zeros_2() -> 27
889.84/297.11	, zeros_3() -> 35
889.84/297.11	, mark_0(2) -> 3
889.84/297.11	, mark_0(3) -> 3
889.84/297.11	, mark_0(5) -> 3
889.84/297.11	, mark_0(7) -> 3
889.84/297.11	, mark_0(11) -> 3
889.84/297.11	, mark_0(13) -> 3
889.84/297.11	, mark_1(15) -> 1
889.84/297.11	, mark_1(15) -> 23
889.84/297.11	, mark_1(18) -> 4
889.84/297.11	, mark_1(18) -> 18
889.84/297.11	, mark_1(19) -> 6
889.84/297.11	, mark_1(19) -> 19
889.84/297.11	, mark_1(20) -> 8
889.84/297.11	, mark_1(20) -> 20
889.84/297.11	, mark_1(21) -> 9
889.84/297.11	, mark_1(21) -> 21
889.84/297.11	, mark_1(22) -> 10
889.84/297.11	, mark_1(22) -> 22
889.84/297.11	, mark_2(25) -> 24
889.84/297.11	, cons_0(2, 2) -> 4
889.84/297.11	, cons_0(2, 3) -> 4
889.84/297.11	, cons_0(2, 5) -> 4
889.84/297.11	, cons_0(2, 7) -> 4
889.84/297.11	, cons_0(2, 11) -> 4
889.84/297.11	, cons_0(2, 13) -> 4
889.84/297.11	, cons_0(3, 2) -> 4
889.84/297.11	, cons_0(3, 3) -> 4
889.84/297.11	, cons_0(3, 5) -> 4
889.84/297.11	, cons_0(3, 7) -> 4
889.84/297.11	, cons_0(3, 11) -> 4
889.84/297.11	, cons_0(3, 13) -> 4
889.84/297.11	, cons_0(5, 2) -> 4
889.84/297.11	, cons_0(5, 3) -> 4
889.84/297.11	, cons_0(5, 5) -> 4
889.84/297.11	, cons_0(5, 7) -> 4
889.84/297.11	, cons_0(5, 11) -> 4
889.84/297.11	, cons_0(5, 13) -> 4
889.84/297.11	, cons_0(7, 2) -> 4
889.84/297.11	, cons_0(7, 3) -> 4
889.84/297.11	, cons_0(7, 5) -> 4
889.84/297.11	, cons_0(7, 7) -> 4
889.84/297.11	, cons_0(7, 11) -> 4
889.84/297.11	, cons_0(7, 13) -> 4
889.84/297.11	, cons_0(11, 2) -> 4
889.84/297.11	, cons_0(11, 3) -> 4
889.84/297.11	, cons_0(11, 5) -> 4
889.84/297.11	, cons_0(11, 7) -> 4
889.84/297.11	, cons_0(11, 11) -> 4
889.84/297.11	, cons_0(11, 13) -> 4
889.84/297.11	, cons_0(13, 2) -> 4
889.84/297.11	, cons_0(13, 3) -> 4
889.84/297.11	, cons_0(13, 5) -> 4
889.84/297.11	, cons_0(13, 7) -> 4
889.84/297.11	, cons_0(13, 11) -> 4
889.84/297.11	, cons_0(13, 13) -> 4
889.84/297.11	, cons_1(2, 2) -> 18
889.84/297.11	, cons_1(2, 3) -> 18
889.84/297.11	, cons_1(2, 5) -> 18
889.84/297.11	, cons_1(2, 7) -> 18
889.84/297.11	, cons_1(2, 11) -> 18
889.84/297.11	, cons_1(2, 13) -> 18
889.84/297.11	, cons_1(3, 2) -> 18
889.84/297.11	, cons_1(3, 3) -> 18
889.84/297.11	, cons_1(3, 5) -> 18
889.84/297.11	, cons_1(3, 7) -> 18
889.84/297.11	, cons_1(3, 11) -> 18
889.84/297.11	, cons_1(3, 13) -> 18
889.84/297.11	, cons_1(5, 2) -> 18
889.84/297.11	, cons_1(5, 3) -> 18
889.84/297.11	, cons_1(5, 5) -> 18
889.84/297.11	, cons_1(5, 7) -> 18
889.84/297.11	, cons_1(5, 11) -> 18
889.84/297.11	, cons_1(5, 13) -> 18
889.84/297.11	, cons_1(7, 2) -> 18
889.84/297.11	, cons_1(7, 3) -> 18
889.84/297.11	, cons_1(7, 5) -> 18
889.84/297.11	, cons_1(7, 7) -> 18
889.84/297.11	, cons_1(7, 11) -> 18
889.84/297.11	, cons_1(7, 13) -> 18
889.84/297.11	, cons_1(11, 2) -> 18
889.84/297.11	, cons_1(11, 3) -> 18
889.84/297.11	, cons_1(11, 5) -> 18
889.84/297.11	, cons_1(11, 7) -> 18
889.84/297.11	, cons_1(11, 11) -> 18
889.84/297.11	, cons_1(11, 13) -> 18
889.84/297.11	, cons_1(13, 2) -> 18
889.84/297.11	, cons_1(13, 3) -> 18
889.84/297.11	, cons_1(13, 5) -> 18
889.84/297.11	, cons_1(13, 7) -> 18
889.84/297.11	, cons_1(13, 11) -> 18
889.84/297.11	, cons_1(13, 13) -> 18
889.84/297.11	, cons_1(16, 17) -> 15
889.84/297.11	, cons_2(26, 27) -> 25
889.84/297.11	, cons_2(28, 29) -> 24
889.84/297.11	, cons_3(26, 27) -> 34
889.84/297.11	, cons_3(31, 32) -> 30
889.84/297.11	, cons_4(33, 35) -> 37
889.84/297.11	, cons_4(36, 27) -> 30
889.84/297.11	, cons_5(39, 35) -> 38
889.84/297.11	, 0_0() -> 5
889.84/297.11	, 0_1() -> 16
889.84/297.11	, 0_2() -> 26
889.84/297.11	, 0_3() -> 33
889.84/297.11	, U11_0(2, 2) -> 6
889.84/297.11	, U11_0(2, 3) -> 6
889.84/297.11	, U11_0(2, 5) -> 6
889.84/297.11	, U11_0(2, 7) -> 6
889.84/297.11	, U11_0(2, 11) -> 6
889.84/297.11	, U11_0(2, 13) -> 6
889.84/297.11	, U11_0(3, 2) -> 6
889.84/297.11	, U11_0(3, 3) -> 6
889.84/297.11	, U11_0(3, 5) -> 6
889.84/297.11	, U11_0(3, 7) -> 6
889.84/297.11	, U11_0(3, 11) -> 6
889.84/297.11	, U11_0(3, 13) -> 6
889.84/297.11	, U11_0(5, 2) -> 6
889.84/297.11	, U11_0(5, 3) -> 6
889.84/297.11	, U11_0(5, 5) -> 6
889.84/297.11	, U11_0(5, 7) -> 6
889.84/297.11	, U11_0(5, 11) -> 6
889.84/297.11	, U11_0(5, 13) -> 6
889.84/297.11	, U11_0(7, 2) -> 6
889.84/297.11	, U11_0(7, 3) -> 6
889.84/297.11	, U11_0(7, 5) -> 6
889.84/297.11	, U11_0(7, 7) -> 6
889.84/297.11	, U11_0(7, 11) -> 6
889.84/297.11	, U11_0(7, 13) -> 6
889.84/297.11	, U11_0(11, 2) -> 6
889.84/297.11	, U11_0(11, 3) -> 6
889.84/297.11	, U11_0(11, 5) -> 6
889.84/297.11	, U11_0(11, 7) -> 6
889.84/297.11	, U11_0(11, 11) -> 6
889.84/297.11	, U11_0(11, 13) -> 6
889.84/297.11	, U11_0(13, 2) -> 6
889.84/297.11	, U11_0(13, 3) -> 6
889.84/297.11	, U11_0(13, 5) -> 6
889.84/297.11	, U11_0(13, 7) -> 6
889.84/297.11	, U11_0(13, 11) -> 6
889.84/297.11	, U11_0(13, 13) -> 6
889.84/297.11	, U11_1(2, 2) -> 19
889.84/297.11	, U11_1(2, 3) -> 19
889.84/297.11	, U11_1(2, 5) -> 19
889.84/297.11	, U11_1(2, 7) -> 19
889.84/297.11	, U11_1(2, 11) -> 19
889.84/297.11	, U11_1(2, 13) -> 19
889.84/297.11	, U11_1(3, 2) -> 19
889.84/297.11	, U11_1(3, 3) -> 19
889.84/297.11	, U11_1(3, 5) -> 19
889.84/297.11	, U11_1(3, 7) -> 19
889.84/297.11	, U11_1(3, 11) -> 19
889.84/297.11	, U11_1(3, 13) -> 19
889.84/297.11	, U11_1(5, 2) -> 19
889.84/297.11	, U11_1(5, 3) -> 19
889.84/297.11	, U11_1(5, 5) -> 19
889.84/297.11	, U11_1(5, 7) -> 19
889.84/297.11	, U11_1(5, 11) -> 19
889.84/297.11	, U11_1(5, 13) -> 19
889.84/297.11	, U11_1(7, 2) -> 19
889.84/297.11	, U11_1(7, 3) -> 19
889.84/297.11	, U11_1(7, 5) -> 19
889.84/297.11	, U11_1(7, 7) -> 19
889.84/297.11	, U11_1(7, 11) -> 19
889.84/297.11	, U11_1(7, 13) -> 19
889.84/297.11	, U11_1(11, 2) -> 19
889.84/297.11	, U11_1(11, 3) -> 19
889.84/297.11	, U11_1(11, 5) -> 19
889.84/297.11	, U11_1(11, 7) -> 19
889.84/297.11	, U11_1(11, 11) -> 19
889.84/297.11	, U11_1(11, 13) -> 19
889.84/297.11	, U11_1(13, 2) -> 19
889.84/297.11	, U11_1(13, 3) -> 19
889.84/297.11	, U11_1(13, 5) -> 19
889.84/297.11	, U11_1(13, 7) -> 19
889.84/297.11	, U11_1(13, 11) -> 19
889.84/297.11	, U11_1(13, 13) -> 19
889.84/297.11	, tt_0() -> 7
889.84/297.11	, tt_1() -> 16
889.84/297.11	, tt_2() -> 26
889.84/297.11	, tt_3() -> 33
889.84/297.11	, U12_0(2, 2) -> 8
889.84/297.11	, U12_0(2, 3) -> 8
889.84/297.11	, U12_0(2, 5) -> 8
889.84/297.11	, U12_0(2, 7) -> 8
889.84/297.11	, U12_0(2, 11) -> 8
889.84/297.11	, U12_0(2, 13) -> 8
889.84/297.11	, U12_0(3, 2) -> 8
889.84/297.11	, U12_0(3, 3) -> 8
889.84/297.11	, U12_0(3, 5) -> 8
889.84/297.11	, U12_0(3, 7) -> 8
889.84/297.11	, U12_0(3, 11) -> 8
889.84/297.11	, U12_0(3, 13) -> 8
889.84/297.11	, U12_0(5, 2) -> 8
889.84/297.11	, U12_0(5, 3) -> 8
889.84/297.11	, U12_0(5, 5) -> 8
889.84/297.11	, U12_0(5, 7) -> 8
889.84/297.11	, U12_0(5, 11) -> 8
889.84/297.11	, U12_0(5, 13) -> 8
889.84/297.11	, U12_0(7, 2) -> 8
889.84/297.11	, U12_0(7, 3) -> 8
889.84/297.11	, U12_0(7, 5) -> 8
889.84/297.11	, U12_0(7, 7) -> 8
889.84/297.11	, U12_0(7, 11) -> 8
889.84/297.11	, U12_0(7, 13) -> 8
889.84/297.11	, U12_0(11, 2) -> 8
889.84/297.11	, U12_0(11, 3) -> 8
889.84/297.11	, U12_0(11, 5) -> 8
889.84/297.11	, U12_0(11, 7) -> 8
889.84/297.11	, U12_0(11, 11) -> 8
889.84/297.11	, U12_0(11, 13) -> 8
889.84/297.11	, U12_0(13, 2) -> 8
889.84/297.11	, U12_0(13, 3) -> 8
889.84/297.11	, U12_0(13, 5) -> 8
889.84/297.11	, U12_0(13, 7) -> 8
889.84/297.11	, U12_0(13, 11) -> 8
889.84/297.11	, U12_0(13, 13) -> 8
889.84/297.11	, U12_1(2, 2) -> 20
889.84/297.11	, U12_1(2, 3) -> 20
889.84/297.11	, U12_1(2, 5) -> 20
889.84/297.11	, U12_1(2, 7) -> 20
889.84/297.11	, U12_1(2, 11) -> 20
889.84/297.11	, U12_1(2, 13) -> 20
889.84/297.11	, U12_1(3, 2) -> 20
889.84/297.11	, U12_1(3, 3) -> 20
889.84/297.11	, U12_1(3, 5) -> 20
889.84/297.11	, U12_1(3, 7) -> 20
889.84/297.11	, U12_1(3, 11) -> 20
889.84/297.11	, U12_1(3, 13) -> 20
889.84/297.11	, U12_1(5, 2) -> 20
889.84/297.11	, U12_1(5, 3) -> 20
889.84/297.11	, U12_1(5, 5) -> 20
889.84/297.11	, U12_1(5, 7) -> 20
889.84/297.11	, U12_1(5, 11) -> 20
889.84/297.11	, U12_1(5, 13) -> 20
889.84/297.11	, U12_1(7, 2) -> 20
889.84/297.11	, U12_1(7, 3) -> 20
889.84/297.11	, U12_1(7, 5) -> 20
889.84/297.11	, U12_1(7, 7) -> 20
889.84/297.11	, U12_1(7, 11) -> 20
889.84/297.11	, U12_1(7, 13) -> 20
889.84/297.11	, U12_1(11, 2) -> 20
889.84/297.11	, U12_1(11, 3) -> 20
889.84/297.11	, U12_1(11, 5) -> 20
889.84/297.11	, U12_1(11, 7) -> 20
889.84/297.11	, U12_1(11, 11) -> 20
889.84/297.11	, U12_1(11, 13) -> 20
889.84/297.11	, U12_1(13, 2) -> 20
889.84/297.11	, U12_1(13, 3) -> 20
889.84/297.11	, U12_1(13, 5) -> 20
889.84/297.11	, U12_1(13, 7) -> 20
889.84/297.11	, U12_1(13, 11) -> 20
889.84/297.11	, U12_1(13, 13) -> 20
889.84/297.11	, s_0(2) -> 9
889.84/297.11	, s_0(3) -> 9
889.84/297.11	, s_0(5) -> 9
889.84/297.11	, s_0(7) -> 9
889.84/297.11	, s_0(11) -> 9
889.84/297.11	, s_0(13) -> 9
889.84/297.11	, s_1(2) -> 21
889.84/297.11	, s_1(3) -> 21
889.84/297.11	, s_1(5) -> 21
889.84/297.11	, s_1(7) -> 21
889.84/297.11	, s_1(11) -> 21
889.84/297.11	, s_1(13) -> 21
889.84/297.11	, length_0(2) -> 10
889.84/297.11	, length_0(3) -> 10
889.84/297.11	, length_0(5) -> 10
889.84/297.11	, length_0(7) -> 10
889.84/297.11	, length_0(11) -> 10
889.84/297.11	, length_0(13) -> 10
889.84/297.11	, length_1(2) -> 22
889.84/297.11	, length_1(3) -> 22
889.84/297.11	, length_1(5) -> 22
889.84/297.11	, length_1(7) -> 22
889.84/297.11	, length_1(11) -> 22
889.84/297.11	, length_1(13) -> 22
889.84/297.11	, nil_0() -> 11
889.84/297.11	, nil_1() -> 16
889.84/297.11	, nil_2() -> 26
889.84/297.11	, nil_3() -> 33
889.84/297.11	, proper_0(2) -> 12
889.84/297.11	, proper_0(3) -> 12
889.84/297.11	, proper_0(5) -> 12
889.84/297.11	, proper_0(7) -> 12
889.84/297.11	, proper_0(11) -> 12
889.84/297.11	, proper_0(13) -> 12
889.84/297.11	, proper_1(2) -> 23
889.84/297.11	, proper_1(3) -> 23
889.84/297.11	, proper_1(5) -> 23
889.84/297.11	, proper_1(7) -> 23
889.84/297.11	, proper_1(11) -> 23
889.84/297.11	, proper_1(13) -> 23
889.84/297.11	, proper_2(15) -> 24
889.84/297.11	, proper_2(16) -> 28
889.84/297.11	, proper_2(17) -> 29
889.84/297.11	, proper_3(25) -> 30
889.84/297.11	, proper_3(26) -> 31
889.84/297.11	, proper_3(27) -> 32
889.84/297.11	, ok_0(2) -> 13
889.84/297.11	, ok_0(3) -> 13
889.84/297.11	, ok_0(5) -> 13
889.84/297.11	, ok_0(7) -> 13
889.84/297.11	, ok_0(11) -> 13
889.84/297.11	, ok_0(13) -> 13
889.84/297.11	, ok_1(16) -> 12
889.84/297.11	, ok_1(16) -> 23
889.84/297.11	, ok_1(17) -> 12
889.84/297.11	, ok_1(17) -> 23
889.84/297.11	, ok_1(18) -> 4
889.84/297.11	, ok_1(18) -> 18
889.84/297.11	, ok_1(19) -> 6
889.84/297.11	, ok_1(19) -> 19
889.84/297.11	, ok_1(20) -> 8
889.84/297.11	, ok_1(20) -> 20
889.84/297.11	, ok_1(21) -> 9
889.84/297.11	, ok_1(21) -> 21
889.84/297.11	, ok_1(22) -> 10
889.84/297.11	, ok_1(22) -> 22
889.84/297.11	, ok_2(26) -> 28
889.84/297.11	, ok_2(27) -> 29
889.84/297.11	, ok_3(33) -> 31
889.84/297.11	, ok_3(34) -> 24
889.84/297.11	, ok_3(35) -> 32
889.84/297.11	, ok_4(37) -> 30
889.84/297.11	, top_0(2) -> 14
889.84/297.11	, top_0(3) -> 14
889.84/297.11	, top_0(5) -> 14
889.84/297.11	, top_0(7) -> 14
889.84/297.11	, top_0(11) -> 14
889.84/297.11	, top_0(13) -> 14
889.84/297.11	, top_1(23) -> 14
889.84/297.11	, top_2(24) -> 14
889.84/297.11	, top_3(30) -> 14
889.84/297.11	, top_4(38) -> 14 }
889.84/297.11	
889.84/297.11	Hurray, we answered YES(?,O(n^1))
889.84/297.18	EOF