/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.itrs /export/starexec/sandbox2/output/output_files


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


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.itrs
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given ITRS could be proven:

(0) ITRS
(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
(2) IDP
(3) UsableRulesProof [EQUIVALENT, 0 ms]
(4) IDP
(5) IDPtoQDPProof [SOUND, 59 ms]
(6) QDP
(7) QReductionProof [EQUIVALENT, 0 ms]
(8) QDP
(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
(10) YES


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

(0)
Obligation:
ITRS problem:

The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 + 	~ 	Add: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>

The TRS R consists of the following rules:
g(x, cons(y, ys)) -> cons(x + y, g(x, ys))
The set Q consists of the following terms:
g(x0, cons(x1, x2))

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

(1) ITRStoIDPProof (EQUIVALENT)
Added dependency pairs
----------------------------------------

(2)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 + 	~ 	Add: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

The ITRS R consists of the following rules:
g(x, cons(y, ys)) -> cons(x + y, g(x, ys))

The integer pair graph contains the following rules and edges:
(0): G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])

   (0) -> (0), if (x[0] ->^* x[0]' & ys[0] ->^* cons(y[0]', ys[0]'))

The set Q consists of the following terms:
g(x0, cons(x1, x2))

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

(3) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(4)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 + 	~ 	Add: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
none

R is empty.

The integer pair graph contains the following rules and edges:
(0): G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])

   (0) -> (0), if (x[0] ->^* x[0]' & ys[0] ->^* cons(y[0]', ys[0]'))

The set Q consists of the following terms:
g(x0, cons(x1, x2))

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

(5) IDPtoQDPProof (SOUND)
Represented integers and predefined function symbols by Terms
----------------------------------------

(6)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])

R is empty.
The set Q consists of the following terms:

   g(x0, cons(x1, x2))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(7) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   g(x0, cons(x1, x2))


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

(8)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(9) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*G(x[0], cons(y[0], ys[0])) -> G(x[0], ys[0])
The graph contains the following edges 1 >= 1, 2 > 2


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

(10)
YES