details

property	value
status	complete
benchmark	z06.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n036.star.cs.uiowa.edu
space	Zantema_05

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.103516817093 seconds
cpu usage	0.10001173
max memory	4083712.0

stage attributes

key	value
output-size	5564
starexec-result	YES

output

/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. a : [] --> o b : [] --> o f : [o * o] --> o f(a, f(b, X)) => f(a, f(a, f(a, X))) f(b, f(a, X)) => f(b, f(b, f(b, X))) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] f#(a, f(b, X)) =#> f#(a, f(a, f(a, X))) 1] f#(a, f(b, X)) =#> f#(a, f(a, X)) 2] f#(a, f(b, X)) =#> f#(a, X) 3] f#(b, f(a, X)) =#> f#(b, f(b, f(b, X))) 4] f#(b, f(a, X)) =#> f#(b, f(b, X)) 5] f#(b, f(a, X)) =#> f#(b, X) Rules R_0: f(a, f(b, X)) => f(a, f(a, f(a, X))) f(b, f(a, X)) => f(b, f(b, f(b, X))) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1, 2 * 1 : 0, 1, 2 * 2 : 0, 1, 2 * 3 : 3, 4, 5 * 4 : 3, 4, 5 * 5 : 3, 4, 5 This graph has the following strongly connected components: P_1: f#(a, f(b, X)) =#> f#(a, f(a, f(a, X))) f#(a, f(b, X)) =#> f#(a, f(a, X)) f#(a, f(b, X)) =#> f#(a, X) P_2: f#(b, f(a, X)) =#> f#(b, f(b, f(b, X))) f#(b, f(a, X)) =#> f#(b, f(b, X)) f#(b, f(a, X)) =#> f#(b, X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f) and (P_2, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: f#(b, f(a, X)) >? f#(b, f(b, f(b, X))) f#(b, f(a, X)) >? f#(b, f(b, X)) f#(b, f(a, X)) >? f#(b, X) f(a, f(b, X)) >= f(a, f(a, f(a, X))) f(b, f(a, X)) >= f(b, f(b, f(b, X))) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: This leaves the following ordering requirements: f#(b, f(a, X)) >= f#(b, f(b, f(b, X))) f#(b, f(a, X)) > f#(b, f(b, X)) f#(b, f(a, X)) >= f#(b, X) f(b, f(a, X)) >= f(b, f(b, f(b, X))) The following interpretation satisfies the requirements: a = 3 b = 0 f = \y0y1.y1 + 3y0 f# = \y0y1.2y1 Using this interpretation, the requirements translate to: [[f#(b, f(a, _x0))]] = 18 + 2x0 > 2x0 = [[f#(b, f(b, f(b, _x0)))]] [[f#(b, f(a, _x0))]] = 18 + 2x0 > 2x0 = [[f#(b, f(b, _x0))]] popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to TRS Stand 20472