3.23/1.57 YES 3.48/1.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.48/1.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.48/1.61 3.48/1.61 3.48/1.61 Termination w.r.t. Q of the given QTRS could be proven: 3.48/1.61 3.48/1.61 (0) QTRS 3.48/1.61 (1) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms] 3.48/1.61 (2) YES 3.48/1.61 3.48/1.61 3.48/1.61 ---------------------------------------- 3.48/1.61 3.48/1.61 (0) 3.48/1.61 Obligation: 3.48/1.61 Q restricted rewrite system: 3.48/1.61 The TRS R consists of the following rules: 3.48/1.61 3.48/1.61 f(f(x)) -> f(x) 3.48/1.61 f(s(x)) -> f(x) 3.48/1.61 g(s(0)) -> g(f(s(0))) 3.48/1.61 3.48/1.61 The set Q consists of the following terms: 3.48/1.61 3.48/1.61 f(f(x0)) 3.48/1.61 f(s(x0)) 3.48/1.61 g(s(0)) 3.48/1.61 3.48/1.61 3.48/1.61 ---------------------------------------- 3.48/1.61 3.48/1.61 (1) RFCMatchBoundsTRSProof (EQUIVALENT) 3.48/1.61 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 3.48/1.61 The following rules were used to construct the certificate: 3.48/1.61 3.48/1.61 f(f(x)) -> f(x) 3.48/1.61 f(s(x)) -> f(x) 3.48/1.61 g(s(0)) -> g(f(s(0))) 3.48/1.61 3.48/1.61 The certificate found is represented by the following graph. 3.48/1.61 The certificate consists of the following enumerated nodes: 3.48/1.61 1, 3, 4, 5, 6 3.48/1.61 3.48/1.61 Node 1 is start node and node 3 is final node. 3.48/1.61 3.48/1.61 Those nodes are connected through the following edges: 3.48/1.61 3.48/1.61 * 1 to 3 labelled f_1(0), f_1(1)* 1 to 4 labelled g_1(0)* 3 to 3 labelled #_1(0)* 4 to 5 labelled f_1(0)* 4 to 6 labelled f_1(1)* 5 to 6 labelled s_1(0)* 6 to 3 labelled 0(0) 3.48/1.61 3.48/1.61 3.48/1.61 ---------------------------------------- 3.48/1.61 3.48/1.61 (2) 3.48/1.61 YES 3.48/1.64 EOF