YES(?,O(n^1)) 0.16/0.22 YES(?,O(n^1)) 0.16/0.22 0.16/0.22 Problem: 0.16/0.22 ++(nil(),y) -> y 0.16/0.22 ++(x,nil()) -> x 0.16/0.22 ++(.(x,y),z) -> .(x,++(y,z)) 0.16/0.22 ++(++(x,y),z) -> ++(x,++(y,z)) 0.16/0.22 0.16/0.22 Proof: 0.16/0.22 Bounds Processor: 0.16/0.22 bound: 1 0.16/0.22 enrichment: match 0.16/0.22 automaton: 0.16/0.22 final states: {3} 0.16/0.22 transitions: 0.16/0.22 .1(1,4) -> 4,3 0.16/0.22 .1(2,7) -> 4,3 0.16/0.22 .1(1,7) -> 4,3 0.16/0.22 .1(2,4) -> 4,3 0.16/0.22 ++1(1,2) -> 7* 0.16/0.22 ++1(2,1) -> 4* 0.16/0.22 ++1(1,1) -> 4* 0.16/0.22 ++1(2,2) -> 4* 0.16/0.22 ++0(1,2) -> 3* 0.16/0.22 ++0(2,1) -> 3* 0.16/0.22 ++0(1,1) -> 3* 0.16/0.22 ++0(2,2) -> 3* 0.16/0.22 nil0() -> 1* 0.16/0.22 .0(1,2) -> 2* 0.16/0.22 .0(2,1) -> 2* 0.16/0.22 .0(1,1) -> 2* 0.16/0.22 .0(2,2) -> 2* 0.16/0.22 1 -> 4,3 0.16/0.22 2 -> 4,7,3 0.16/0.22 problem: 0.16/0.22 0.16/0.22 Qed 0.16/0.22 EOF