details

property	value
status	complete
benchmark	list-sum-prod-bin-assoc.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n100.star.cs.uiowa.edu
space	CiME_04

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.230411052704 seconds
cpu usage	0.199460841
max memory	8032256.0

stage attributes

key	value
output-size	11257
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. !940 : [] --> o !plus : [o * o] --> o !times : [o * o] --> o 0 : [o] --> o 1 : [o] --> o cons : [o * o] --> o nil : [] --> o prod : [o] --> o sum : [o] --> o 0(!940) => !940 !plus(X, !940) => X !plus(!940, X) => X !plus(0(X), 0(Y)) => 0(!plus(X, Y)) !plus(0(X), 1(Y)) => 1(!plus(X, Y)) !plus(1(X), 0(Y)) => 1(!plus(X, Y)) !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(!940, X) => !940 !times(0(X), Y) => 0(!times(X, Y)) !times(1(X), Y) => !plus(0(!times(X, Y)), Y) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) sum(nil) => 0(!940) sum(cons(X, Y)) => !plus(X, sum(Y)) prod(nil) => 1(!940) prod(cons(X, Y)) => !times(X, prod(Y)) 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] !plus#(0(X), 0(Y)) =#> 0#(!plus(X, Y)) 1] !plus#(0(X), 0(Y)) =#> !plus#(X, Y) 2] !plus#(0(X), 1(Y)) =#> !plus#(X, Y) 3] !plus#(1(X), 0(Y)) =#> !plus#(X, Y) 4] !plus#(1(X), 1(Y)) =#> 0#(!plus(!plus(X, Y), 1(!940))) 5] !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940)) 6] !plus#(1(X), 1(Y)) =#> !plus#(X, Y) 7] !plus#(!plus(X, Y), Z) =#> !plus#(X, !plus(Y, Z)) 8] !plus#(!plus(X, Y), Z) =#> !plus#(Y, Z) 9] !times#(0(X), Y) =#> 0#(!times(X, Y)) 10] !times#(0(X), Y) =#> !times#(X, Y) 11] !times#(1(X), Y) =#> !plus#(0(!times(X, Y)), Y) 12] !times#(1(X), Y) =#> 0#(!times(X, Y)) 13] !times#(1(X), Y) =#> !times#(X, Y) 14] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z)) 15] !times#(!times(X, Y), Z) =#> !times#(Y, Z) 16] sum#(nil) =#> 0#(!940) 17] sum#(cons(X, Y)) =#> !plus#(X, sum(Y)) 18] sum#(cons(X, Y)) =#> sum#(Y) 19] prod#(cons(X, Y)) =#> !times#(X, prod(Y)) 20] prod#(cons(X, Y)) =#> prod#(Y) Rules R_0: 0(!940) => !940 !plus(X, !940) => X !plus(!940, X) => X !plus(0(X), 0(Y)) => 0(!plus(X, Y)) !plus(0(X), 1(Y)) => 1(!plus(X, Y)) !plus(1(X), 0(Y)) => 1(!plus(X, Y)) !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(!940, X) => !940 !times(0(X), Y) => 0(!times(X, Y)) !times(1(X), Y) => !plus(0(!times(X, Y)), Y) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) sum(nil) => 0(!940) sum(cons(X, Y)) => !plus(X, sum(Y)) prod(nil) => 1(!940) prod(cons(X, Y)) => !times(X, prod(Y)) 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 : * 1 : 0, 1, 2, 3, 4, 5, 6, 7, 8 * 2 : 0, 1, 2, 3, 4, 5, 6, 7, 8 * 3 : 0, 1, 2, 3, 4, 5, 6, 7, 8 * 4 : * 5 : 2, 4, 5, 6, 7, 8 * 6 : 0, 1, 2, 3, 4, 5, 6, 7, 8 * 7 : 0, 1, 2, 3, 4, 5, 6, 7, 8 * 8 : 0, 1, 2, 3, 4, 5, 6, 7, 8 popout

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

job log

popout

actions

all output return to TRS Stand 20472