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


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


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


Quasi decreasingness of the given CTRS could not be shown:

(0) CTRS
(1) CTRSToQTRSProof [SOUND, 0 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 0 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) QDP
(7) NonLoopProof [COMPLETE, 486 ms]
(8) NO


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

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

   a -> h(b)
   a -> h(c)

The conditional TRS C consists of the following conditional rules:

   f(x) -> y <= a -> h(y)
   g(x, b) -> g(f(c), x) <= f(b) -> x, x -> c


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

(1) CTRSToQTRSProof (SOUND)
The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
----------------------------------------

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

   f(x) -> U1(a)
   U1(h(y)) -> y
   g(x, b) -> U2(f(b), x)
   U2(x, x) -> U3(x, x)
   U3(c, x) -> g(f(c), x)
   a -> h(b)
   a -> h(c)

Q is empty.

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

(3) DependencyPairsProof (EQUIVALENT)
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:

   F(x) -> U1^1(a)
   F(x) -> A
   G(x, b) -> U2^1(f(b), x)
   G(x, b) -> F(b)
   U2^1(x, x) -> U3^1(x, x)
   U3^1(c, x) -> G(f(c), x)
   U3^1(c, x) -> F(c)

The TRS R consists of the following rules:

   f(x) -> U1(a)
   U1(h(y)) -> y
   g(x, b) -> U2(f(b), x)
   U2(x, x) -> U3(x, x)
   U3(c, x) -> g(f(c), x)
   a -> h(b)
   a -> h(c)

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

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes.
----------------------------------------

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

   G(x, b) -> U2^1(f(b), x)
   U2^1(x, x) -> U3^1(x, x)
   U3^1(c, x) -> G(f(c), x)

The TRS R consists of the following rules:

   f(x) -> U1(a)
   U1(h(y)) -> y
   g(x, b) -> U2(f(b), x)
   U2(x, x) -> U3(x, x)
   U3(c, x) -> g(f(c), x)
   a -> h(b)
   a -> h(c)

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

(7) NonLoopProof (COMPLETE)
By Theorem 8 [NONLOOP] we deduce infiniteness of the QDP.
We apply the theorem with m = 1, b = 0, 
σ' = [ ], and μ' = [ ] on the rule
G(U1(a), b)[ ]^n[ ] -> G(U1(a), b)[ ]^n[ ]
This rule is correct for the QDP as the following derivation shows:

G(U1(a), b)[ ]^n[ ] -> G(U1(a), b)[ ]^n[ ]
    by Narrowing at position: [0]
    G(U1(a), b)[ ]^n[ ] -> G(f(c), b)[ ]^n[ ]
        by Narrowing at position: []
        G(U1(a), b)[ ]^n[ ] -> U3^1(c, b)[ ]^n[ ]
            by Rewrite t with the rewrite sequence <Pos,Rule>: [([0],U1(h(y)) -> y), ([1,0],a -> h(b)), ([1],U1(h(y)) -> y)]
            G(U1(a), b)[ ]^n[ ] -> U3^1(U1(h(c)), U1(a))[ ]^n[ ]
                by Narrowing at position: [0,0]
                G(U1(a), b)[ ]^n[ ] -> U3^1(U1(a), U1(a))[ ]^n[ ]
                    by Narrowing at position: []
                    intermediate steps: Instantiation
                    G(x0, b)[ ]^n[ ] -> U2^1(U1(a), x0)[ ]^n[ ]
                        by Narrowing at position: [0]
                        intermediate steps: Instantiation
                        G(x, b)[ ]^n[ ] -> U2^1(f(b), x)[ ]^n[ ]
                            by Rule from TRS P

                        intermediate steps: Instantiation - Instantiation
                        f(x)[ ]^n[ ] -> U1(a)[ ]^n[ ]
                            by Rule from TRS R

                    intermediate steps: Instantiation - Instantiation
                    U2^1(x, x)[ ]^n[ ] -> U3^1(x, x)[ ]^n[ ]
                        by Rule from TRS P

                a[ ]^n[ ] -> h(c)[ ]^n[ ]
                    by Rule from TRS R

        intermediate steps: Instantiation - Instantiation
        U3^1(c, x)[ ]^n[ ] -> G(f(c), x)[ ]^n[ ]
            by Rule from TRS P

    intermediate steps: Instantiation - Instantiation
    f(x)[ ]^n[ ] -> U1(a)[ ]^n[ ]
        by Rule from TRS R
----------------------------------------

(8)
NO