/export/starexec/sandbox/solver/bin/starexec_run_tct_dci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE * Step 1: DecomposeCP. MAYBE + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),d,stop(),true(),b2,b3,i) -> idle(B(),open(),stop(),false(),b2,b3,i) busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),d,stop(),b1,b2,b3,i) -> incorrect() busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),d,stop(),b1,true(),b3,i) -> idle(F(),open(),stop(),b1,false(),b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),d,stop(),b1,b2,b3,i) -> incorrect() busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),d,stop(),b1,b2,true(),i) -> idle(S(),open(),stop(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) -> busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) or(false(),b) -> b or(true(),b) -> true() start(i) -> busy(F(),closed(),stop(),false(),false(),false(),i) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeComp, withCP_ = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly: busy(B(),d,stop(),true(),b2,b3,i) -> idle(B(),open(),stop(),false(),b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(BF(),d,stop(),b1,b2,b3,i) -> incorrect() busy(F(),d,stop(),b1,true(),b3,i) -> idle(F(),open(),stop(),b1,false(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(FS(),d,stop(),b1,b2,b3,i) -> incorrect() busy(S(),d,stop(),b1,b2,true(),i) -> idle(S(),open(),stop(),b1,b2,false(),i) busy(S(),closed(),stop(),false(),false(),false(),empty()) -> correct() idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) -> busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) start(i) -> busy(F(),closed(),stop(),false(),false(),false(),i) The Processor induces the complexity certificate TIME (?,O(n^1)) BEST_CASE TIME (?,?) SPACE(?,?) Observe that weak rules from Problem (R) are non-size-increasing. Once the complexity of (R) has been assessed, it suffices to consider only rules whose complexity has not been estimated in (R) resulting in the following Problem (S). Overall the certificate is obtained by composition. Problem (S) - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) or(false(),b) -> b or(true(),b) -> true() - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0 ,incorrect/0,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} ** Step 1.a:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),d,stop(),true(),b2,b3,i) -> idle(B(),open(),stop(),false(),b2,b3,i) busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),d,stop(),b1,b2,b3,i) -> incorrect() busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),d,stop(),b1,true(),b3,i) -> idle(F(),open(),stop(),b1,false(),b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),d,stop(),b1,b2,b3,i) -> incorrect() busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),d,stop(),b1,b2,true(),i) -> idle(S(),open(),stop(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) -> busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) or(false(),b) -> b or(true(),b) -> true() start(i) -> busy(F(),closed(),stop(),false(),false(),false(),i) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(B) = [4] p(BF) = [4] p(F) = [4] p(FS) = [4] p(S) = [4] p(busy) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(closed) = [0] p(correct) = [0] p(down) = [0] p(empty) = [0] p(false) = [0] p(idle) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(incorrect) = [0] p(newbuttons) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [2] p(open) = [0] p(or) = [1] x1 + [1] x2 + [0] p(start) = [1] x1 + [7] p(stop) = [0] p(true) = [4] p(up) = [0] Following rules are strictly oriented: busy(B(),d,stop(),true(),b2,b3,i) = [1] b2 + [1] b3 + [1] d + [1] i + [8] > [1] b2 + [1] b3 + [1] i + [4] = idle(B(),open(),stop(),false(),b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),empty()) = [4] > [0] = correct() busy(BF(),d,stop(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] i + [4] > [0] = incorrect() busy(F(),d,stop(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] d + [1] i + [8] > [1] b1 + [1] b3 + [1] i + [4] = idle(F(),open(),stop(),b1,false(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),empty()) = [4] > [0] = correct() busy(FS(),d,stop(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] i + [4] > [0] = incorrect() busy(S(),d,stop(),b1,b2,true(),i) = [1] b1 + [1] b2 + [1] d + [1] i + [8] > [1] b1 + [1] b2 + [1] i + [4] = idle(S(),open(),stop(),b1,b2,false(),i) busy(S(),closed(),stop(),false(),false(),false(),empty()) = [4] > [0] = correct() idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] i + [1] i1 + [1] i2 + [1] i3 + [1] m + [2] > [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] i + [1] i1 + [1] i2 + [1] i3 + [1] m + [0] = busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) start(i) = [1] i + [7] > [1] i + [4] = busy(F(),closed(),stop(),false(),false(),false(),i) Following rules are (at-least) weakly oriented: busy(fl,open(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [0] >= [0] = incorrect() busy(fl,open(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [0] >= [0] = incorrect() busy(B(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [6] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [6] = idle(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) = [1] i + [8] >= [1] i + [8] = idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) = [1] b3 + [1] i + [8] >= [1] b3 + [1] i + [8] = idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [4] >= [1] b2 + [1] b3 + [1] i + [4] = idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [8] >= [1] b2 + [1] b3 + [1] i + [8] = idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [4] >= [1] b2 + [1] b3 + [1] i + [4] = idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b3 + [1] i + [4] = idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [8] >= [1] b1 + [1] b3 + [1] i + [8] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [6] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [6] = idle(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) = [1] i + [8] >= [1] i + [8] = idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) = [1] b3 + [1] i + [8] >= [1] b3 + [1] i + [8] = idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b3 + [1] i + [4] = idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [8] >= [1] b1 + [1] b3 + [1] i + [8] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b3 + [1] i + [4] = idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [4] >= [1] b1 + [1] b2 + [1] i + [4] = idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) = [1] b1 + [1] b2 + [1] i + [8] >= [1] b1 + [1] b2 + [1] i + [8] = idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) = [1] b1 + [1] i + [8] >= [1] b1 + [1] i + [8] = idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [6] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [6] = idle(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) = [1] i + [8] >= [1] i + [8] = idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [4] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [4] = idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [4] >= [1] b1 + [1] b2 + [1] i + [4] = idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [0] = busy(fl,d,m,b1,b2,b3,empty()) or(false(),b) = [1] b + [0] >= [1] b + [0] = b or(true(),b) = [1] b + [4] >= [4] = true() ** Step 1.a:2: Assumption. WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) or(false(),b) -> b or(true(),b) -> true() - Weak TRS: busy(B(),d,stop(),true(),b2,b3,i) -> idle(B(),open(),stop(),false(),b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(BF(),d,stop(),b1,b2,b3,i) -> incorrect() busy(F(),d,stop(),b1,true(),b3,i) -> idle(F(),open(),stop(),b1,false(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),empty()) -> correct() busy(FS(),d,stop(),b1,b2,b3,i) -> incorrect() busy(S(),d,stop(),b1,b2,true(),i) -> idle(S(),open(),stop(),b1,b2,false(),i) busy(S(),closed(),stop(),false(),false(),false(),empty()) -> correct() idle(fl,d,m,b1,b2,b3,newbuttons(i1,i2,i3,i)) -> busy(fl,d,m,or(b1,i1),or(b2,i2),or(b3,i3),i) start(i) -> busy(F(),closed(),stop(),false(),false(),false(),i) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}} + Details: () ** Step 1.b:1: DecomposeCP. MAYBE + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) or(false(),b) -> b or(true(),b) -> true() - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeMul, withCP_ = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly: or(false(),b) -> b or(true(),b) -> true() The Processor induces the complexity certificate TIME (?,O(n^1)) BEST_CASE TIME (?,?) SPACE(?,?) Observe that Problem (R) is non-size-increasing. Once the complexity of (R) has been assessed, it suffices to consider only rules whose complexity has not been estimated in (R) resulting in the following Problem (S). Overall the certificate is obtained by multiplication. Problem (S) - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0 ,incorrect/0,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} *** Step 1.b:1.a:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) or(false(),b) -> b or(true(),b) -> true() - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(B) = [0] p(BF) = [0] p(F) = [0] p(FS) = [0] p(S) = [0] p(busy) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(closed) = [0] p(correct) = [1] p(down) = [0] p(empty) = [3] p(false) = [0] p(idle) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(incorrect) = [0] p(newbuttons) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [0] p(open) = [0] p(or) = [1] x1 + [1] x2 + [1] p(start) = [1] x1 + [0] p(stop) = [0] p(true) = [0] p(up) = [0] Following rules are strictly oriented: or(false(),b) = [1] b + [1] > [1] b + [0] = b or(true(),b) = [1] b + [1] > [0] = true() Following rules are (at-least) weakly oriented: busy(fl,open(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [0] >= [0] = incorrect() busy(fl,open(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [0] >= [0] = incorrect() busy(B(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [0] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [0] = idle(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) = [1] i + [0] >= [1] i + [0] = idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) = [1] b3 + [1] i + [0] >= [1] b3 + [1] i + [0] = idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [0] >= [1] b2 + [1] b3 + [1] i + [0] = idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [0] >= [1] b2 + [1] b3 + [1] i + [0] = idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [0] >= [1] b2 + [1] b3 + [1] i + [0] = idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b3 + [1] i + [0] = idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b3 + [1] i + [0] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [0] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [0] = idle(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) = [1] i + [0] >= [1] i + [0] = idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) = [1] b3 + [1] i + [0] >= [1] b3 + [1] i + [0] = idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b3 + [1] i + [0] = idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b3 + [1] i + [0] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b3 + [1] i + [0] = idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [0] >= [1] b1 + [1] b2 + [1] i + [0] = idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) = [1] b1 + [1] b2 + [1] i + [0] >= [1] b1 + [1] b2 + [1] i + [0] = idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) = [1] b1 + [1] i + [0] >= [1] b1 + [1] i + [0] = idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [0] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [0] = idle(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) = [1] i + [0] >= [1] i + [0] = idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [0] = idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [0] >= [1] b1 + [1] b2 + [1] i + [0] = idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [3] >= [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [3] = busy(fl,d,m,b1,b2,b3,empty()) *** Step 1.b:1.a:2: Assumption. WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Weak TRS: or(false(),b) -> b or(true(),b) -> true() - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}} + Details: () *** Step 1.b:1.b:1: DecomposeCP. MAYBE + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeMul, withCP_ = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() The Processor induces the complexity certificate TIME (?,O(n^1)) BEST_CASE TIME (?,?) SPACE(?,?) Observe that Problem (R) is non-size-increasing. Once the complexity of (R) has been assessed, it suffices to consider only rules whose complexity has not been estimated in (R) resulting in the following Problem (S). Overall the certificate is obtained by multiplication. Problem (S) - Strict TRS: busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0 ,incorrect/0,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} **** Step 1.b:1.b:1.a:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(B) = [0] p(BF) = [0] p(F) = [0] p(FS) = [0] p(S) = [0] p(busy) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(closed) = [0] p(correct) = [0] p(down) = [1] p(empty) = [0] p(false) = [1] p(idle) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [1] x5 + [1] x6 + [1] x7 + [0] p(incorrect) = [0] p(newbuttons) = [1] x1 + [1] x2 + [1] x3 + [1] x4 + [0] p(open) = [0] p(or) = [1] x1 + [1] x2 + [0] p(start) = [1] x1 + [0] p(stop) = [1] p(true) = [0] p(up) = [1] Following rules are strictly oriented: busy(fl,open(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [1] > [0] = incorrect() busy(fl,open(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] fl + [1] i + [1] > [0] = incorrect() Following rules are (at-least) weakly oriented: busy(B(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [4] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [4] = idle(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) = [1] i + [3] >= [1] i + [3] = idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) = [1] b3 + [1] i + [2] >= [1] b3 + [1] i + [2] = idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [2] >= [1] b2 + [1] b3 + [1] i + [2] = idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [1] >= [1] b2 + [1] b3 + [1] i + [1] = idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) = [1] b2 + [1] b3 + [1] i + [2] >= [1] b2 + [1] b3 + [1] i + [2] = idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [2] >= [1] b1 + [1] b3 + [1] i + [2] = idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b3 + [1] i + [1] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [4] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [4] = idle(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) = [1] i + [3] >= [1] i + [3] = idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) = [1] b3 + [1] i + [2] >= [1] b3 + [1] i + [2] = idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [2] >= [1] b1 + [1] b3 + [1] i + [2] = idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) = [1] b1 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b3 + [1] i + [1] = idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) = [1] b1 + [1] b3 + [1] i + [2] >= [1] b1 + [1] b3 + [1] i + [2] = idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [2] >= [1] b1 + [1] b2 + [1] i + [2] = idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) = [1] b1 + [1] b2 + [1] i + [1] >= [1] b1 + [1] b2 + [1] i + [1] = idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) = [1] b1 + [1] i + [2] >= [1] b1 + [1] i + [2] = idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) = [1] i + [1] i1 + [1] i2 + [1] i3 + [4] >= [1] i + [1] i1 + [1] i2 + [1] i3 + [4] = idle(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) = [1] i + [3] >= [1] i + [3] = idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) = [1] b1 + [1] b2 + [1] b3 + [1] i + [1] >= [1] b1 + [1] b2 + [1] b3 + [1] i + [1] = idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) = [1] b1 + [1] b2 + [1] i + [2] >= [1] b1 + [1] b2 + [1] i + [2] = idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) = [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [0] >= [1] b1 + [1] b2 + [1] b3 + [1] d + [1] fl + [1] m + [0] = busy(fl,d,m,b1,b2,b3,empty()) **** Step 1.b:1.b:1.a:2: Assumption. WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: busy(B(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),stop(),b1,b2,b3,i) busy(B(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(B() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(B(),closed(),stop(),false(),false(),true(),i) -> idle(B(),closed(),up(),false(),false(),true(),i) busy(B(),closed(),stop(),false(),true(),b3,i) -> idle(B(),closed(),up(),false(),true(),b3,i) busy(B(),closed(),up(),false(),b2,b3,i) -> idle(BF(),closed(),up(),false(),b2,b3,i) busy(B(),closed(),up(),true(),b2,b3,i) -> idle(B(),closed(),stop(),true(),b2,b3,i) busy(B(),open(),stop(),false(),b2,b3,i) -> idle(B(),closed(),stop(),false(),b2,b3,i) busy(BF(),closed(),down(),b1,b2,b3,i) -> idle(B(),closed(),down(),b1,b2,b3,i) busy(BF(),closed(),up(),b1,b2,b3,i) -> idle(F(),closed(),up(),b1,b2,b3,i) busy(F(),closed(),down(),b1,false(),b3,i) -> idle(BF(),closed(),down(),b1,false(),b3,i) busy(F(),closed(),down(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(F() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(F(),closed(),stop(),false(),false(),true(),i) -> idle(F(),closed(),up(),false(),false(),true(),i) busy(F(),closed(),stop(),true(),false(),b3,i) -> idle(F(),closed(),down(),true(),false(),b3,i) busy(F(),closed(),up(),b1,false(),b3,i) -> idle(FS(),closed(),up(),b1,false(),b3,i) busy(F(),closed(),up(),b1,true(),b3,i) -> idle(F(),closed(),stop(),b1,true(),b3,i) busy(F(),open(),stop(),b1,false(),b3,i) -> idle(F(),closed(),stop(),b1,false(),b3,i) busy(FS(),closed(),down(),b1,b2,b3,i) -> idle(F(),closed(),down(),b1,b2,b3,i) busy(FS(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),up(),b1,b2,b3,i) busy(S(),closed(),down(),b1,b2,false(),i) -> idle(FS(),closed(),down(),b1,b2,false(),i) busy(S(),closed(),down(),b1,b2,true(),i) -> idle(S(),closed(),stop(),b1,b2,true(),i) busy(S(),closed(),stop(),b1,true(),false(),i) -> idle(S(),closed(),down(),b1,true(),false(),i) busy(S(),closed(),stop(),false(),false(),false(),newbuttons(i1,i2,i3,i)) -> idle(S() ,closed() ,stop() ,false() ,false() ,false() ,newbuttons(i1,i2,i3,i)) busy(S(),closed(),stop(),true(),false(),false(),i) -> idle(S(),closed(),down(),true(),false(),false(),i) busy(S(),closed(),up(),b1,b2,b3,i) -> idle(S(),closed(),stop(),b1,b2,b3,i) busy(S(),open(),stop(),b1,b2,false(),i) -> idle(S(),closed(),stop(),b1,b2,false(),i) idle(fl,d,m,b1,b2,b3,empty()) -> busy(fl,d,m,b1,b2,b3,empty()) - Weak TRS: busy(fl,open(),down(),b1,b2,b3,i) -> incorrect() busy(fl,open(),up(),b1,b2,b3,i) -> incorrect() - Signature: {busy/7,idle/7,or/2,start/1} / {B/0,BF/0,F/0,FS/0,S/0,closed/0,correct/0,down/0,empty/0,false/0,incorrect/0 ,newbuttons/4,open/0,stop/0,true/0,up/0} - Obligation: innermost derivational complexity wrt. signature {B,BF,F,FS,S,busy,closed,correct,down,empty,false,idle ,incorrect,newbuttons,open,or,start,stop,true,up} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}} + Details: () **** Step 1.b:1.b:1.b:1: Failure MAYBE timed out MAYBE