/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES

Problem 1: 

(VAR v_NonEmpty:S x:S y:S)
(RULES
f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
h(d) -> c(a)
h(d) -> c(b)
)

Problem 1: 
Valid CTRS Processor:
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)
-> The system is a deterministic 3-CTRS.

Problem 1: 

Dependency Pairs Processor:

Conditional Termination Problem 1:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)

Conditional Termination Problem 2:
-> Pairs:
 G(x:S) -> H(x:S)
 G(x:S) -> H(x:S) | h(x:S) ->* d
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)


The problem is decomposed in 2 subproblems.

Problem 1.1: 

SCC Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
->->-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)

Problem 1.1: 

Unsatisfiable Rule Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)
->AGES Output:
 
Model Results

System:
mod InTheory is
  sorts S Bool .

op _->*_ : S S -> Bool .
op _->_ : S S -> Bool .
op f : S S S -> S .
op g : S -> S .
op h : S -> S .
op a :  -> S .
op b :  -> S .
op c : S -> S .
op d :  -> S .
op fSNonEmpty :  -> S .
op k : S -> S .
op gtrsim : S S -> Bool .
op sqsupset : S S -> Bool .

endm


Property:
x:S ->R* x:S
x:S ->R y:S /\ y:S ->R* z:S => x:S ->R* z:S
gtrsim(x:S,y:S) /\ sqsupset(y:S,z:S) => sqsupset(x:S,z:S)
x1:S ->R y1:S => f(x1:S,x2:S,x3:S) ->R f(y1:S,x2:S,x3:S)
x2:S ->R y2:S => f(x1:S,x2:S,x3:S) ->R f(x1:S,y2:S,x3:S)
x3:S ->R y3:S => f(x1:S,x2:S,x3:S) ->R f(x1:S,x2:S,y3:S)
x1:S ->R y1:S => g(x1:S) ->R g(y1:S)
x1:S ->R y1:S => h(x1:S) ->R h(y1:S)
x1:S ->R y1:S => c(x1:S) ->R c(y1:S)
x1:S ->R y1:S => k(x1:S) ->R k(y1:S)
f(k(a),k(b),x:S) ->R f(x:S,x:S,x:S)
h(x:S) ->R* d /\ h(x:S) ->R* c(y:S) => g(x:S) ->R k(y:S)
h(d) ->R c(a)
h(d) ->R c(b)
x:S ->R y:S => gtrsim(x:S,y:S)
sqsupset(d,h(x:S))

Results:


Domains:
S: |N U {-1}

Function Interpretations:
|[f(x_1_1:S,x_2_1:S,x_3_1:S)]| = 1
|[g(x_1_1:S)]| = 1
|[h(x_1_1:S)]| = 0
|[a]| = 0
|[b]| = 0
|[c(x_1_1:S)]| = x_1_1:S
|[d]| = 1
|[fSNonEmpty]| =  - 1
|[k(x_1_1:S)]| =  - 1

Predicate Interpretations:
 x_1_1:S ->* x_2_1:S <=> (1 + x_1_1:S >= 0)
 x_1_1:S -> x_2_1:S <=> ((1 + x_1_1:S >= 0) /\ (x_1_1:S >= x_2_1:S))
gtrsim(x_1_1:S,x_2_1:S) <=> (x_1_1:S >= x_2_1:S)
sqsupset(x_1_1:S,x_2_1:S) <=> (2.x_1_1:S >= 1+2.x_2_1:S)

Problem 1.1: 

SCC Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> QPairs:
 Empty
->->-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)

Problem 1.1: 

Shift to Dependency Pair Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)

Problem 1.1: 

SCC Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
->->-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)

Problem 1.1: 

Forward Instantiation Processor:
-> Pairs:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Instantiated Pairs:
->->Original Pair:
 F(k(a),k(b),x:S) -> F(x:S,x:S,x:S)
->-> Instantiated pairs:
 Empty

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

SCC Processor:
-> Pairs:
 G(x:S) -> H(x:S)
 G(x:S) -> H(x:S) | h(x:S) ->* d
-> QPairs:
 Empty
-> Rules:
 f(k(a),k(b),x:S) -> f(x:S,x:S,x:S)
 g(x:S) -> k(y:S) | h(x:S) ->* d, h(x:S) ->* c(y:S)
 h(d) -> c(a)
 h(d) -> c(b)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.