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