interpretations
Execution Time (secs) | - |
Answer | YES(?,O(n^2)) |
Input | AG01 3.5 |
YES(?,O(n^2))
We are left with following problem, upon which TcT provides the
certificate YES(?,O(n^2)).
Strict Trs:
{ le(0(), y) -> true()
, le(s(x), 0()) -> false()
, le(s(x), s(y)) -> le(x, y)
, minus(x, 0()) -> x
, minus(s(x), s(y)) -> minus(x, y)
, mod(0(), y) -> 0()
, mod(s(x), 0()) -> 0()
, mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
, if_mod(true(), s(x), s(y)) -> mod(minus(x, y), s(y))
, if_mod(false(), s(x), s(y)) -> s(x) }
Obligation:
innermost runtime complexity
Answer:
YES(?,O(n^2))
The following argument positions are usable:
Uargs(le) = {}, Uargs(s) = {}, Uargs(minus) = {}, Uargs(mod) = {1},
Uargs(if_mod) = {1}
TcT has computed following constructor-restricted polynomial
interpretation.
[le](x1, x2) = 1 + 2*x1
[0]() = 0
[true]() = 0
[s](x1) = 3 + x1
[false]() = 0
[minus](x1, x2) = 2 + x1
[mod](x1, x2) = 2 + 3*x1 + 3*x1*x2 + 3*x2
[if_mod](x1, x2, x3) = x1 + 3*x2 + 3*x2*x3
This order satisfies following ordering constraints
[le(0(), y)] = 1
>
= [true()]
[le(s(x), 0())] = 7 + 2*x
>
= [false()]
[le(s(x), s(y))] = 7 + 2*x
> 1 + 2*x
= [le(x, y)]
[minus(x, 0())] = 2 + x
> x
= [x]
[minus(s(x), s(y))] = 5 + x
> 2 + x
= [minus(x, y)]
[mod(0(), y)] = 2 + 3*y
>
= [0()]
[mod(s(x), 0())] = 11 + 3*x
>
= [0()]
[mod(s(x), s(y))] = 47 + 12*x + 12*y + 3*x*y
> 37 + 11*y + 12*x + 3*x*y
= [if_mod(le(y, x), s(x), s(y))]
[if_mod(true(), s(x), s(y))] = 36 + 12*x + 9*y + 3*x*y
> 35 + 12*x + 9*y + 3*x*y
= [mod(minus(x, y), s(y))]
[if_mod(false(), s(x), s(y))] = 36 + 12*x + 9*y + 3*x*y
> 3 + x
= [s(x)]
Hurray, we answered YES(?,O(n^2))
lmpo
Execution Time (secs) | - |
Answer | MAYBE |
Input | AG01 3.5 |
MAYBE
We are left with following problem, upon which TcT provides the
certificate MAYBE.
Strict Trs:
{ le(0(), y) -> true()
, le(s(x), 0()) -> false()
, le(s(x), s(y)) -> le(x, y)
, minus(x, 0()) -> x
, minus(s(x), s(y)) -> minus(x, y)
, mod(0(), y) -> 0()
, mod(s(x), 0()) -> 0()
, mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
, if_mod(true(), s(x), s(y)) -> mod(minus(x, y), s(y))
, if_mod(false(), s(x), s(y)) -> s(x) }
Obligation:
innermost runtime complexity
Answer:
MAYBE
The input cannot be shown compatible
Arrrr..
mpo
Execution Time (secs) | - |
Answer | MAYBE |
Input | AG01 3.5 |
MAYBE
We are left with following problem, upon which TcT provides the
certificate MAYBE.
Strict Trs:
{ le(0(), y) -> true()
, le(s(x), 0()) -> false()
, le(s(x), s(y)) -> le(x, y)
, minus(x, 0()) -> x
, minus(s(x), s(y)) -> minus(x, y)
, mod(0(), y) -> 0()
, mod(s(x), 0()) -> 0()
, mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
, if_mod(true(), s(x), s(y)) -> mod(minus(x, y), s(y))
, if_mod(false(), s(x), s(y)) -> s(x) }
Obligation:
innermost runtime complexity
Answer:
MAYBE
The input cannot be shown compatible
Arrrr..
popstar
Execution Time (secs) | 0.253 |
Answer | MAYBE |
Input | AG01 3.5 |
MAYBE
We are left with following problem, upon which TcT provides the
certificate MAYBE.
Strict Trs:
{ le(0(), y) -> true()
, le(s(x), 0()) -> false()
, le(s(x), s(y)) -> le(x, y)
, minus(x, 0()) -> x
, minus(s(x), s(y)) -> minus(x, y)
, mod(0(), y) -> 0()
, mod(s(x), 0()) -> 0()
, mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
, if_mod(true(), s(x), s(y)) -> mod(minus(x, y), s(y))
, if_mod(false(), s(x), s(y)) -> s(x) }
Obligation:
innermost runtime complexity
Answer:
MAYBE
The input cannot be shown compatible
Arrrr..
popstar-ps
Execution Time (secs) | 0.227 |
Answer | MAYBE |
Input | AG01 3.5 |
MAYBE
We are left with following problem, upon which TcT provides the
certificate MAYBE.
Strict Trs:
{ le(0(), y) -> true()
, le(s(x), 0()) -> false()
, le(s(x), s(y)) -> le(x, y)
, minus(x, 0()) -> x
, minus(s(x), s(y)) -> minus(x, y)
, mod(0(), y) -> 0()
, mod(s(x), 0()) -> 0()
, mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y))
, if_mod(true(), s(x), s(y)) -> mod(minus(x, y), s(y))
, if_mod(false(), s(x), s(y)) -> s(x) }
Obligation:
innermost runtime complexity
Answer:
MAYBE
The input cannot be shown compatible
Arrrr..