/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


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


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


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 0 ms]
(2) QDP
(3) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
(4) QDP
(5) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms]
(6) YES


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

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

   a(f, a(g, a(f, x))) -> a(f, a(g, a(g, a(f, x))))
   a(g, a(f, a(g, x))) -> a(g, a(f, a(f, a(g, x))))

Q is empty.

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

(1) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

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

   A(f, a(g, a(f, x))) -> A(f, a(g, a(g, a(f, x))))
   A(f, a(g, a(f, x))) -> A(g, a(g, a(f, x)))
   A(g, a(f, a(g, x))) -> A(g, a(f, a(f, a(g, x))))
   A(g, a(f, a(g, x))) -> A(f, a(f, a(g, x)))

The TRS R consists of the following rules:

   a(f, a(g, a(f, x))) -> a(f, a(g, a(g, a(f, x))))
   a(g, a(f, a(g, x))) -> a(g, a(f, a(f, a(g, x))))

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

(3) UsableRulesReductionPairsProof (EQUIVALENT)
First, we A-transformed [FROCOS05] the QDP-Problem.
Then we obtain the following A-transformed DP problem.

The pairs P are: 

   f1(g(f(x))) -> f1(g(g(f(x))))
   f1(g(f(x))) -> g1(g(f(x)))
   g1(f(g(x))) -> g1(f(f(g(x))))
   g1(f(g(x))) -> f1(f(g(x)))

and the Q and R are:
Q restricted rewrite system:
The TRS R consists of the following rules:

   g(f(g(x))) -> g(f(f(g(x))))
   f(g(f(x))) -> f(g(g(f(x))))

Q is empty.

By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules 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:

   a(f, a(g, a(f, x))) -> a(f, a(g, a(g, a(f, x))))
   a(g, a(f, a(g, x))) -> a(g, a(f, a(f, a(g, x))))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(f(x_1)) = x_1
   POL(f1(x_1)) = x_1
   POL(g(x_1)) = x_1
   POL(g1(x_1)) = x_1


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

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

   f1(g(f(x))) -> f1(g(g(f(x))))
   f1(g(f(x))) -> g1(g(f(x)))
   g1(f(g(x))) -> g1(f(f(g(x))))
   g1(f(g(x))) -> f1(f(g(x)))

The TRS R consists of the following rules:

   g(f(g(x))) -> g(f(f(g(x))))
   f(g(f(x))) -> f(g(g(f(x))))

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

(5) RFCMatchBoundsDPProof (EQUIVALENT)
Finiteness of the DP problem can be shown by a matchbound of 2. 
As the DP problem is minimal we only have to initialize the certificate graph by the rules of P:

   f1(g(f(x))) -> f1(g(g(f(x))))
   f1(g(f(x))) -> g1(g(f(x)))
   g1(f(g(x))) -> g1(f(f(g(x))))
   g1(f(g(x))) -> f1(f(g(x)))

To find matches we regarded all rules of R and P:

   g(f(g(x))) -> g(f(f(g(x))))
   f(g(f(x))) -> f(g(g(f(x))))
   f1(g(f(x))) -> f1(g(g(f(x))))
   f1(g(f(x))) -> g1(g(f(x)))
   g1(f(g(x))) -> g1(f(f(g(x))))
   g1(f(g(x))) -> f1(f(g(x)))

The certificate found is represented by the following graph.
The certificate consists of the following enumerated nodes:
40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59

Node 40 is start node and node 41 is final node.

Those nodes are connected through the following edges:

* 40 to 42 labelled f1_1(0)* 40 to 43 labelled g1_1(0)* 40 to 45 labelled g1_1(0)* 40 to 46 labelled f1_1(0)* 41 to 41 labelled #_1(0)* 42 to 43 labelled g_1(0)* 43 to 44 labelled g_1(0)* 43 to 51 labelled g_1(1)* 44 to 41 labelled f_1(0)* 44 to 48 labelled f_1(1)* 45 to 46 labelled f_1(0)* 46 to 47 labelled f_1(0)* 46 to 48 labelled f_1(1)* 47 to 41 labelled g_1(0)* 47 to 51 labelled g_1(1)* 48 to 49 labelled g_1(1)* 49 to 50 labelled g_1(1)* 49 to 51 labelled g_1(1)* 49 to 54 labelled g_1(2)* 50 to 41 labelled f_1(1)* 50 to 48 labelled f_1(1)* 51 to 52 labelled f_1(1)* 52 to 53 labelled f_1(1)* 52 to 48 labelled f_1(1)* 52 to 57 labelled f_1(2)* 53 to 41 labelled g_1(1)* 53 to 51 labelled g_1(1)* 54 to 55 labelled f_1(2)* 55 to 56 labelled f_1(2)* 56 to 49 labelled g_1(2)* 57 to 58 labelled g_1(2)* 58 to 59 labelled g_1(2)* 59 to 52 labelled f_1(2)


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

(6)
YES