21.63/21.75 YES 21.63/21.75 21.63/21.75 Problem 1: 21.63/21.75 21.63/21.75 (VAR v_NonEmpty:S fun:S x:S xs:S y:S) 21.63/21.75 (RULES 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ) 21.63/21.75 (STRATEGY INNERMOST) 21.63/21.75 21.63/21.75 Problem 1: 21.63/21.75 21.63/21.75 Dependency Pairs Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(f,x:S),app(app(plus,x:S),x:S)) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(plus,x:S),x:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(filter2,app(fun:S,x:S)),fun:S),x:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(filter2,app(fun:S,x:S)),fun:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(filter2,app(fun:S,x:S)) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(map,fun:S),xs:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(cons,app(fun:S,x:S)) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(app(plus,x:S),y:S) 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(s,app(app(plus,x:S),y:S)) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 21.63/21.75 Problem 1: 21.63/21.75 21.63/21.75 SCC Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(f,x:S),app(app(plus,x:S),x:S)) 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(plus,x:S),x:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(filter2,app(fun:S,x:S)),fun:S),x:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(filter2,app(fun:S,x:S)),fun:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(filter2,app(fun:S,x:S)) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(map,fun:S),xs:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(cons,app(fun:S,x:S)) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(app(plus,x:S),y:S) 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(s,app(app(plus,x:S),y:S)) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Strongly Connected Components: 21.63/21.75 ->->Cycle: 21.63/21.75 ->->-> Pairs: 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(app(plus,x:S),y:S) 21.63/21.75 ->->-> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->->Cycle: 21.63/21.75 ->->-> Pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 ->->-> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->->Cycle: 21.63/21.75 ->->-> Pairs: 21.63/21.75 APP(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(map,fun:S),xs:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 ->->-> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 21.63/21.75 21.63/21.75 The problem is decomposed in 3 subproblems. 21.63/21.75 21.63/21.75 Problem 1.1: 21.63/21.75 21.63/21.75 Subterm Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(plus,x:S),app(s,y:S)) -> APP(app(plus,x:S),y:S) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Projection: 21.63/21.75 pi(APP) = 2 21.63/21.75 21.63/21.75 Problem 1.1: 21.63/21.75 21.63/21.75 SCC Processor: 21.63/21.75 -> Pairs: 21.63/21.75 Empty 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Strongly Connected Components: 21.63/21.75 There is no strongly connected component 21.63/21.75 21.63/21.75 The problem is finite. 21.63/21.75 21.63/21.75 Problem 1.2: 21.63/21.75 21.63/21.75 Instantiation Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Instantiated Pairs: 21.63/21.75 ->->Original Pair: 21.63/21.75 APP(app(app(f,0),app(s,0)),x:S) -> APP(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 ->-> Instantiated pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),0) -> APP(app(app(f,0),app(app(plus,0),0)),0) 21.63/21.75 21.63/21.75 Problem 1.2: 21.63/21.75 21.63/21.75 SCC Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),0) -> APP(app(app(f,0),app(app(plus,0),0)),0) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Strongly Connected Components: 21.63/21.75 ->->Cycle: 21.63/21.75 ->->-> Pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),0) -> APP(app(app(f,0),app(app(plus,0),0)),0) 21.63/21.75 ->->-> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 21.63/21.75 Problem 1.2: 21.63/21.75 21.63/21.75 Reduction Pair Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(f,0),app(s,0)),0) -> APP(app(app(f,0),app(app(plus,0),0)),0) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 -> Usable rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Mace4 Output: 21.63/21.75 ============================== Mace4 ================================= 21.63/21.75 Mace4 (64) version 2009-11A, November 2009. 21.63/21.75 Process 35009 was started by sandbox on n132.star.cs.uiowa.edu, 21.63/21.75 Thu Mar 28 22:25:04 2019 21.63/21.75 The command was "./mace4 -c -f /tmp/mace41911759956749241873.in". 21.63/21.75 ============================== end of head =========================== 21.63/21.75 21.63/21.75 ============================== INPUT ================================= 21.63/21.75 21.63/21.75 % Reading from file /tmp/mace41911759956749241873.in 21.63/21.75 21.63/21.75 assign(max_seconds,20). 21.63/21.75 21.63/21.75 formulas(assumptions). 21.63/21.75 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). 21.63/21.75 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). 21.63/21.75 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility). 21.63/21.75 arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence). 21.63/21.75 arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence). 21.63/21.75 arrow_s0(x1,y) -> arrow_s0(f17(x1,x2),f17(y,x2)) # label(congruence). 21.63/21.75 arrow_s0(x2,y) -> arrow_s0(f17(x1,x2),f17(x1,y)) # label(congruence). 21.63/21.75 arrow_s0(f2(f2(f2(f2(f9,f7),x1),x2),x3),f2(f2(f8,x1),x3)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f2(f2(f9,f15),x1),x2),x3),f2(f2(f4,x2),f2(f2(f8,x1),x3))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f2(f5,f3),f2(f14,f3)),x2),f2(f2(f2(f5,x2),f2(f2(f13,x2),x2)),x2)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f8,x1),f2(f2(f4,x2),x3)),f2(f2(f2(f2(f9,f2(x1,x2)),x1),x2),x3)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f8,x1),f12),f12) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f10,x2),x4),x2) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f10,x2),x4),x4) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f11,x1),f2(f2(f4,x2),x3)),f2(f2(f4,f2(x1,x2)),f2(f2(f11,x1),x3))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f11,x1),f12),f12) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f13,x2),f2(f14,x4)),f2(f14,f2(f2(f13,x2),x4))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f13,x2),f3),x2) # label(replacement). 21.63/21.75 arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion). 21.63/21.75 sqsupset_s0(f17(f2(f2(f5,f3),f2(f14,f3)),f3),f17(f2(f2(f5,f3),f2(f2(f13,f3),f3)),f3)) # label(replacement). 21.63/21.75 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion). 21.63/21.75 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility). 21.63/21.75 end_of_list. 21.63/21.75 21.63/21.75 formulas(goals). 21.63/21.75 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness). 21.63/21.75 end_of_list. 21.63/21.75 21.63/21.75 ============================== end of input ========================== 21.63/21.75 21.63/21.75 ============================== PROCESS NON-CLAUSAL FORMULAS ========== 21.63/21.75 21.63/21.75 % Formulas that are not ordinary clauses: 21.63/21.75 1 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 21.63/21.75 2 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 21.63/21.75 3 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 21.63/21.75 4 arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 21.63/21.75 5 arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 21.63/21.75 6 arrow_s0(x1,y) -> arrow_s0(f17(x1,x2),f17(y,x2)) # label(congruence) # label(non_clause). [assumption]. 21.63/21.75 7 arrow_s0(x2,y) -> arrow_s0(f17(x1,x2),f17(x1,y)) # label(congruence) # label(non_clause). [assumption]. 21.63/21.75 8 arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 21.63/21.75 9 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 21.63/21.75 10 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 21.63/21.75 11 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness) # label(non_clause) # label(goal). [goal]. 21.63/21.75 21.63/21.75 ============================== end of process non-clausal formulas === 21.63/21.75 21.63/21.75 ============================== CLAUSES FOR SEARCH ==================== 21.63/21.75 21.63/21.75 formulas(mace4_clauses). 21.63/21.75 -gtrsim_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). 21.63/21.75 -succeq_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). 21.63/21.75 -gtrsim_s0(x,y) | -succeq_s0(y,z) | gtrsim_s0(x,z) # label(compatibility). 21.63/21.75 -arrow_s0(x,y) | arrow_s0(f2(x,z),f2(y,z)) # label(congruence). 21.63/21.75 -arrow_s0(x,y) | arrow_s0(f2(z,x),f2(z,y)) # label(congruence). 21.63/21.75 -arrow_s0(x,y) | arrow_s0(f17(x,z),f17(y,z)) # label(congruence). 21.63/21.75 -arrow_s0(x,y) | arrow_s0(f17(z,x),f17(z,y)) # label(congruence). 21.63/21.75 arrow_s0(f2(f2(f2(f2(f9,f7),x),y),z),f2(f2(f8,x),z)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f2(f2(f9,f15),x),y),z),f2(f2(f4,y),f2(f2(f8,x),z))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f2(f5,f3),f2(f14,f3)),x),f2(f2(f2(f5,x),f2(f2(f13,x),x)),x)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f8,x),f2(f2(f4,y),z)),f2(f2(f2(f2(f9,f2(x,y)),x),y),z)) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f8,x),f12),f12) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f10,x),y),x) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f10,x),y),y) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f11,x),f2(f2(f4,y),z)),f2(f2(f4,f2(x,y)),f2(f2(f11,x),z))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f11,x),f12),f12) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f13,x),f2(f14,y)),f2(f14,f2(f2(f13,x),y))) # label(replacement). 21.63/21.75 arrow_s0(f2(f2(f13,x),f3),x) # label(replacement). 21.63/21.75 -arrow_s0(x,y) | gtrsim_s0(x,y) # label(inclusion). 21.63/21.75 sqsupset_s0(f17(f2(f2(f5,f3),f2(f14,f3)),f3),f17(f2(f2(f5,f3),f2(f2(f13,f3),f3)),f3)) # label(replacement). 21.63/21.75 -sqsupset_s0(x,y) | sqsupsetStar_s0(x,y) # label(inclusion). 21.63/21.75 -sqsupset_s0(x,y) | -sqsupsetStar_s0(y,z) | sqsupsetStar_s0(x,z) # label(compatibility). 21.63/21.75 -sqsupsetStar_s0(x,x) # label(wellfoundedness). 21.63/21.75 end_of_list. 21.63/21.75 21.63/21.75 ============================== end of clauses for search ============= 21.63/21.75 21.63/21.75 % There are no natural numbers in the input. 21.63/21.75 21.63/21.75 ============================== DOMAIN SIZE 2 ========================= 21.63/21.75 21.63/21.75 ============================== MODEL ================================= 21.63/21.75 21.63/21.75 interpretation( 2, [number=1, seconds=0], [ 21.63/21.75 21.63/21.75 function(f10, [ 0 ]), 21.63/21.75 21.63/21.75 function(f11, [ 0 ]), 21.63/21.75 21.63/21.75 function(f12, [ 0 ]), 21.63/21.75 21.63/21.75 function(f13, [ 0 ]), 21.63/21.75 21.63/21.75 function(f14, [ 1 ]), 21.63/21.75 21.63/21.75 function(f15, [ 0 ]), 21.63/21.75 21.63/21.75 function(f3, [ 0 ]), 21.63/21.75 21.63/21.75 function(f4, [ 0 ]), 21.63/21.75 21.63/21.75 function(f5, [ 0 ]), 21.63/21.75 21.63/21.75 function(f7, [ 0 ]), 21.63/21.75 21.63/21.75 function(f8, [ 0 ]), 21.63/21.75 21.63/21.75 function(f9, [ 0 ]), 21.63/21.75 21.63/21.75 function(f17(_,_), [ 21.63/21.75 0, 0, 21.63/21.75 1, 1 ]), 21.63/21.75 21.63/21.75 function(f2(_,_), [ 21.63/21.75 0, 1, 21.63/21.75 1, 1 ]), 21.63/21.75 21.63/21.75 relation(arrow_s0(_,_), [ 21.63/21.75 1, 0, 21.63/21.75 1, 1 ]), 21.63/21.75 21.63/21.75 relation(gtrsim_s0(_,_), [ 21.63/21.75 1, 0, 21.63/21.75 1, 1 ]), 21.63/21.75 21.63/21.75 relation(sqsupsetStar_s0(_,_), [ 21.63/21.75 0, 0, 21.63/21.75 1, 0 ]), 21.63/21.75 21.63/21.75 relation(sqsupset_s0(_,_), [ 21.63/21.75 0, 0, 21.63/21.75 1, 0 ]), 21.63/21.75 21.63/21.75 relation(succeq_s0(_,_), [ 21.63/21.75 0, 0, 21.63/21.75 0, 0 ]) 21.63/21.75 ]). 21.63/21.75 21.63/21.75 ============================== end of model ========================== 21.63/21.75 21.63/21.75 ============================== STATISTICS ============================ 21.63/21.75 21.63/21.75 For domain size 2. 21.63/21.75 21.63/21.75 Current CPU time: 0.00 seconds (total CPU time: 0.69 seconds). 21.63/21.75 Ground clauses: seen=127, kept=127. 21.63/21.75 Selections=48032, assignments=96047, propagations=97780, current_models=1. 21.63/21.75 Rewrite_terms=5884534, rewrite_bools=1706923, indexes=681434. 21.63/21.75 Rules_from_neg_clauses=769, cross_offs=769. 21.63/21.75 21.63/21.75 ============================== end of statistics ===================== 21.63/21.75 21.63/21.75 User_CPU=0.69, System_CPU=0.03, Wall_clock=0. 21.63/21.75 21.63/21.75 Exiting with 1 model. 21.63/21.75 21.63/21.75 Process 35009 exit (max_models) Thu Mar 28 22:25:04 2019 21.63/21.75 The process finished Thu Mar 28 22:25:04 2019 21.63/21.75 21.63/21.75 21.63/21.75 Mace4 cooked interpretation: 21.63/21.75 21.63/21.75 % number = 1 21.63/21.75 % seconds = 0 21.63/21.75 21.63/21.75 % Interpretation of size 2 21.63/21.75 21.63/21.75 f10 = 0. 21.63/21.75 21.63/21.75 f11 = 0. 21.63/21.75 21.63/21.75 f12 = 0. 21.63/21.75 21.63/21.75 f13 = 0. 21.63/21.75 21.63/21.75 f14 = 1. 21.63/21.75 21.63/21.75 f15 = 0. 21.63/21.75 21.63/21.75 f3 = 0. 21.63/21.75 21.63/21.75 f4 = 0. 21.63/21.75 21.63/21.75 f5 = 0. 21.63/21.75 21.63/21.75 f7 = 0. 21.63/21.75 21.63/21.75 f8 = 0. 21.63/21.75 21.63/21.75 f9 = 0. 21.63/21.75 21.63/21.75 f17(0,0) = 0. 21.63/21.75 f17(0,1) = 0. 21.63/21.75 f17(1,0) = 1. 21.63/21.75 f17(1,1) = 1. 21.63/21.75 21.63/21.75 f2(0,0) = 0. 21.63/21.75 f2(0,1) = 1. 21.63/21.75 f2(1,0) = 1. 21.63/21.75 f2(1,1) = 1. 21.63/21.75 21.63/21.75 arrow_s0(0,0). 21.63/21.75 - arrow_s0(0,1). 21.63/21.75 arrow_s0(1,0). 21.63/21.75 arrow_s0(1,1). 21.63/21.75 21.63/21.75 gtrsim_s0(0,0). 21.63/21.75 - gtrsim_s0(0,1). 21.63/21.75 gtrsim_s0(1,0). 21.63/21.75 gtrsim_s0(1,1). 21.63/21.75 21.63/21.75 - sqsupsetStar_s0(0,0). 21.63/21.75 - sqsupsetStar_s0(0,1). 21.63/21.75 sqsupsetStar_s0(1,0). 21.63/21.75 - sqsupsetStar_s0(1,1). 21.63/21.75 21.63/21.75 - sqsupset_s0(0,0). 21.63/21.75 - sqsupset_s0(0,1). 21.63/21.75 sqsupset_s0(1,0). 21.63/21.75 - sqsupset_s0(1,1). 21.63/21.75 21.63/21.75 - succeq_s0(0,0). 21.63/21.75 - succeq_s0(0,1). 21.63/21.75 - succeq_s0(1,0). 21.63/21.75 - succeq_s0(1,1). 21.63/21.75 21.63/21.75 21.63/21.75 Problem 1.2: 21.63/21.75 21.63/21.75 SCC Processor: 21.63/21.75 -> Pairs: 21.63/21.75 Empty 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Strongly Connected Components: 21.63/21.75 There is no strongly connected component 21.63/21.75 21.63/21.75 The problem is finite. 21.63/21.75 21.63/21.75 Problem 1.3: 21.63/21.75 21.63/21.75 Subterm Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 APP(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(app(map,fun:S),xs:S) 21.63/21.75 APP(app(map,fun:S),app(app(cons,x:S),xs:S)) -> APP(fun:S,x:S) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Projection: 21.63/21.75 pi(APP) = 2 21.63/21.75 21.63/21.75 Problem 1.3: 21.63/21.75 21.63/21.75 SCC Processor: 21.63/21.75 -> Pairs: 21.63/21.75 APP(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 APP(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> APP(app(filter,fun:S),xs:S) 21.63/21.75 -> Rules: 21.63/21.75 app(app(app(app(filter2,ffalse),fun:S),x:S),xs:S) -> app(app(filter,fun:S),xs:S) 21.63/21.75 app(app(app(app(filter2,ttrue),fun:S),x:S),xs:S) -> app(app(cons,x:S),app(app(filter,fun:S),xs:S)) 21.63/21.75 app(app(app(f,0),app(s,0)),x:S) -> app(app(app(f,x:S),app(app(plus,x:S),x:S)),x:S) 21.63/21.75 app(app(filter,fun:S),app(app(cons,x:S),xs:S)) -> app(app(app(app(filter2,app(fun:S,x:S)),fun:S),x:S),xs:S) 21.63/21.75 app(app(filter,fun:S),nil) -> nil 21.63/21.75 app(app(g,x:S),y:S) -> x:S 21.63/21.75 app(app(g,x:S),y:S) -> y:S 21.63/21.75 app(app(map,fun:S),app(app(cons,x:S),xs:S)) -> app(app(cons,app(fun:S,x:S)),app(app(map,fun:S),xs:S)) 21.63/21.75 app(app(map,fun:S),nil) -> nil 21.63/21.75 app(app(plus,x:S),app(s,y:S)) -> app(s,app(app(plus,x:S),y:S)) 21.63/21.75 app(app(plus,x:S),0) -> x:S 21.63/21.75 ->Strongly Connected Components: 21.63/21.75 There is no strongly connected component 21.63/21.75 21.63/21.75 The problem is finite. 21.63/21.75 EOF