YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ETRS could be proven:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(2) EDP
(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
(4) EDP
(5) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
(6) EDP
(7) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms]
(8) QDP
(9) MNOCProof [EQUIVALENT, 0 ms]
(10) QDP
(11) MRRProof [EQUIVALENT, 0 ms]
(12) QDP
(13) DependencyGraphProof [EQUIVALENT, 0 ms]
(14) TRUE


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

(0)
Obligation:
Equational rewrite system:
The TRS R consists of the following rules:

   p(s(x)) -> x
   fac(0) -> s(0)
   fac(s(x)) -> times(s(x), fac(p(s(x))))

The set E consists of the following equations:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))


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

(1) EquationalDependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
The TRS P consists of the following rules:

   FAC(s(x)) -> FAC(p(s(x)))
   FAC(s(x)) -> P(s(x))

The TRS R consists of the following rules:

   p(s(x)) -> x
   fac(0) -> s(0)
   fac(s(x)) -> times(s(x), fac(p(s(x))))

The set E consists of the following equations:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))

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

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

(2)
Obligation:
The TRS P consists of the following rules:

   FAC(s(x)) -> FAC(p(s(x)))
   FAC(s(x)) -> P(s(x))

The TRS R consists of the following rules:

   p(s(x)) -> x
   fac(0) -> s(0)
   fac(s(x)) -> times(s(x), fac(p(s(x))))

The set E consists of the following equations:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))

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

(3) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node.
----------------------------------------

(4)
Obligation:
The TRS P consists of the following rules:

   FAC(s(x)) -> FAC(p(s(x)))

The TRS R consists of the following rules:

   p(s(x)) -> x
   fac(0) -> s(0)
   fac(s(x)) -> times(s(x), fac(p(s(x))))

The set E consists of the following equations:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))

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

(5) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

No dependency pairs are removed.

The following rules are removed from R:

   fac(0) -> s(0)
   fac(s(x)) -> times(s(x), fac(p(s(x))))
The following equations are removed from E:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(FAC(x_1)) = x_1
   POL(p(x_1)) = x_1
   POL(s(x_1)) = x_1


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

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

   FAC(s(x)) -> FAC(p(s(x)))

The TRS R consists of the following rules:

   p(s(x)) -> x

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

(7) EDPProblemToQDPProblemProof (EQUIVALENT)
The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem.
----------------------------------------

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

   FAC(s(x)) -> FAC(p(s(x)))

The TRS R consists of the following rules:

   p(s(x)) -> x

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

(9) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
----------------------------------------

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

   FAC(s(x)) -> FAC(p(s(x)))

The TRS R consists of the following rules:

   p(s(x)) -> x

The set Q consists of the following terms:

   p(s(x0))

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

(11) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.


Strictly oriented rules of the TRS R:

   p(s(x)) -> x

Used ordering: Polynomial interpretation [POLO]:

   POL(FAC(x_1)) = 2*x_1
   POL(p(x_1)) = x_1
   POL(s(x_1)) = 2 + x_1


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

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

   FAC(s(x)) -> FAC(p(s(x)))

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

   p(s(x0))

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

(13) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(14)
TRUE