(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
Q is empty.
(1) AAECC Innermost (EQUIVALENT transformation)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is
inc(0) → s(0)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
inc(s(x)) → s(inc(x))
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
The TRS R 2 is
f → g
f → h
The signature Sigma is {
f,
g,
h}
(2) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
(3) DependencyPairsProof (EQUIVALENT transformation)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
(4) Obligation:
Q DP problem:
The TRS P consists of the following rules:
INC(s(x)) → INC(x)
PLUS(x, y) → IFPLUS(eq(x, 0), minus(x, s(0)), x, inc(x))
PLUS(x, y) → EQ(x, 0)
PLUS(x, y) → MINUS(x, s(0))
PLUS(x, y) → INC(x)
IFPLUS(false, x, y, z) → PLUS(x, z)
MINUS(s(x), s(y)) → MINUS(x, y)
EQ(s(x), s(y)) → EQ(x, y)
TIMES(x, y) → TIMESITER(x, y, 0)
TIMESITER(x, y, z) → IFTIMES(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
TIMESITER(x, y, z) → EQ(x, 0)
TIMESITER(x, y, z) → MINUS(x, s(0))
TIMESITER(x, y, z) → PLUS(y, z)
IFTIMES(false, x, y, z, u) → TIMESITER(x, y, u)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.
(5) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 7 less nodes.
(6) Complex Obligation (AND)
(7) Obligation:
Q DP problem:
The TRS P consists of the following rules:
EQ(s(x), s(y)) → EQ(x, y)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.
(8) Obligation:
Q DP problem:
The TRS P consists of the following rules:
MINUS(s(x), s(y)) → MINUS(x, y)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.
(9) Obligation:
Q DP problem:
The TRS P consists of the following rules:
INC(s(x)) → INC(x)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.
(10) Obligation:
Q DP problem:
The TRS P consists of the following rules:
PLUS(x, y) → IFPLUS(eq(x, 0), minus(x, s(0)), x, inc(x))
IFPLUS(false, x, y, z) → PLUS(x, z)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.
(11) Obligation:
Q DP problem:
The TRS P consists of the following rules:
TIMESITER(x, y, z) → IFTIMES(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
IFTIMES(false, x, y, z, u) → TIMESITER(x, y, u)
The TRS R consists of the following rules:
inc(s(x)) → s(inc(x))
inc(0) → s(0)
plus(x, y) → ifPlus(eq(x, 0), minus(x, s(0)), x, inc(x))
ifPlus(false, x, y, z) → plus(x, z)
ifPlus(true, x, y, z) → y
minus(s(x), s(y)) → minus(x, y)
minus(0, x) → 0
minus(x, 0) → x
minus(x, x) → 0
eq(s(x), s(y)) → eq(x, y)
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(0, 0) → true
eq(x, x) → true
times(x, y) → timesIter(x, y, 0)
timesIter(x, y, z) → ifTimes(eq(x, 0), minus(x, s(0)), y, z, plus(y, z))
ifTimes(true, x, y, z, u) → z
ifTimes(false, x, y, z, u) → timesIter(x, y, u)
f → g
f → h
The set Q consists of the following terms:
inc(s(x0))
inc(0)
plus(x0, x1)
ifPlus(false, x0, x1, x2)
ifPlus(true, x0, x1, x2)
minus(s(x0), s(x1))
minus(0, x0)
minus(x0, 0)
minus(x0, x0)
eq(s(x0), s(x1))
eq(0, s(x0))
eq(s(x0), 0)
eq(x0, x0)
times(x0, x1)
timesIter(x0, x1, x2)
ifTimes(true, x0, x1, x2, x3)
ifTimes(false, x0, x1, x2, x3)
f
We have to consider all minimal (P,Q,R)-chains.