6.02/2.51	YES
6.25/2.52	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.25/2.52	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.25/2.52	
6.25/2.52	
6.25/2.52	Termination of the given ETRS could be proven:
6.25/2.52	
6.25/2.52	(0) ETRS
6.25/2.52	(1) RRRPoloETRSProof [EQUIVALENT, 349 ms]
6.25/2.52	(2) ETRS
6.25/2.52	(3) RRRPoloETRSProof [EQUIVALENT, 150 ms]
6.25/2.52	(4) ETRS
6.25/2.52	(5) RRRPoloETRSProof [EQUIVALENT, 102 ms]
6.25/2.52	(6) ETRS
6.25/2.52	(7) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
6.25/2.52	(8) EDP
6.25/2.52	(9) EDependencyGraphProof [EQUIVALENT, 0 ms]
6.25/2.52	(10) TRUE
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(0)
6.25/2.52	Obligation:
6.25/2.52	Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   app(cons(x, l), k) -> cons(x, app(l, k))
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	   plus(0, y) -> y
6.25/2.52	   plus(s(x), y) -> s(plus(x, y))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(1) RRRPoloETRSProof (EQUIVALENT)
6.25/2.52	The following E TRS is given: Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   app(cons(x, l), k) -> cons(x, app(l, k))
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	   plus(0, y) -> y
6.25/2.52	   plus(s(x), y) -> s(plus(x, y))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
6.25/2.52	
6.25/2.52	   app(cons(x, l), k) -> cons(x, app(l, k))
6.25/2.52	   plus(0, y) -> y
6.25/2.52	   plus(s(x), y) -> s(plus(x, y))
6.25/2.52	Used ordering:
6.25/2.52	Polynomial interpretation [POLO]:
6.25/2.52	
6.25/2.52	   POL(0) = 0
6.25/2.52	   POL(app(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2
6.25/2.52	   POL(cons(x_1, x_2)) = 1 + x_1 + x_1*x_2 + 2*x_2
6.25/2.52	   POL(nil) = 0
6.25/2.52	   POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2
6.25/2.52	   POL(s(x_1)) = 3 + 2*x_1
6.25/2.52	   POL(sum(x_1)) = x_1
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(2)
6.25/2.52	Obligation:
6.25/2.52	Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(3) RRRPoloETRSProof (EQUIVALENT)
6.25/2.52	The following E TRS is given: Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
6.25/2.52	
6.25/2.52	   sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l))
6.25/2.52	Used ordering:
6.25/2.52	Polynomial interpretation [POLO]:
6.25/2.52	
6.25/2.52	   POL(app(x_1, x_2)) = x_1 + x_2
6.25/2.52	   POL(cons(x_1, x_2)) = 3 + x_1 + 3*x_2
6.25/2.52	   POL(nil) = 0
6.25/2.52	   POL(plus(x_1, x_2)) = x_1 + x_2
6.25/2.52	   POL(sum(x_1)) = x_1
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(4)
6.25/2.52	Obligation:
6.25/2.52	Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(5) RRRPoloETRSProof (EQUIVALENT)
6.25/2.52	The following E TRS is given: Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
6.25/2.52	
6.25/2.52	   app(nil, k) -> k
6.25/2.52	   app(l, nil) -> l
6.25/2.52	Used ordering:
6.25/2.52	Polynomial interpretation [POLO]:
6.25/2.52	
6.25/2.52	   POL(app(x_1, x_2)) = 2 + x_1 + x_2
6.25/2.52	   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
6.25/2.52	   POL(nil) = 0
6.25/2.52	   POL(plus(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2
6.25/2.52	   POL(sum(x_1)) = x_1
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(6)
6.25/2.52	Obligation:
6.25/2.52	Equational rewrite system:
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(7) EquationalDependencyPairsProof (EQUIVALENT)
6.25/2.52	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
6.25/2.52	The TRS P consists of the following rules:
6.25/2.52	
6.25/2.52	   SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	   SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k)))
6.25/2.52	
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	E# is empty.
6.25/2.52	We have to consider all minimal (P,E#,R,E)-chains
6.25/2.52	
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(8)
6.25/2.52	Obligation:
6.25/2.52	The TRS P consists of the following rules:
6.25/2.52	
6.25/2.52	   SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	   SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k)))
6.25/2.52	
6.25/2.52	The TRS R consists of the following rules:
6.25/2.52	
6.25/2.52	   sum(cons(x, nil)) -> cons(x, nil)
6.25/2.52	   sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k)))))
6.25/2.52	
6.25/2.52	The set E consists of the following equations:
6.25/2.52	
6.25/2.52	   plus(x, y) == plus(y, x)
6.25/2.52	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.25/2.52	
6.25/2.52	E# is empty.
6.25/2.52	We have to consider all minimal (P,E#,R,E)-chains
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(9) EDependencyGraphProof (EQUIVALENT)
6.25/2.52	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 2 less nodes.
6.25/2.52	----------------------------------------
6.25/2.52	
6.25/2.52	(10)
6.25/2.52	TRUE
6.25/2.55	EOF