Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381710427
details
property
value
status
complete
benchmark
sat.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n094.star.cs.uiowa.edu
space
TCT_12
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.608991146088 seconds
cpu usage
0.605767191
max memory
1.9984384E7
stage attributes
key
value
output-size
23539
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [o] --> o 1 : [o] --> o O : [o] --> o choice : [o] --> o cons : [o * o] --> o eq : [o * o] --> o false : [] --> o guess : [o] --> o if : [o * o * o] --> o member : [o * o] --> o negate : [o] --> o nil : [] --> o sat : [o] --> o satck : [o * o] --> o true : [] --> o unsat : [] --> o verify : [o] --> o if(true, X, Y) => X if(false, X, Y) => Y member(X, nil) => false member(X, cons(Y, Z)) => if(eq(X, Y), true, member(X, Z)) eq(nil, nil) => true eq(O(X), 0(Y)) => eq(X, Y) eq(0(X), 1(Y)) => false eq(1(X), 0(Y)) => false eq(1(X), 1(Y)) => eq(X, Y) negate(0(X)) => 1(X) negate(1(X)) => 0(X) choice(cons(X, Y)) => X choice(cons(X, Y)) => choice(Y) guess(nil) => nil guess(cons(X, Y)) => cons(choice(X), guess(Y)) verify(nil) => true verify(cons(X, Y)) => if(member(negate(X), Y), false, verify(Y)) sat(X) => satck(X, guess(X)) satck(X, Y) => if(verify(Y), Y, unsat) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): if(true, X, Y) >? X if(false, X, Y) >? Y member(X, nil) >? false member(X, cons(Y, Z)) >? if(eq(X, Y), true, member(X, Z)) eq(nil, nil) >? true eq(O(X), 0(Y)) >? eq(X, Y) eq(0(X), 1(Y)) >? false eq(1(X), 0(Y)) >? false eq(1(X), 1(Y)) >? eq(X, Y) negate(0(X)) >? 1(X) negate(1(X)) >? 0(X) choice(cons(X, Y)) >? X choice(cons(X, Y)) >? choice(Y) guess(nil) >? nil guess(cons(X, Y)) >? cons(choice(X), guess(Y)) verify(nil) >? true verify(cons(X, Y)) >? if(member(negate(X), Y), false, verify(Y)) sat(X) >? satck(X, guess(X)) satck(X, Y) >? if(verify(Y), Y, unsat) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[false]] = _|_ [[nil]] = _|_ [[true]] = _|_ [[unsat]] = _|_ We choose Lex = {} and Mul = {0, 1, O, choice, cons, eq, guess, if, member, negate, sat, satck, verify}, and the following precedence: sat > satck > guess > 0 = 1 = negate = verify > member > if > eq > cons > choice > O Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: if(_|_, X, Y) > X if(_|_, X, Y) >= Y member(X, _|_) >= _|_ member(X, cons(Y, Z)) >= if(eq(X, Y), _|_, member(X, Z)) eq(_|_, _|_) >= _|_ eq(O(X), 0(Y)) >= eq(X, Y) eq(0(X), 1(Y)) > _|_ eq(1(X), 0(Y)) >= _|_ eq(1(X), 1(Y)) > eq(X, Y) negate(0(X)) >= 1(X) negate(1(X)) >= 0(X) choice(cons(X, Y)) > X
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472