42.18/11.65	YES
50.96/13.91	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
50.96/13.91	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
50.96/13.91	
50.96/13.91	
50.96/13.91	Termination w.r.t. Q of the given QTRS could be proven:
50.96/13.91	
50.96/13.91	(0) QTRS
50.96/13.91	(1) QTRSRRRProof [EQUIVALENT, 76 ms]
50.96/13.91	(2) QTRS
50.96/13.91	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
50.96/13.91	(4) QDP
50.96/13.91	(5) DependencyGraphProof [EQUIVALENT, 2 ms]
50.96/13.91	(6) AND
50.96/13.91	    (7) QDP
50.96/13.91	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (9) QDP
50.96/13.91	        (10) MNOCProof [EQUIVALENT, 0 ms]
50.96/13.91	        (11) QDP
50.96/13.91	        (12) MRRProof [EQUIVALENT, 32 ms]
50.96/13.91	        (13) QDP
50.96/13.91	        (14) MRRProof [EQUIVALENT, 0 ms]
50.96/13.91	        (15) QDP
50.96/13.91	        (16) PisEmptyProof [EQUIVALENT, 0 ms]
50.96/13.91	        (17) YES
50.96/13.91	    (18) QDP
50.96/13.91	        (19) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (20) QDP
50.96/13.91	        (21) MNOCProof [EQUIVALENT, 0 ms]
50.96/13.91	        (22) QDP
50.96/13.91	        (23) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (24) QDP
50.96/13.91	        (25) QDPOrderProof [EQUIVALENT, 0 ms]
50.96/13.91	        (26) QDP
50.96/13.91	        (27) PisEmptyProof [EQUIVALENT, 0 ms]
50.96/13.91	        (28) YES
50.96/13.91	    (29) QDP
50.96/13.91	        (30) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (31) QDP
50.96/13.91	        (32) QDPOrderProof [EQUIVALENT, 235 ms]
50.96/13.91	        (33) QDP
50.96/13.91	        (34) QDPOrderProof [EQUIVALENT, 0 ms]
50.96/13.91	        (35) QDP
50.96/13.91	        (36) QDPOrderProof [EQUIVALENT, 0 ms]
50.96/13.91	        (37) QDP
50.96/13.91	        (38) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (39) QDP
50.96/13.91	        (40) MRRProof [EQUIVALENT, 4 ms]
50.96/13.91	        (41) QDP
50.96/13.91	        (42) UsableRulesProof [EQUIVALENT, 0 ms]
50.96/13.91	        (43) QDP
50.96/13.91	        (44) QDPSizeChangeProof [EQUIVALENT, 0 ms]
50.96/13.91	        (45) YES
50.96/13.91	
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(0)
50.96/13.91	Obligation:
50.96/13.91	Q restricted rewrite system:
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   a(b(x1)) -> b(c(a(x1)))
50.96/13.91	   b(c(x1)) -> c(b(b(x1)))
50.96/13.91	   a(c(x1)) -> c(a(b(x1)))
50.96/13.91	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.91	   d(a(x1)) -> d(d(c(x1)))
50.96/13.91	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	   e(x1) -> a(x1)
50.96/13.91	   b(d(x1)) -> d(d(x1))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(1) QTRSRRRProof (EQUIVALENT)
50.96/13.91	Used ordering:
50.96/13.91	Polynomial interpretation [POLO]:
50.96/13.91	
50.96/13.91	   POL(a(x_1)) = x_1
50.96/13.91	   POL(b(x_1)) = x_1
50.96/13.91	   POL(c(x_1)) = x_1
50.96/13.91	   POL(d(x_1)) = x_1
50.96/13.91	   POL(e(x_1)) = 1 + x_1
50.96/13.91	   POL(f(x_1)) = x_1
50.96/13.91	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
50.96/13.91	
50.96/13.91	   e(x1) -> a(x1)
50.96/13.91	
50.96/13.91	
50.96/13.91	
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(2)
50.96/13.91	Obligation:
50.96/13.91	Q restricted rewrite system:
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   a(b(x1)) -> b(c(a(x1)))
50.96/13.91	   b(c(x1)) -> c(b(b(x1)))
50.96/13.91	   a(c(x1)) -> c(a(b(x1)))
50.96/13.91	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.91	   d(a(x1)) -> d(d(c(x1)))
50.96/13.91	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	   b(d(x1)) -> d(d(x1))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(3) DependencyPairsProof (EQUIVALENT)
50.96/13.91	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(4)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   A(b(x1)) -> B(c(a(x1)))
50.96/13.91	   A(b(x1)) -> A(x1)
50.96/13.91	   B(c(x1)) -> B(b(x1))
50.96/13.91	   B(c(x1)) -> B(x1)
50.96/13.91	   A(c(x1)) -> A(b(x1))
50.96/13.91	   A(c(x1)) -> B(x1)
50.96/13.91	   A(a(x1)) -> A(d(d(d(x1))))
50.96/13.91	   A(a(x1)) -> D(d(d(x1)))
50.96/13.91	   A(a(x1)) -> D(d(x1))
50.96/13.91	   A(a(x1)) -> D(x1)
50.96/13.91	   D(a(x1)) -> D(d(c(x1)))
50.96/13.91	   D(a(x1)) -> D(c(x1))
50.96/13.91	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.91	   A(d(d(c(x1)))) -> A(a(d(x1)))
50.96/13.91	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.91	   A(d(d(c(x1)))) -> D(x1)
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	   E(e(f(f(x1)))) -> E(x1)
50.96/13.91	   B(d(x1)) -> D(d(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   a(b(x1)) -> b(c(a(x1)))
50.96/13.91	   b(c(x1)) -> c(b(b(x1)))
50.96/13.91	   a(c(x1)) -> c(a(b(x1)))
50.96/13.91	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.91	   d(a(x1)) -> d(d(c(x1)))
50.96/13.91	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	   b(d(x1)) -> d(d(x1))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(5) DependencyGraphProof (EQUIVALENT)
50.96/13.91	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 9 less nodes.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(6)
50.96/13.91	Complex Obligation (AND)
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(7)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(x1)
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   a(b(x1)) -> b(c(a(x1)))
50.96/13.91	   b(c(x1)) -> c(b(b(x1)))
50.96/13.91	   a(c(x1)) -> c(a(b(x1)))
50.96/13.91	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.91	   d(a(x1)) -> d(d(c(x1)))
50.96/13.91	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	   b(d(x1)) -> d(d(x1))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(8) UsableRulesProof (EQUIVALENT)
50.96/13.91	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(9)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(x1)
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(10) MNOCProof (EQUIVALENT)
50.96/13.91	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(11)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(x1)
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	
50.96/13.91	The set Q consists of the following terms:
50.96/13.91	
50.96/13.91	   e(e(f(f(x0))))
50.96/13.91	
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(12) MRRProof (EQUIVALENT)
50.96/13.91	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.
50.96/13.91	
50.96/13.91	Strictly oriented dependency pairs:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(x1)
50.96/13.91	
50.96/13.91	
50.96/13.91	Used ordering: Polynomial interpretation [POLO]:
50.96/13.91	
50.96/13.91	   POL(E(x_1)) = 2*x_1
50.96/13.91	   POL(e(x_1)) = 1 + x_1
50.96/13.91	   POL(f(x_1)) = x_1
50.96/13.91	
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(13)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	
50.96/13.91	The set Q consists of the following terms:
50.96/13.91	
50.96/13.91	   e(e(f(f(x0))))
50.96/13.91	
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(14) MRRProof (EQUIVALENT)
50.96/13.91	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.
50.96/13.91	
50.96/13.91	Strictly oriented dependency pairs:
50.96/13.91	
50.96/13.91	   E(e(f(f(x1)))) -> E(e(x1))
50.96/13.91	
50.96/13.91	Strictly oriented rules of the TRS R:
50.96/13.91	
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	
50.96/13.91	Used ordering: Polynomial interpretation [POLO]:
50.96/13.91	
50.96/13.91	   POL(E(x_1)) = 2*x_1
50.96/13.91	   POL(e(x_1)) = 3*x_1
50.96/13.91	   POL(f(x_1)) = 3 + x_1
50.96/13.91	
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(15)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	P is empty.
50.96/13.91	R is empty.
50.96/13.91	The set Q consists of the following terms:
50.96/13.91	
50.96/13.91	   e(e(f(f(x0))))
50.96/13.91	
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(16) PisEmptyProof (EQUIVALENT)
50.96/13.91	The TRS P is empty. Hence, there is no (P,Q,R) chain.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(17)
50.96/13.91	YES
50.96/13.91	
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(18)
50.96/13.91	Obligation:
50.96/13.91	Q DP problem:
50.96/13.91	The TRS P consists of the following rules:
50.96/13.91	
50.96/13.91	   B(c(x1)) -> B(x1)
50.96/13.91	   B(c(x1)) -> B(b(x1))
50.96/13.91	
50.96/13.91	The TRS R consists of the following rules:
50.96/13.91	
50.96/13.91	   a(b(x1)) -> b(c(a(x1)))
50.96/13.91	   b(c(x1)) -> c(b(b(x1)))
50.96/13.91	   a(c(x1)) -> c(a(b(x1)))
50.96/13.91	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.91	   d(a(x1)) -> d(d(c(x1)))
50.96/13.91	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.91	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.91	   b(d(x1)) -> d(d(x1))
50.96/13.91	
50.96/13.91	Q is empty.
50.96/13.91	We have to consider all minimal (P,Q,R)-chains.
50.96/13.91	----------------------------------------
50.96/13.91	
50.96/13.91	(19) UsableRulesProof (EQUIVALENT)
50.96/13.91	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(20)
50.96/13.92	Obligation:
50.96/13.92	Q DP problem:
50.96/13.92	The TRS P consists of the following rules:
50.96/13.92	
50.96/13.92	   B(c(x1)) -> B(x1)
50.96/13.92	   B(c(x1)) -> B(b(x1))
50.96/13.92	
50.96/13.92	The TRS R consists of the following rules:
50.96/13.92	
50.96/13.92	   b(c(x1)) -> c(b(b(x1)))
50.96/13.92	   b(d(x1)) -> d(d(x1))
50.96/13.92	   d(a(x1)) -> d(d(c(x1)))
50.96/13.92	
50.96/13.92	Q is empty.
50.96/13.92	We have to consider all minimal (P,Q,R)-chains.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(21) MNOCProof (EQUIVALENT)
50.96/13.92	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(22)
50.96/13.92	Obligation:
50.96/13.92	Q DP problem:
50.96/13.92	The TRS P consists of the following rules:
50.96/13.92	
50.96/13.92	   B(c(x1)) -> B(x1)
50.96/13.92	   B(c(x1)) -> B(b(x1))
50.96/13.92	
50.96/13.92	The TRS R consists of the following rules:
50.96/13.92	
50.96/13.92	   b(c(x1)) -> c(b(b(x1)))
50.96/13.92	   b(d(x1)) -> d(d(x1))
50.96/13.92	   d(a(x1)) -> d(d(c(x1)))
50.96/13.92	
50.96/13.92	The set Q consists of the following terms:
50.96/13.92	
50.96/13.92	   b(c(x0))
50.96/13.92	   b(d(x0))
50.96/13.92	   d(a(x0))
50.96/13.92	
50.96/13.92	We have to consider all minimal (P,Q,R)-chains.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(23) UsableRulesProof (EQUIVALENT)
50.96/13.92	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.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(24)
50.96/13.92	Obligation:
50.96/13.92	Q DP problem:
50.96/13.92	The TRS P consists of the following rules:
50.96/13.92	
50.96/13.92	   B(c(x1)) -> B(x1)
50.96/13.92	   B(c(x1)) -> B(b(x1))
50.96/13.92	
50.96/13.92	The TRS R consists of the following rules:
50.96/13.92	
50.96/13.92	   b(c(x1)) -> c(b(b(x1)))
50.96/13.92	   b(d(x1)) -> d(d(x1))
50.96/13.92	
50.96/13.92	The set Q consists of the following terms:
50.96/13.92	
50.96/13.92	   b(c(x0))
50.96/13.92	   b(d(x0))
50.96/13.92	   d(a(x0))
50.96/13.92	
50.96/13.92	We have to consider all minimal (P,Q,R)-chains.
50.96/13.92	----------------------------------------
50.96/13.92	
50.96/13.92	(25) QDPOrderProof (EQUIVALENT)
50.96/13.92	We use the reduction pair processor [LPAR04,JAR06].
50.96/13.92	
50.96/13.92	
50.96/13.92	The following pairs can be oriented strictly and are deleted.
50.96/13.92	
50.96/13.92	   B(c(x1)) -> B(x1)
50.96/13.92	   B(c(x1)) -> B(b(x1))
50.96/13.92	The remaining pairs can at least be oriented weakly.
50.96/13.92	Used ordering:  Polynomial interpretation [POLO]:
50.96/13.92	
50.96/13.92	   POL(B(x_1)) = x_1
50.96/13.92	   POL(b(x_1)) = x_1
50.96/13.92	   POL(c(x_1)) = 1 + x_1
50.96/13.93	   POL(d(x_1)) = 1
50.96/13.93	
50.96/13.93	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
50.96/13.93	
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(26)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	P is empty.
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	The set Q consists of the following terms:
50.96/13.93	
50.96/13.93	   b(c(x0))
50.96/13.93	   b(d(x0))
50.96/13.93	   d(a(x0))
50.96/13.93	
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(27) PisEmptyProof (EQUIVALENT)
50.96/13.93	The TRS P is empty. Hence, there is no (P,Q,R) chain.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(28)
50.96/13.93	YES
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(29)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(a(x1)) -> A(d(d(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(a(d(x1)))
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	   e(e(f(f(x1)))) -> f(f(f(e(e(x1)))))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(30) UsableRulesProof (EQUIVALENT)
50.96/13.93	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(31)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(a(x1)) -> A(d(d(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(a(d(x1)))
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(32) QDPOrderProof (EQUIVALENT)
50.96/13.93	We use the reduction pair processor [LPAR04,JAR06].
50.96/13.93	
50.96/13.93	
50.96/13.93	The following pairs can be oriented strictly and are deleted.
50.96/13.93	
50.96/13.93	   A(d(d(c(x1)))) -> A(a(d(x1)))
50.96/13.93	The remaining pairs can at least be oriented weakly.
50.96/13.93	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(A(x_1)) =  	[[0A]] 	 +  	[[0A, -I, -I]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(c(x_1)) =  	[[1A], [0A], [1A]] 	 +  	[[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(b(x_1)) =  	[[1A], [0A], [1A]] 	 +  	[[0A, 0A, 0A], [0A, -I, 0A], [0A, 0A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(a(x_1)) =  	[[0A], [1A], [-I]] 	 +  	[[-I, -I, 0A], [0A, 0A, 0A], [0A, -I, -I]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(d(x_1)) =  	[[0A], [0A], [0A]] 	 +  	[[-I, 0A, 0A], [-I, -I, 0A], [-I, -I, -I]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	
50.96/13.93	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
50.96/13.93	
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(33)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(a(x1)) -> A(d(d(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(34) QDPOrderProof (EQUIVALENT)
50.96/13.93	We use the reduction pair processor [LPAR04,JAR06].
50.96/13.93	
50.96/13.93	
50.96/13.93	The following pairs can be oriented strictly and are deleted.
50.96/13.93	
50.96/13.93	   A(a(x1)) -> A(d(d(d(x1))))
50.96/13.93	The remaining pairs can at least be oriented weakly.
50.96/13.93	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(A(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(c(x_1)) =  	[[1A], [0A], [1A]] 	 +  	[[0A, 1A, -I], [-I, 0A, -I], [-I, 0A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(b(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, -I], [-I, 0A, -I], [0A, 1A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(a(x_1)) =  	[[1A], [0A], [1A]] 	 +  	[[-I, 0A, -I], [-I, -I, -I], [0A, 0A, 0A]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	   <<<
50.96/13.93	 POL(d(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, 0A, 0A], [-I, -I, 0A], [-I, -I, -I]] 	* 	x_1
50.96/13.93	>>>
50.96/13.93	
50.96/13.93	
50.96/13.93	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
50.96/13.93	
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(35)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(36) QDPOrderProof (EQUIVALENT)
50.96/13.93	We use the reduction pair processor [LPAR04,JAR06].
50.96/13.93	
50.96/13.93	
50.96/13.93	The following pairs can be oriented strictly and are deleted.
50.96/13.93	
50.96/13.93	   A(d(d(c(x1)))) -> A(a(a(d(x1))))
50.96/13.93	The remaining pairs can at least be oriented weakly.
50.96/13.93	Used ordering:  Polynomial interpretation [POLO]:
50.96/13.93	
50.96/13.93	   POL(A(x_1)) = x_1
50.96/13.93	   POL(a(x_1)) = 0
50.96/13.93	   POL(b(x_1)) = x_1
50.96/13.93	   POL(c(x_1)) = x_1
50.96/13.93	   POL(d(x_1)) = 1
50.96/13.93	
50.96/13.93	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
50.96/13.93	
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(37)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   a(b(x1)) -> b(c(a(x1)))
50.96/13.93	   a(c(x1)) -> c(a(b(x1)))
50.96/13.93	   a(d(d(c(x1)))) -> a(a(a(d(x1))))
50.96/13.93	   a(a(x1)) -> a(d(d(d(x1))))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(38) UsableRulesProof (EQUIVALENT)
50.96/13.93	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(39)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(40) MRRProof (EQUIVALENT)
50.96/13.93	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.
50.96/13.93	
50.96/13.93	Strictly oriented dependency pairs:
50.96/13.93	
50.96/13.93	   A(c(x1)) -> A(b(x1))
50.96/13.93	   A(d(d(c(x1)))) -> A(d(x1))
50.96/13.93	
50.96/13.93	
50.96/13.93	Used ordering: Polynomial interpretation [POLO]:
50.96/13.93	
50.96/13.93	   POL(A(x_1)) = 3*x_1
50.96/13.93	   POL(a(x_1)) = 1 + 3*x_1
50.96/13.93	   POL(b(x_1)) = x_1
50.96/13.93	   POL(c(x_1)) = 1 + 2*x_1
50.96/13.93	   POL(d(x_1)) = x_1
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(41)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	
50.96/13.93	The TRS R consists of the following rules:
50.96/13.93	
50.96/13.93	   d(a(x1)) -> d(d(c(x1)))
50.96/13.93	   b(c(x1)) -> c(b(b(x1)))
50.96/13.93	   b(d(x1)) -> d(d(x1))
50.96/13.93	
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(42) UsableRulesProof (EQUIVALENT)
50.96/13.93	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(43)
50.96/13.93	Obligation:
50.96/13.93	Q DP problem:
50.96/13.93	The TRS P consists of the following rules:
50.96/13.93	
50.96/13.93	   A(b(x1)) -> A(x1)
50.96/13.93	
50.96/13.93	R is empty.
50.96/13.93	Q is empty.
50.96/13.93	We have to consider all minimal (P,Q,R)-chains.
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(44) QDPSizeChangeProof (EQUIVALENT)
50.96/13.93	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
50.96/13.93	
50.96/13.93	From the DPs we obtained the following set of size-change graphs:
50.96/13.93	*A(b(x1)) -> A(x1)
50.96/13.93	The graph contains the following edges 1 > 1
50.96/13.93	
50.96/13.93	
50.96/13.93	----------------------------------------
50.96/13.93	
50.96/13.93	(45)
50.96/13.93	YES
51.46/14.02	EOF