We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(n^1)).
Strict Trs:
{ not(x) -> xor(x, true())
, implies(x, y) -> xor(and(x, y), xor(x, true()))
, or(x, y) -> xor(and(x, y), xor(x, y))
, =(x, y) -> xor(x, xor(y, true())) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(n^1))
We add the following weak dependency pairs:
Strict DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y)
, =^#(x, y) -> c_4(x, y) }
and mark the set of starting terms.
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(n^1)).
Strict DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y)
, =^#(x, y) -> c_4(x, y) }
Strict Trs:
{ not(x) -> xor(x, true())
, implies(x, y) -> xor(and(x, y), xor(x, true()))
, or(x, y) -> xor(and(x, y), xor(x, y))
, =(x, y) -> xor(x, xor(y, true())) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(n^1))
No rule is usable, rules are removed from the input problem.
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(n^1)).
Strict DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y)
, =^#(x, y) -> c_4(x, y) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(n^1))
The weightgap principle applies (using the following constant
growth matrix-interpretation)
The following argument positions are usable:
none
TcT has computed the following constructor-restricted matrix
interpretation.
[not^#](x1) = [0]
[0]
[c_1](x1) = [0]
[0]
[implies^#](x1, x2) = [2 2] x1 + [0]
[0 0] [0]
[c_2](x1, x2, x3) = [0 0] x1 + [0 0] x3 + [0]
[1 0] [1 0] [0]
[or^#](x1, x2) = [2 1] x1 + [1 1] x2 + [0]
[0 0] [0 0] [0]
[c_3](x1, x2, x3, x4) = [0 1] x1 + [0 0] x2 + [1 0] x3 + [0
0] x4 + [0]
[1 1] [1 0] [1 1] [1
0] [0]
[=^#](x1, x2) = [1]
[0]
[c_4](x1, x2) = [0]
[0]
The order satisfies the following ordering constraints:
[not^#(x)] = [0]
[0]
>= [0]
[0]
= [c_1(x)]
[implies^#(x, y)] = [2 2] x + [0]
[0 0] [0]
? [0 0] x + [0]
[2 0] [0]
= [c_2(x, y, x)]
[or^#(x, y)] = [2 1] x + [1 1] y + [0]
[0 0] [0 0] [0]
? [1 1] x + [0 0] y + [0]
[2 2] [2 0] [0]
= [c_3(x, y, x, y)]
[=^#(x, y)] = [1]
[0]
> [0]
[0]
= [c_4(x, y)]
Further, it can be verified that all rules not oriented are covered by the weightgap condition.
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(n^1)).
Strict DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y) }
Weak DPs: { =^#(x, y) -> c_4(x, y) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(n^1))
We use the processor 'matrix interpretation of dimension 1' to
orient following rules strictly.
DPs:
{ 1: not^#(x) -> c_1(x)
, 2: implies^#(x, y) -> c_2(x, y, x)
, 4: =^#(x, y) -> c_4(x, y) }
Sub-proof:
----------
The following argument positions are usable:
none
TcT has computed the following constructor-based matrix
interpretation satisfying not(EDA).
[not^#](x1) = [7]
[c_1](x1) = [1]
[implies^#](x1, x2) = [7] x1 + [7] x2 + [7]
[c_2](x1, x2, x3) = [4] x2 + [1] x3 + [4]
[or^#](x1, x2) = [7] x1 + [7] x2 + [7]
[c_3](x1, x2, x3, x4) = [4] x1 + [4] x2 + [1] x3 + [1] x4 + [7]
[=^#](x1, x2) = [7] x1 + [7] x2 + [7]
[c_4](x1, x2) = [4] x2 + [5]
The order satisfies the following ordering constraints:
[not^#(x)] = [7]
> [1]
= [c_1(x)]
[implies^#(x, y)] = [7] x + [7] y + [7]
> [1] x + [4] y + [4]
= [c_2(x, y, x)]
[or^#(x, y)] = [7] x + [7] y + [7]
>= [5] x + [5] y + [7]
= [c_3(x, y, x, y)]
[=^#(x, y)] = [7] x + [7] y + [7]
> [4] y + [5]
= [c_4(x, y)]
The strictly oriented rules are moved into the weak component.
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(1)).
Strict DPs: { or^#(x, y) -> c_3(x, y, x, y) }
Weak DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, =^#(x, y) -> c_4(x, y) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(1))
We use the processor 'matrix interpretation of dimension 1' to
orient following rules strictly.
DPs:
{ 1: or^#(x, y) -> c_3(x, y, x, y)
, 2: not^#(x) -> c_1(x)
, 3: implies^#(x, y) -> c_2(x, y, x)
, 4: =^#(x, y) -> c_4(x, y) }
Sub-proof:
----------
The following argument positions are usable:
none
TcT has computed the following constructor-restricted matrix
interpretation. Note that the diagonal of the component-wise maxima
of interpretation-entries (of constructors) contains no more than 0
non-zero entries.
[not^#](x1) = [1] x1 + [7]
[c_1](x1) = [4]
[implies^#](x1, x2) = [7] x1 + [7] x2 + [7]
[c_2](x1, x2, x3) = [4] x1 + [1] x2 + [1] x3 + [3]
[or^#](x1, x2) = [7] x1 + [7] x2 + [7]
[c_3](x1, x2, x3, x4) = [1] x2 + [1] x3 + [2]
[=^#](x1, x2) = [7] x1 + [7]
[c_4](x1, x2) = [0]
The order satisfies the following ordering constraints:
[not^#(x)] = [1] x + [7]
> [4]
= [c_1(x)]
[implies^#(x, y)] = [7] x + [7] y + [7]
> [5] x + [1] y + [3]
= [c_2(x, y, x)]
[or^#(x, y)] = [7] x + [7] y + [7]
> [1] x + [1] y + [2]
= [c_3(x, y, x, y)]
[=^#(x, y)] = [7] x + [7]
> [0]
= [c_4(x, y)]
The strictly oriented rules are moved into the weak component.
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(1)).
Weak DPs:
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y)
, =^#(x, y) -> c_4(x, y) }
Obligation:
runtime complexity
Answer:
YES(O(1),O(1))
The following weak DPs constitute a sub-graph of the DG that is
closed under successors. The DPs are removed.
{ not^#(x) -> c_1(x)
, implies^#(x, y) -> c_2(x, y, x)
, or^#(x, y) -> c_3(x, y, x, y)
, =^#(x, y) -> c_4(x, y) }
We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(1)).
Rules: Empty
Obligation:
runtime complexity
Answer:
YES(O(1),O(1))
Empty rules are trivially bounded
Hurray, we answered YES(O(1),O(n^1))