TRS Stand 20472 pair #381717020

details

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

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.801074028015 seconds
cpu usage	0.798536302
max memory	1.2136448E7

stage attributes

key	value
output-size	43994
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 
  U11 : [o * o] --> o 
  a!6220!6220U11 : [o * o] --> o 
  a!6220!6220and : [o * o] --> o 
  a!6220!6220isNat : [o] --> o 
  a!6220!6220isNatIList : [o] --> o 
  a!6220!6220isNatList : [o] --> o 
  a!6220!6220length : [o] --> o 
  a!6220!6220zeros : [] --> o 
  and : [o * o] --> o 
  cons : [o * o] --> o 
  isNat : [o] --> o 
  isNatIList : [o] --> o 
  isNatList : [o] --> o 
  length : [o] --> o 
  mark : [o] --> o 
  nil : [] --> o 
  s : [o] --> o 
  tt : [] --> o 
  zeros : [] --> o 

  a!6220!6220zeros => cons(0, zeros) 
  a!6220!6220U11(tt, X) => s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) => mark(X) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(length(X)) => a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) => a!6220!6220isNat(X) 
  a!6220!6220isNatIList(X) => a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) => tt 
  a!6220!6220isNatIList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(nil) => tt 
  a!6220!6220isNatList(cons(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(nil) => 0 
  a!6220!6220length(cons(X, Y)) => a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) => a!6220!6220zeros 
  mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) 
  mark(length(X)) => a!6220!6220length(mark(X)) 
  mark(and(X, Y)) => a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(isNatList(X)) => a!6220!6220isNatList(X) 
  mark(isNatIList(X)) => a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) => cons(mark(X), Y) 
  mark(0) => 0 
  mark(tt) => tt 
  mark(s(X)) => s(mark(X)) 
  mark(nil) => nil 
  a!6220!6220zeros => zeros 
  a!6220!6220U11(X, Y) => U11(X, Y) 
  a!6220!6220length(X) => length(X) 
  a!6220!6220and(X, Y) => and(X, Y) 
  a!6220!6220isNat(X) => isNat(X) 
  a!6220!6220isNatList(X) => isNatList(X) 
  a!6220!6220isNatIList(X) => isNatIList(X) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  a!6220!6220zeros >? cons(0, zeros) 
  a!6220!6220U11(tt, X) >? s(a!6220!6220length(mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(length(X)) >? a!6220!6220isNatList(X) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220isNatIList(X) >? a!6220!6220isNatList(X) 
  a!6220!6220isNatIList(zeros) >? tt 
  a!6220!6220isNatIList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatIList(Y)) 
  a!6220!6220isNatList(nil) >? tt 
  a!6220!6220isNatList(cons(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNatList(Y)) 
  a!6220!6220length(nil) >? 0 
  a!6220!6220length(cons(X, Y)) >? a!6220!6220U11(a!6220!6220and(a!6220!6220isNatList(Y), isNat(X)), Y) 
  mark(zeros) >? a!6220!6220zeros 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(isNatList(X)) >? a!6220!6220isNatList(X) 
  mark(isNatIList(X)) >? a!6220!6220isNatIList(X) 
  mark(cons(X, Y)) >? cons(mark(X), Y) 
  mark(0) >? 0 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(nil) >? nil 
  a!6220!6220zeros >? zeros 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220length(X) >? length(X) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 
  a!6220!6220isNatList(X) >? isNatList(X)

popout

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

job log

popout

actions all output return to TRS Stand 20472