23.53/11.72	MAYBE
23.75/11.73	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
23.75/11.73	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
23.75/11.73	
23.75/11.73	
23.75/11.73	Quasi decreasingness of the given CTRS could not be shown:
23.75/11.73	
23.75/11.73	(0) CTRS
23.75/11.73	(1) CTRSToQTRSProof [SOUND, 0 ms]
23.75/11.73	(2) QTRS
23.75/11.73	(3) QTRSRRRProof [EQUIVALENT, 55 ms]
23.75/11.73	(4) QTRS
23.75/11.73	(5) AAECC Innermost [EQUIVALENT, 0 ms]
23.75/11.73	(6) QTRS
23.75/11.73	(7) DependencyPairsProof [EQUIVALENT, 0 ms]
23.75/11.73	(8) QDP
23.75/11.73	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
23.75/11.73	(10) AND
23.75/11.73	    (11) QDP
23.75/11.73	        (12) UsableRulesProof [EQUIVALENT, 0 ms]
23.75/11.73	        (13) QDP
23.75/11.73	        (14) QReductionProof [EQUIVALENT, 0 ms]
23.75/11.73	        (15) QDP
23.75/11.73	        (16) NonTerminationLoopProof [COMPLETE, 0 ms]
23.75/11.73	        (17) NO
23.75/11.73	    (18) QDP
23.75/11.73	        (19) MNOCProof [EQUIVALENT, 0 ms]
23.75/11.73	        (20) QDP
23.75/11.73	        (21) NonLoopProof [COMPLETE, 19 ms]
23.75/11.73	        (22) NO
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(0)
23.75/11.73	Obligation:
23.75/11.73	Conditional term rewrite system:
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The conditional TRS C consists of the following conditional rules:
23.75/11.73	
23.75/11.73	   a -> b <= a -> c, b -> c
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(1) CTRSToQTRSProof (SOUND)
23.75/11.73	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(2)
23.75/11.73	Obligation:
23.75/11.73	Q restricted rewrite system:
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   U1(c) -> U2(b)
23.75/11.73	   U2(c) -> b
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	Q is empty.
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(3) QTRSRRRProof (EQUIVALENT)
23.75/11.73	Used ordering:
23.75/11.73	Polynomial interpretation [POLO]:
23.75/11.73	
23.75/11.73	   POL(U1(x_1)) = x_1
23.75/11.73	   POL(U2(x_1)) = 2*x_1
23.75/11.73	   POL(a) = 0
23.75/11.73	   POL(b) = 0
23.75/11.73	   POL(c) = 2
23.75/11.73	   POL(f(x_1)) = 2*x_1
23.75/11.73	   POL(g(x_1)) = 2*x_1
23.75/11.73	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
23.75/11.73	
23.75/11.73	   U1(c) -> U2(b)
23.75/11.73	   U2(c) -> b
23.75/11.73	
23.75/11.73	
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(4)
23.75/11.73	Obligation:
23.75/11.73	Q restricted rewrite system:
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	Q is empty.
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(5) AAECC Innermost (EQUIVALENT)
23.75/11.73	We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
23.75/11.73	   a -> U1(a)
23.75/11.73	
23.75/11.73	The TRS R 2 is 
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The signature Sigma is {f_1, g_1}
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(6)
23.75/11.73	Obligation:
23.75/11.73	Q restricted rewrite system:
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The set Q consists of the following terms:
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(7) DependencyPairsProof (EQUIVALENT)
23.75/11.73	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(8)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   A -> A
23.75/11.73	   F(x) -> G(a)
23.75/11.73	   F(x) -> A
23.75/11.73	   G(x) -> F(x)
23.75/11.73	
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The set Q consists of the following terms:
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	We have to consider all minimal (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(9) DependencyGraphProof (EQUIVALENT)
23.75/11.73	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(10)
23.75/11.73	Complex Obligation (AND)
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(11)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   A -> A
23.75/11.73	
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The set Q consists of the following terms:
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	We have to consider all minimal (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(12) UsableRulesProof (EQUIVALENT)
23.75/11.73	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(13)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   A -> A
23.75/11.73	
23.75/11.73	R is empty.
23.75/11.73	The set Q consists of the following terms:
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	We have to consider all minimal (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(14) QReductionProof (EQUIVALENT)
23.75/11.73	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(15)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   A -> A
23.75/11.73	
23.75/11.73	R is empty.
23.75/11.73	Q is empty.
23.75/11.73	We have to consider all minimal (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(16) NonTerminationLoopProof (COMPLETE)
23.75/11.73	We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
23.75/11.73	Found a loop by semiunifying a rule from P directly.
23.75/11.73	
23.75/11.73	s = A evaluates to  t =A
23.75/11.73	
23.75/11.73	Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
23.75/11.73	* Matcher: [ ]
23.75/11.73	* Semiunifier: [ ]
23.75/11.73	
23.75/11.73	--------------------------------------------------------------------------------
23.75/11.73	Rewriting sequence
23.75/11.73	
23.75/11.73	The DP semiunifies directly so there is only one rewrite step from A to A.
23.75/11.73	
23.75/11.73	
23.75/11.73	
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(17)
23.75/11.73	NO
23.75/11.73	
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(18)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   F(x) -> G(a)
23.75/11.73	   G(x) -> F(x)
23.75/11.73	
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	The set Q consists of the following terms:
23.75/11.73	
23.75/11.73	   a
23.75/11.73	   f(x0)
23.75/11.73	   g(x0)
23.75/11.73	
23.75/11.73	We have to consider all minimal (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(19) MNOCProof (EQUIVALENT)
23.75/11.73	We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(20)
23.75/11.73	Obligation:
23.75/11.73	Q DP problem:
23.75/11.73	The TRS P consists of the following rules:
23.75/11.73	
23.75/11.73	   F(x) -> G(a)
23.75/11.73	   G(x) -> F(x)
23.75/11.73	
23.75/11.73	The TRS R consists of the following rules:
23.75/11.73	
23.75/11.73	   a -> U1(a)
23.75/11.73	   f(x) -> g(a)
23.75/11.73	   g(x) -> f(x)
23.75/11.73	
23.75/11.73	Q is empty.
23.75/11.73	We have to consider all (P,Q,R)-chains.
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(21) NonLoopProof (COMPLETE)
23.75/11.73	By Theorem 8 [NONLOOP] we deduce infiniteness of the QDP.
23.75/11.73	We apply the theorem with m = 1, b = 0, 
23.75/11.73	σ' = [ ], and μ' = [x0 / a] on the rule
23.75/11.73	G(a)[ ]^n[ ] -> G(a)[ ]^n[x0 / a]
23.75/11.73	This rule is correct for the QDP as the following derivation shows:
23.75/11.73	
23.75/11.73	G(a)[ ]^n[ ] -> G(a)[ ]^n[x0 / a]
23.75/11.73	    by Equivalency by Simplifying Mu with mu1: [x0 / a] mu2: [ ]
23.75/11.73	    intermediate steps: Instantiate mu
23.75/11.73	    G(x0)[ ]^n[ ] -> G(a)[ ]^n[ ]
23.75/11.73	        by Narrowing at position: []
23.75/11.73	        intermediate steps: Instantiation
23.75/11.73	        G(x)[ ]^n[ ] -> F(x)[ ]^n[ ]
23.75/11.73	            by Rule from TRS P
23.75/11.73	
23.75/11.73	        intermediate steps: Instantiation - Instantiation
23.75/11.73	        F(x)[ ]^n[ ] -> G(a)[ ]^n[ ]
23.75/11.73	            by Rule from TRS P
23.75/11.73	----------------------------------------
23.75/11.73	
23.75/11.73	(22)
23.75/11.73	NO
23.75/11.77	EOF