/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR v_NonEmpty:S x:S xs:S y:S ys:S zs:S) (RULES app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ) Problem 1: Valid CTRS Processor: -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) -> The system is a deterministic 3-CTRS. Problem 1: Dependency Pairs Processor: Conditional Termination Problem 1: -> Pairs: APP(cons(x:S,xs:S),ys:S) -> APP(xs:S,ys:S) LE(s(x:S),s(y:S)) -> LE(x:S,y:S) QSORT(cons(x:S,xs:S)) -> APP(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(ys:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) Conditional Termination Problem 2: -> Pairs: QSORT(cons(x:S,xs:S)) -> SPLIT(x:S,xs:S) SPLIT(x:S,cons(y:S,ys:S)) -> LE(x:S,y:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S) SPLIT(x:S,cons(y:S,ys:S)) -> SPLIT(x:S,ys:S) -> QPairs: LE(s(x:S),s(y:S)) -> LE(x:S,y:S) -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) The problem is decomposed in 2 subproblems. Problem 1.1: SCC Processor: -> Pairs: APP(cons(x:S,xs:S),ys:S) -> APP(xs:S,ys:S) LE(s(x:S),s(y:S)) -> LE(x:S,y:S) QSORT(cons(x:S,xs:S)) -> APP(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(ys:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: LE(s(x:S),s(y:S)) -> LE(x:S,y:S) -> QPairs: Empty ->->-> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->->Cycle: ->->-> Pairs: APP(cons(x:S,xs:S),ys:S) -> APP(xs:S,ys:S) -> QPairs: Empty ->->-> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->->Cycle: ->->-> Pairs: QSORT(cons(x:S,xs:S)) -> QSORT(ys:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> QPairs: Empty ->->-> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) The problem is decomposed in 3 subproblems. Problem 1.1.1: Conditional Subterm Processor: -> Pairs: LE(s(x:S),s(y:S)) -> LE(x:S,y:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Projection: pi(LE) = 1 Problem 1.1.1: SCC Processor: -> Pairs: Empty -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.1.2: Conditional Subterm Processor: -> Pairs: APP(cons(x:S,xs:S),ys:S) -> APP(xs:S,ys:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Projection: pi(APP) = 1 Problem 1.1.2: SCC Processor: -> Pairs: Empty -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.1.3: Reduction Pair Processor: -> Pairs: QSORT(cons(x:S,xs:S)) -> QSORT(ys:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) -> Needed rules: Empty -> Usable rules: le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Mace4 Output: ============================== Mace4 ================================= Mace4 (64) version 2009-11A, November 2009. Process 7313 was started by sandbox2 on n053.star.cs.uiowa.edu, Wed Jul 1 00:11:47 2020 The command was "./mace4 -c -f /tmp/mace45965166491189641421.in". ============================== end of head =========================== ============================== INPUT ================================= % Reading from file /tmp/mace45965166491189641421.in assign(max_seconds,20). formulas(assumptions). arrowStar_s0(x,x) # label(reflexivity). arrow_s0(x,y) & arrowStar_s0(y,z) -> arrowStar_s0(x,z) # label(compatibility). gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility). arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f4(x1),f4(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f5(x1,x2),f5(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f5(x1,x2),f5(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f12(x1,x2),f12(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f12(x1,x2),f12(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f13(x1),f13(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f2(x1,x2),f2(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f2(x1,x2),f2(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f3(x1,x2),f3(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f3(x1,x2),f3(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f4(x1),f4(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f5(x1,x2),f5(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f5(x1,x2),f5(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f7(x1,x2),f7(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f7(x1,x2),f7(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f11(x1,x2),f11(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f11(x1,x2),f11(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f12(x1,x2),f12(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f12(x1,x2),f12(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f13(x1),f13(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f17(x1,x2),f17(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f17(x1,x2),f17(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f18(x1,x2),f18(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f18(x1,x2),f18(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f19(x1),f19(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f20(x1,x2),f20(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f20(x1,x2),f20(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f21(x1,x2),f21(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f21(x1,x2),f21(x1,y)) # label(congruence). arrow_s0(f3(f6,x1),f14) # label(replacement). arrow_s0(f3(f13(x1),f6),f9) # label(replacement). arrow_s0(f3(f13(x1),f13(x3)),f3(x1,x3)) # label(replacement). arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f9) -> arrow_s0(f5(x1,f7(x3,x4)),f11(f7(x3,x2),x5)) # label(replacement). arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f14) -> arrow_s0(f5(x1,f7(x3,x4)),f11(x2,f7(x3,x5))) # label(replacement). arrow_s0(f5(x1,f10),f11(f10,f10)) # label(replacement). arrow_s0(f21(x6,x7),x6) # label(replacement). arrow_s0(f21(x6,x7),x7) # label(replacement). arrowN_s0(f21(x6,x7),x6) # label(replacement). arrowN_s0(f21(x6,x7),x7) # label(replacement). arrowN_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion). arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> sqsupset_s0(f19(f7(x1,x2)),f19(x4)) # label(replacement). arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> succeq_s0(f19(f7(x1,x2)),f19(x5)) # label(replacement). sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion). sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility). end_of_list. formulas(goals). (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness). end_of_list. ============================== end of input ========================== ============================== PROCESS NON-CLAUSAL FORMULAS ========== % Formulas that are not ordinary clauses: 1 arrow_s0(x,y) & arrowStar_s0(y,z) -> arrowStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 2 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 3 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 4 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 5 arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 6 arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 7 arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause). [assumption]. 8 arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause). [assumption]. 9 arrow_s0(x1,y) -> arrow_s0(f4(x1),f4(y)) # label(congruence) # label(non_clause). [assumption]. 10 arrow_s0(x1,y) -> arrow_s0(f5(x1,x2),f5(y,x2)) # label(congruence) # label(non_clause). [assumption]. 11 arrow_s0(x2,y) -> arrow_s0(f5(x1,x2),f5(x1,y)) # label(congruence) # label(non_clause). [assumption]. 12 arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence) # label(non_clause). [assumption]. 13 arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence) # label(non_clause). [assumption]. 14 arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause). [assumption]. 15 arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause). [assumption]. 16 arrow_s0(x1,y) -> arrow_s0(f12(x1,x2),f12(y,x2)) # label(congruence) # label(non_clause). [assumption]. 17 arrow_s0(x2,y) -> arrow_s0(f12(x1,x2),f12(x1,y)) # label(congruence) # label(non_clause). [assumption]. 18 arrow_s0(x1,y) -> arrow_s0(f13(x1),f13(y)) # label(congruence) # label(non_clause). [assumption]. 19 arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence) # label(non_clause). [assumption]. 20 arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence) # label(non_clause). [assumption]. 21 arrowN_s0(x1,y) -> arrowN_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 22 arrowN_s0(x2,y) -> arrowN_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 23 arrowN_s0(x1,y) -> arrowN_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause). [assumption]. 24 arrowN_s0(x2,y) -> arrowN_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause). [assumption]. 25 arrowN_s0(x1,y) -> arrowN_s0(f4(x1),f4(y)) # label(congruence) # label(non_clause). [assumption]. 26 arrowN_s0(x1,y) -> arrowN_s0(f5(x1,x2),f5(y,x2)) # label(congruence) # label(non_clause). [assumption]. 27 arrowN_s0(x2,y) -> arrowN_s0(f5(x1,x2),f5(x1,y)) # label(congruence) # label(non_clause). [assumption]. 28 arrowN_s0(x1,y) -> arrowN_s0(f7(x1,x2),f7(y,x2)) # label(congruence) # label(non_clause). [assumption]. 29 arrowN_s0(x2,y) -> arrowN_s0(f7(x1,x2),f7(x1,y)) # label(congruence) # label(non_clause). [assumption]. 30 arrowN_s0(x1,y) -> arrowN_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause). [assumption]. 31 arrowN_s0(x2,y) -> arrowN_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause). [assumption]. 32 arrowN_s0(x1,y) -> arrowN_s0(f12(x1,x2),f12(y,x2)) # label(congruence) # label(non_clause). [assumption]. 33 arrowN_s0(x2,y) -> arrowN_s0(f12(x1,x2),f12(x1,y)) # label(congruence) # label(non_clause). [assumption]. 34 arrowN_s0(x1,y) -> arrowN_s0(f13(x1),f13(y)) # label(congruence) # label(non_clause). [assumption]. 35 arrowN_s0(x1,y) -> arrowN_s0(f17(x1,x2),f17(y,x2)) # label(congruence) # label(non_clause). [assumption]. 36 arrowN_s0(x2,y) -> arrowN_s0(f17(x1,x2),f17(x1,y)) # label(congruence) # label(non_clause). [assumption]. 37 arrowN_s0(x1,y) -> arrowN_s0(f18(x1,x2),f18(y,x2)) # label(congruence) # label(non_clause). [assumption]. 38 arrowN_s0(x2,y) -> arrowN_s0(f18(x1,x2),f18(x1,y)) # label(congruence) # label(non_clause). [assumption]. 39 arrowN_s0(x1,y) -> arrowN_s0(f19(x1),f19(y)) # label(congruence) # label(non_clause). [assumption]. 40 arrowN_s0(x1,y) -> arrowN_s0(f20(x1,x2),f20(y,x2)) # label(congruence) # label(non_clause). [assumption]. 41 arrowN_s0(x2,y) -> arrowN_s0(f20(x1,x2),f20(x1,y)) # label(congruence) # label(non_clause). [assumption]. 42 arrowN_s0(x1,y) -> arrowN_s0(f21(x1,x2),f21(y,x2)) # label(congruence) # label(non_clause). [assumption]. 43 arrowN_s0(x2,y) -> arrowN_s0(f21(x1,x2),f21(x1,y)) # label(congruence) # label(non_clause). [assumption]. 44 arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f9) -> arrow_s0(f5(x1,f7(x3,x4)),f11(f7(x3,x2),x5)) # label(replacement) # label(non_clause). [assumption]. 45 arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f14) -> arrow_s0(f5(x1,f7(x3,x4)),f11(x2,f7(x3,x5))) # label(replacement) # label(non_clause). [assumption]. 46 arrowN_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 47 arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> sqsupset_s0(f19(f7(x1,x2)),f19(x4)) # label(replacement) # label(non_clause). [assumption]. 48 arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> succeq_s0(f19(f7(x1,x2)),f19(x5)) # label(replacement) # label(non_clause). [assumption]. 49 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 50 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 51 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness) # label(non_clause) # label(goal). [goal]. ============================== end of process non-clausal formulas === ============================== CLAUSES FOR SEARCH ==================== formulas(mace4_clauses). arrowStar_s0(x,x) # label(reflexivity). -arrow_s0(x,y) | -arrowStar_s0(y,z) | arrowStar_s0(x,z) # label(compatibility). -gtrsim_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -succeq_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -gtrsim_s0(x,y) | -succeq_s0(y,z) | gtrsim_s0(x,z) # label(compatibility). -arrow_s0(x,y) | arrow_s0(f2(x,z),f2(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f2(z,x),f2(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(x,z),f3(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(z,x),f3(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f4(x),f4(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(x,z),f5(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(z,x),f5(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(x,z),f7(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(z,x),f7(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(x,z),f11(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(z,x),f11(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f12(x,z),f12(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f12(z,x),f12(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f13(x),f13(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(x,z),f21(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(z,x),f21(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f2(x,z),f2(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f2(z,x),f2(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f3(x,z),f3(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f3(z,x),f3(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f4(x),f4(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f5(x,z),f5(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f5(z,x),f5(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f7(x,z),f7(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f7(z,x),f7(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f11(x,z),f11(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f11(z,x),f11(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f12(x,z),f12(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f12(z,x),f12(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f13(x),f13(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f17(x,z),f17(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f17(z,x),f17(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f18(x,z),f18(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f18(z,x),f18(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f19(x),f19(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f20(x,z),f20(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f20(z,x),f20(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f21(x,z),f21(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f21(z,x),f21(z,y)) # label(congruence). arrow_s0(f3(f6,x),f14) # label(replacement). arrow_s0(f3(f13(x),f6),f9) # label(replacement). arrow_s0(f3(f13(x),f13(y)),f3(x,y)) # label(replacement). -arrowStar_s0(f5(x,y),f12(z,u)) | -arrowStar_s0(f3(x,w),f9) | arrow_s0(f5(x,f7(w,y)),f11(f7(w,z),u)) # label(replacement). -arrowStar_s0(f5(x,y),f12(z,u)) | -arrowStar_s0(f3(x,w),f14) | arrow_s0(f5(x,f7(w,y)),f11(z,f7(w,u))) # label(replacement). arrow_s0(f5(x,f10),f11(f10,f10)) # label(replacement). arrow_s0(f21(x,y),x) # label(replacement). arrow_s0(f21(x,y),y) # label(replacement). arrowN_s0(f21(x,y),x) # label(replacement). arrowN_s0(f21(x,y),y) # label(replacement). -arrowN_s0(x,y) | gtrsim_s0(x,y) # label(inclusion). -arrowStar_s0(f5(x,y),f11(z,u)) | sqsupset_s0(f19(f7(x,y)),f19(z)) # label(replacement). -arrowStar_s0(f5(x,y),f11(z,u)) | succeq_s0(f19(f7(x,y)),f19(u)) # label(replacement). -sqsupset_s0(x,y) | sqsupsetStar_s0(x,y) # label(inclusion). -sqsupset_s0(x,y) | -sqsupsetStar_s0(y,z) | sqsupsetStar_s0(x,z) # label(compatibility). -sqsupsetStar_s0(x,x) # label(wellfoundedness). end_of_list. ============================== end of clauses for search ============= % There are no natural numbers in the input. ============================== DOMAIN SIZE 2 ========================= ============================== MODEL ================================= interpretation( 2, [number=1, seconds=0], [ function(f10, [ 0 ]), function(f14, [ 0 ]), function(f6, [ 0 ]), function(f9, [ 0 ]), function(f13(_), [ 0, 0 ]), function(f19(_), [ 0, 1 ]), function(f4(_), [ 0, 0 ]), function(f11(_,_), [ 0, 0, 1, 1 ]), function(f12(_,_), [ 1, 1, 1, 1 ]), function(f17(_,_), [ 0, 0, 0, 0 ]), function(f18(_,_), [ 0, 0, 0, 0 ]), function(f2(_,_), [ 0, 0, 0, 0 ]), function(f20(_,_), [ 0, 0, 0, 0 ]), function(f21(_,_), [ 0, 1, 1, 1 ]), function(f3(_,_), [ 0, 0, 0, 0 ]), function(f5(_,_), [ 0, 0, 0, 0 ]), function(f7(_,_), [ 1, 1, 1, 1 ]), relation(arrowN_s0(_,_), [ 1, 0, 1, 1 ]), relation(arrowStar_s0(_,_), [ 1, 0, 1, 1 ]), relation(arrow_s0(_,_), [ 1, 0, 1, 1 ]), relation(gtrsim_s0(_,_), [ 1, 0, 1, 1 ]), relation(sqsupsetStar_s0(_,_), [ 0, 0, 1, 0 ]), relation(sqsupset_s0(_,_), [ 0, 0, 1, 0 ]), relation(succeq_s0(_,_), [ 0, 0, 1, 1 ]) ]). ============================== end of model ========================== ============================== STATISTICS ============================ For domain size 2. Current CPU time: 0.00 seconds (total CPU time: 0.80 seconds). Ground clauses: seen=466, kept=462. Selections=69039, assignments=138047, propagations=223726, current_models=1. Rewrite_terms=5275362, rewrite_bools=3618306, indexes=185695. Rules_from_neg_clauses=100834, cross_offs=100834. ============================== end of statistics ===================== User_CPU=0.80, System_CPU=0.07, Wall_clock=1. Exiting with 1 model. Process 7313 exit (max_models) Wed Jul 1 00:11:48 2020 The process finished Wed Jul 1 00:11:48 2020 Mace4 cooked interpretation: % number = 1 % seconds = 0 % Interpretation of size 2 f10 = 0. f14 = 0. f6 = 0. f9 = 0. f13(0) = 0. f13(1) = 0. f19(0) = 0. f19(1) = 1. f4(0) = 0. f4(1) = 0. f11(0,0) = 0. f11(0,1) = 0. f11(1,0) = 1. f11(1,1) = 1. f12(0,0) = 1. f12(0,1) = 1. f12(1,0) = 1. f12(1,1) = 1. f17(0,0) = 0. f17(0,1) = 0. f17(1,0) = 0. f17(1,1) = 0. f18(0,0) = 0. f18(0,1) = 0. f18(1,0) = 0. f18(1,1) = 0. f2(0,0) = 0. f2(0,1) = 0. f2(1,0) = 0. f2(1,1) = 0. f20(0,0) = 0. f20(0,1) = 0. f20(1,0) = 0. f20(1,1) = 0. f21(0,0) = 0. f21(0,1) = 1. f21(1,0) = 1. f21(1,1) = 1. f3(0,0) = 0. f3(0,1) = 0. f3(1,0) = 0. f3(1,1) = 0. f5(0,0) = 0. f5(0,1) = 0. f5(1,0) = 0. f5(1,1) = 0. f7(0,0) = 1. f7(0,1) = 1. f7(1,0) = 1. f7(1,1) = 1. arrowN_s0(0,0). - arrowN_s0(0,1). arrowN_s0(1,0). arrowN_s0(1,1). arrowStar_s0(0,0). - arrowStar_s0(0,1). arrowStar_s0(1,0). arrowStar_s0(1,1). arrow_s0(0,0). - arrow_s0(0,1). arrow_s0(1,0). arrow_s0(1,1). gtrsim_s0(0,0). - gtrsim_s0(0,1). gtrsim_s0(1,0). gtrsim_s0(1,1). - sqsupsetStar_s0(0,0). - sqsupsetStar_s0(0,1). sqsupsetStar_s0(1,0). - sqsupsetStar_s0(1,1). - sqsupset_s0(0,0). - sqsupset_s0(0,1). sqsupset_s0(1,0). - sqsupset_s0(1,1). - succeq_s0(0,0). - succeq_s0(0,1). succeq_s0(1,0). succeq_s0(1,1). Problem 1.1.3: SCC Processor: -> Pairs: QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> QPairs: Empty ->->-> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) Problem 1.1.3: Reduction Pair Processor: -> Pairs: QSORT(cons(x:S,xs:S)) -> QSORT(zs:S) | split(x:S,xs:S) ->* pair(ys:S,zs:S) -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) -> Needed rules: Empty -> Usable rules: le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Mace4 Output: ============================== Mace4 ================================= Mace4 (64) version 2009-11A, November 2009. Process 7327 was started by sandbox2 on n053.star.cs.uiowa.edu, Wed Jul 1 00:11:48 2020 The command was "./mace4 -c -f /tmp/mace43040891721303455736.in". ============================== end of head =========================== ============================== INPUT ================================= % Reading from file /tmp/mace43040891721303455736.in assign(max_seconds,20). formulas(assumptions). arrowStar_s0(x,x) # label(reflexivity). arrow_s0(x,y) & arrowStar_s0(y,z) -> arrowStar_s0(x,z) # label(compatibility). gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility). gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility). arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f4(x1),f4(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f5(x1,x2),f5(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f5(x1,x2),f5(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f12(x1,x2),f12(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f12(x1,x2),f12(x1,y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f13(x1),f13(y)) # label(congruence). arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence). arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f2(x1,x2),f2(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f2(x1,x2),f2(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f3(x1,x2),f3(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f3(x1,x2),f3(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f4(x1),f4(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f5(x1,x2),f5(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f5(x1,x2),f5(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f7(x1,x2),f7(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f7(x1,x2),f7(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f11(x1,x2),f11(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f11(x1,x2),f11(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f12(x1,x2),f12(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f12(x1,x2),f12(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f13(x1),f13(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f17(x1,x2),f17(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f17(x1,x2),f17(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f18(x1,x2),f18(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f18(x1,x2),f18(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f19(x1),f19(y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f20(x1,x2),f20(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f20(x1,x2),f20(x1,y)) # label(congruence). arrowN_s0(x1,y) -> arrowN_s0(f21(x1,x2),f21(y,x2)) # label(congruence). arrowN_s0(x2,y) -> arrowN_s0(f21(x1,x2),f21(x1,y)) # label(congruence). arrow_s0(f3(f6,x1),f14) # label(replacement). arrow_s0(f3(f13(x1),f6),f9) # label(replacement). arrow_s0(f3(f13(x1),f13(x3)),f3(x1,x3)) # label(replacement). arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f9) -> arrow_s0(f5(x1,f7(x3,x4)),f11(f7(x3,x2),x5)) # label(replacement). arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f14) -> arrow_s0(f5(x1,f7(x3,x4)),f11(x2,f7(x3,x5))) # label(replacement). arrow_s0(f5(x1,f10),f11(f10,f10)) # label(replacement). arrow_s0(f21(x6,x7),x6) # label(replacement). arrow_s0(f21(x6,x7),x7) # label(replacement). arrowN_s0(f21(x6,x7),x6) # label(replacement). arrowN_s0(f21(x6,x7),x7) # label(replacement). arrowN_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion). arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> sqsupset_s0(f19(f7(x1,x2)),f19(x5)) # label(replacement). sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion). sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility). end_of_list. formulas(goals). (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness). end_of_list. ============================== end of input ========================== ============================== PROCESS NON-CLAUSAL FORMULAS ========== % Formulas that are not ordinary clauses: 1 arrow_s0(x,y) & arrowStar_s0(y,z) -> arrowStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 2 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 3 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 4 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 5 arrow_s0(x1,y) -> arrow_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 6 arrow_s0(x2,y) -> arrow_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 7 arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause). [assumption]. 8 arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause). [assumption]. 9 arrow_s0(x1,y) -> arrow_s0(f4(x1),f4(y)) # label(congruence) # label(non_clause). [assumption]. 10 arrow_s0(x1,y) -> arrow_s0(f5(x1,x2),f5(y,x2)) # label(congruence) # label(non_clause). [assumption]. 11 arrow_s0(x2,y) -> arrow_s0(f5(x1,x2),f5(x1,y)) # label(congruence) # label(non_clause). [assumption]. 12 arrow_s0(x1,y) -> arrow_s0(f7(x1,x2),f7(y,x2)) # label(congruence) # label(non_clause). [assumption]. 13 arrow_s0(x2,y) -> arrow_s0(f7(x1,x2),f7(x1,y)) # label(congruence) # label(non_clause). [assumption]. 14 arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause). [assumption]. 15 arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause). [assumption]. 16 arrow_s0(x1,y) -> arrow_s0(f12(x1,x2),f12(y,x2)) # label(congruence) # label(non_clause). [assumption]. 17 arrow_s0(x2,y) -> arrow_s0(f12(x1,x2),f12(x1,y)) # label(congruence) # label(non_clause). [assumption]. 18 arrow_s0(x1,y) -> arrow_s0(f13(x1),f13(y)) # label(congruence) # label(non_clause). [assumption]. 19 arrow_s0(x1,y) -> arrow_s0(f21(x1,x2),f21(y,x2)) # label(congruence) # label(non_clause). [assumption]. 20 arrow_s0(x2,y) -> arrow_s0(f21(x1,x2),f21(x1,y)) # label(congruence) # label(non_clause). [assumption]. 21 arrowN_s0(x1,y) -> arrowN_s0(f2(x1,x2),f2(y,x2)) # label(congruence) # label(non_clause). [assumption]. 22 arrowN_s0(x2,y) -> arrowN_s0(f2(x1,x2),f2(x1,y)) # label(congruence) # label(non_clause). [assumption]. 23 arrowN_s0(x1,y) -> arrowN_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause). [assumption]. 24 arrowN_s0(x2,y) -> arrowN_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause). [assumption]. 25 arrowN_s0(x1,y) -> arrowN_s0(f4(x1),f4(y)) # label(congruence) # label(non_clause). [assumption]. 26 arrowN_s0(x1,y) -> arrowN_s0(f5(x1,x2),f5(y,x2)) # label(congruence) # label(non_clause). [assumption]. 27 arrowN_s0(x2,y) -> arrowN_s0(f5(x1,x2),f5(x1,y)) # label(congruence) # label(non_clause). [assumption]. 28 arrowN_s0(x1,y) -> arrowN_s0(f7(x1,x2),f7(y,x2)) # label(congruence) # label(non_clause). [assumption]. 29 arrowN_s0(x2,y) -> arrowN_s0(f7(x1,x2),f7(x1,y)) # label(congruence) # label(non_clause). [assumption]. 30 arrowN_s0(x1,y) -> arrowN_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause). [assumption]. 31 arrowN_s0(x2,y) -> arrowN_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause). [assumption]. 32 arrowN_s0(x1,y) -> arrowN_s0(f12(x1,x2),f12(y,x2)) # label(congruence) # label(non_clause). [assumption]. 33 arrowN_s0(x2,y) -> arrowN_s0(f12(x1,x2),f12(x1,y)) # label(congruence) # label(non_clause). [assumption]. 34 arrowN_s0(x1,y) -> arrowN_s0(f13(x1),f13(y)) # label(congruence) # label(non_clause). [assumption]. 35 arrowN_s0(x1,y) -> arrowN_s0(f17(x1,x2),f17(y,x2)) # label(congruence) # label(non_clause). [assumption]. 36 arrowN_s0(x2,y) -> arrowN_s0(f17(x1,x2),f17(x1,y)) # label(congruence) # label(non_clause). [assumption]. 37 arrowN_s0(x1,y) -> arrowN_s0(f18(x1,x2),f18(y,x2)) # label(congruence) # label(non_clause). [assumption]. 38 arrowN_s0(x2,y) -> arrowN_s0(f18(x1,x2),f18(x1,y)) # label(congruence) # label(non_clause). [assumption]. 39 arrowN_s0(x1,y) -> arrowN_s0(f19(x1),f19(y)) # label(congruence) # label(non_clause). [assumption]. 40 arrowN_s0(x1,y) -> arrowN_s0(f20(x1,x2),f20(y,x2)) # label(congruence) # label(non_clause). [assumption]. 41 arrowN_s0(x2,y) -> arrowN_s0(f20(x1,x2),f20(x1,y)) # label(congruence) # label(non_clause). [assumption]. 42 arrowN_s0(x1,y) -> arrowN_s0(f21(x1,x2),f21(y,x2)) # label(congruence) # label(non_clause). [assumption]. 43 arrowN_s0(x2,y) -> arrowN_s0(f21(x1,x2),f21(x1,y)) # label(congruence) # label(non_clause). [assumption]. 44 arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f9) -> arrow_s0(f5(x1,f7(x3,x4)),f11(f7(x3,x2),x5)) # label(replacement) # label(non_clause). [assumption]. 45 arrowStar_s0(f5(x1,x4),f12(x2,x5)) & arrowStar_s0(f3(x1,x3),f14) -> arrow_s0(f5(x1,f7(x3,x4)),f11(x2,f7(x3,x5))) # label(replacement) # label(non_clause). [assumption]. 46 arrowN_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 47 arrowStar_s0(f5(x1,x2),f11(x4,x5)) -> sqsupset_s0(f19(f7(x1,x2)),f19(x5)) # label(replacement) # label(non_clause). [assumption]. 48 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion) # label(non_clause). [assumption]. 49 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility) # label(non_clause). [assumption]. 50 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness) # label(non_clause) # label(goal). [goal]. ============================== end of process non-clausal formulas === ============================== CLAUSES FOR SEARCH ==================== formulas(mace4_clauses). arrowStar_s0(x,x) # label(reflexivity). -arrow_s0(x,y) | -arrowStar_s0(y,z) | arrowStar_s0(x,z) # label(compatibility). -gtrsim_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -succeq_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility). -gtrsim_s0(x,y) | -succeq_s0(y,z) | gtrsim_s0(x,z) # label(compatibility). -arrow_s0(x,y) | arrow_s0(f2(x,z),f2(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f2(z,x),f2(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(x,z),f3(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f3(z,x),f3(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f4(x),f4(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(x,z),f5(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f5(z,x),f5(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(x,z),f7(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f7(z,x),f7(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(x,z),f11(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f11(z,x),f11(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f12(x,z),f12(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f12(z,x),f12(z,y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f13(x),f13(y)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(x,z),f21(y,z)) # label(congruence). -arrow_s0(x,y) | arrow_s0(f21(z,x),f21(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f2(x,z),f2(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f2(z,x),f2(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f3(x,z),f3(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f3(z,x),f3(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f4(x),f4(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f5(x,z),f5(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f5(z,x),f5(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f7(x,z),f7(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f7(z,x),f7(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f11(x,z),f11(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f11(z,x),f11(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f12(x,z),f12(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f12(z,x),f12(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f13(x),f13(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f17(x,z),f17(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f17(z,x),f17(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f18(x,z),f18(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f18(z,x),f18(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f19(x),f19(y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f20(x,z),f20(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f20(z,x),f20(z,y)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f21(x,z),f21(y,z)) # label(congruence). -arrowN_s0(x,y) | arrowN_s0(f21(z,x),f21(z,y)) # label(congruence). arrow_s0(f3(f6,x),f14) # label(replacement). arrow_s0(f3(f13(x),f6),f9) # label(replacement). arrow_s0(f3(f13(x),f13(y)),f3(x,y)) # label(replacement). -arrowStar_s0(f5(x,y),f12(z,u)) | -arrowStar_s0(f3(x,w),f9) | arrow_s0(f5(x,f7(w,y)),f11(f7(w,z),u)) # label(replacement). -arrowStar_s0(f5(x,y),f12(z,u)) | -arrowStar_s0(f3(x,w),f14) | arrow_s0(f5(x,f7(w,y)),f11(z,f7(w,u))) # label(replacement). arrow_s0(f5(x,f10),f11(f10,f10)) # label(replacement). arrow_s0(f21(x,y),x) # label(replacement). arrow_s0(f21(x,y),y) # label(replacement). arrowN_s0(f21(x,y),x) # label(replacement). arrowN_s0(f21(x,y),y) # label(replacement). -arrowN_s0(x,y) | gtrsim_s0(x,y) # label(inclusion). -arrowStar_s0(f5(x,y),f11(z,u)) | sqsupset_s0(f19(f7(x,y)),f19(u)) # label(replacement). -sqsupset_s0(x,y) | sqsupsetStar_s0(x,y) # label(inclusion). -sqsupset_s0(x,y) | -sqsupsetStar_s0(y,z) | sqsupsetStar_s0(x,z) # label(compatibility). -sqsupsetStar_s0(x,x) # label(wellfoundedness). end_of_list. ============================== end of clauses for search ============= % There are no natural numbers in the input. ============================== DOMAIN SIZE 2 ========================= ============================== MODEL ================================= interpretation( 2, [number=1, seconds=0], [ function(f10, [ 0 ]), function(f14, [ 0 ]), function(f6, [ 0 ]), function(f9, [ 0 ]), function(f13(_), [ 0, 0 ]), function(f19(_), [ 0, 1 ]), function(f4(_), [ 0, 0 ]), function(f11(_,_), [ 0, 1, 0, 1 ]), function(f12(_,_), [ 1, 1, 1, 1 ]), function(f17(_,_), [ 0, 0, 0, 0 ]), function(f18(_,_), [ 0, 0, 0, 0 ]), function(f2(_,_), [ 0, 0, 0, 0 ]), function(f20(_,_), [ 0, 0, 0, 0 ]), function(f21(_,_), [ 0, 1, 1, 1 ]), function(f3(_,_), [ 0, 0, 0, 0 ]), function(f5(_,_), [ 0, 0, 0, 0 ]), function(f7(_,_), [ 1, 1, 1, 1 ]), relation(arrowN_s0(_,_), [ 1, 0, 1, 1 ]), relation(arrowStar_s0(_,_), [ 1, 0, 1, 1 ]), relation(arrow_s0(_,_), [ 1, 0, 1, 1 ]), relation(gtrsim_s0(_,_), [ 1, 0, 1, 1 ]), relation(sqsupsetStar_s0(_,_), [ 0, 0, 1, 0 ]), relation(sqsupset_s0(_,_), [ 0, 0, 1, 0 ]), relation(succeq_s0(_,_), [ 0, 0, 0, 0 ]) ]). ============================== end of model ========================== ============================== STATISTICS ============================ For domain size 2. Current CPU time: 0.00 seconds (total CPU time: 0.75 seconds). Ground clauses: seen=450, kept=446. Selections=69041, assignments=138049, propagations=198437, current_models=1. Rewrite_terms=4769630, rewrite_bools=3383128, indexes=109186. Rules_from_neg_clauses=100834, cross_offs=100834. ============================== end of statistics ===================== User_CPU=0.75, System_CPU=0.06, Wall_clock=1. Exiting with 1 model. Process 7327 exit (max_models) Wed Jul 1 00:11:49 2020 The process finished Wed Jul 1 00:11:49 2020 Mace4 cooked interpretation: % number = 1 % seconds = 0 % Interpretation of size 2 f10 = 0. f14 = 0. f6 = 0. f9 = 0. f13(0) = 0. f13(1) = 0. f19(0) = 0. f19(1) = 1. f4(0) = 0. f4(1) = 0. f11(0,0) = 0. f11(0,1) = 1. f11(1,0) = 0. f11(1,1) = 1. f12(0,0) = 1. f12(0,1) = 1. f12(1,0) = 1. f12(1,1) = 1. f17(0,0) = 0. f17(0,1) = 0. f17(1,0) = 0. f17(1,1) = 0. f18(0,0) = 0. f18(0,1) = 0. f18(1,0) = 0. f18(1,1) = 0. f2(0,0) = 0. f2(0,1) = 0. f2(1,0) = 0. f2(1,1) = 0. f20(0,0) = 0. f20(0,1) = 0. f20(1,0) = 0. f20(1,1) = 0. f21(0,0) = 0. f21(0,1) = 1. f21(1,0) = 1. f21(1,1) = 1. f3(0,0) = 0. f3(0,1) = 0. f3(1,0) = 0. f3(1,1) = 0. f5(0,0) = 0. f5(0,1) = 0. f5(1,0) = 0. f5(1,1) = 0. f7(0,0) = 1. f7(0,1) = 1. f7(1,0) = 1. f7(1,1) = 1. arrowN_s0(0,0). - arrowN_s0(0,1). arrowN_s0(1,0). arrowN_s0(1,1). arrowStar_s0(0,0). - arrowStar_s0(0,1). arrowStar_s0(1,0). arrowStar_s0(1,1). arrow_s0(0,0). - arrow_s0(0,1). arrow_s0(1,0). arrow_s0(1,1). gtrsim_s0(0,0). - gtrsim_s0(0,1). gtrsim_s0(1,0). gtrsim_s0(1,1). - sqsupsetStar_s0(0,0). - sqsupsetStar_s0(0,1). sqsupsetStar_s0(1,0). - sqsupsetStar_s0(1,1). - sqsupset_s0(0,0). - sqsupset_s0(0,1). sqsupset_s0(1,0). - sqsupset_s0(1,1). - succeq_s0(0,0). - succeq_s0(0,1). - succeq_s0(1,0). - succeq_s0(1,1). Problem 1.1.3: SCC Processor: -> Pairs: Empty -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: SCC Processor: -> Pairs: QSORT(cons(x:S,xs:S)) -> SPLIT(x:S,xs:S) SPLIT(x:S,cons(y:S,ys:S)) -> LE(x:S,y:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S) SPLIT(x:S,cons(y:S,ys:S)) -> SPLIT(x:S,ys:S) -> QPairs: LE(s(x:S),s(y:S)) -> LE(x:S,y:S) -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: SPLIT(x:S,cons(y:S,ys:S)) -> SPLIT(x:S,ys:S) -> QPairs: Empty ->->-> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) Problem 1.2: Conditional Subterm Processor: -> Pairs: SPLIT(x:S,cons(y:S,ys:S)) -> SPLIT(x:S,ys:S) -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Projection: pi(SPLIT) = 2 Problem 1.2: SCC Processor: -> Pairs: Empty -> QPairs: Empty -> Rules: app(cons(x:S,xs:S),ys:S) -> cons(x:S,app(xs:S,ys:S)) app(nil,x:S) -> x:S le(0,x:S) -> ttrue le(s(x:S),0) -> ffalse le(s(x:S),s(y:S)) -> le(x:S,y:S) qsort(cons(x:S,xs:S)) -> app(qsort(ys:S),cons(x:S,qsort(zs:S))) | split(x:S,xs:S) ->* pair(ys:S,zs:S) qsort(nil) -> nil split(x:S,cons(y:S,ys:S)) -> pair(cons(y:S,xs:S),zs:S) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ffalse split(x:S,cons(y:S,ys:S)) -> pair(xs:S,cons(y:S,zs:S)) | split(x:S,ys:S) ->* pairs(xs:S,zs:S), le(x:S,y:S) ->* ttrue split(x:S,nil) -> pair(nil,nil) ->Strongly Connected Components: There is no strongly connected component The problem is finite.