4.98/2.80 NO 4.98/2.80 We consider the system theBenchmark. 4.98/2.80 4.98/2.80 Alphabet: 4.98/2.80 4.98/2.80 0 : [] --> b 4.98/2.80 cons : [d * e] --> e 4.98/2.80 f : [b * b * b] --> a 4.98/2.80 false : [] --> c 4.98/2.80 filter : [d -> c * e] --> e 4.98/2.80 filter2 : [c * d -> c * d * e] --> e 4.98/2.80 g : [b] --> b 4.98/2.80 map : [d -> d * e] --> e 4.98/2.80 nil : [] --> e 4.98/2.80 s : [b] --> b 4.98/2.80 true : [] --> c 4.98/2.80 4.98/2.80 Rules: 4.98/2.80 4.98/2.80 f(g(x), s(0), y) => f(g(s(0)), y, g(x)) 4.98/2.80 g(s(x)) => s(g(x)) 4.98/2.80 g(0) => 0 4.98/2.80 map(h, nil) => nil 4.98/2.80 map(h, cons(x, y)) => cons(h x, map(h, y)) 4.98/2.80 filter(h, nil) => nil 4.98/2.80 filter(h, cons(x, y)) => filter2(h x, h, x, y) 4.98/2.80 filter2(true, h, x, y) => cons(x, filter(h, y)) 4.98/2.80 filter2(false, h, x, y) => filter(h, y) 4.98/2.80 4.98/2.80 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 4.98/2.80 4.98/2.80 This system is non-terminating, as demonstrated by our external first-order non-termination checker: 4.98/2.80 4.98/2.80 || The following well-typed term is terminating: f(g(s(0)), g(s(0)), g(s(0))) 4.98/2.80 || 4.98/2.80 || proof of resources/system.trs 4.98/2.80 || # AProVE Commit ID: 500ec9b2e2a919720cb177ef26031cb0220e008e fuhs 20130603 4.98/2.80 || 4.98/2.80 || 4.98/2.80 || Termination w.r.t. Q of the given QTRS could be disproven: 4.98/2.80 || 4.98/2.80 || (0) QTRS 4.98/2.80 || (1) NonTerminationProof [EQUIVALENT, 0 ms] 4.98/2.80 || (2) NO 4.98/2.80 || 4.98/2.80 || 4.98/2.80 || ---------------------------------------- 4.98/2.80 || 4.98/2.80 || (0) 4.98/2.80 || Obligation: 4.98/2.80 || Q restricted rewrite system: 4.98/2.80 || The TRS R consists of the following rules: 4.98/2.80 || 4.98/2.80 || f(g(%X), s(0), %Y) -> f(g(s(0)), %Y, g(%X)) 4.98/2.80 || g(s(%X)) -> s(g(%X)) 4.98/2.80 || g(0) -> 0 4.98/2.80 || 4.98/2.80 || Q is empty. 4.98/2.80 || 4.98/2.80 || ---------------------------------------- 4.98/2.80 || 4.98/2.80 || (1) NonTerminationProof (EQUIVALENT) 4.98/2.80 || The following loops were found: 4.98/2.80 || 4.98/2.80 || ---------- Loop: ---------- 4.98/2.80 || 4.98/2.80 || f(g(s(0)), g(s(0)), g(s(0))) -> f(g(s(0)), s(g(0)), g(s(0))) with rule g(s(%X')) -> s(g(%X')) at position [1] and matcher [%X' / 0] 4.98/2.80 || 4.98/2.80 || f(g(s(0)), s(g(0)), g(s(0))) -> f(g(s(0)), s(0), g(s(0))) with rule g(0) -> 0 at position [1,0] and matcher [ ] 4.98/2.80 || 4.98/2.80 || f(g(s(0)), s(0), g(s(0))) -> f(g(s(0)), g(s(0)), g(s(0))) with rule f(g(%X), s(0), %Y) -> f(g(s(0)), %Y, g(%X)) at position [] and matcher [%X / s(0), %Y / g(s(0))] 4.98/2.80 || 4.98/2.80 || Now an instance of the first term with Matcher [ ] occurs in the last term at position []. 4.98/2.80 || 4.98/2.80 || Context: [] 4.98/2.80 || 4.98/2.80 || 4.98/2.80 || ---------------------------------------- 4.98/2.80 || 4.98/2.80 || (2) 4.98/2.80 || NO 4.98/2.80 || 4.98/2.80 EOF