TRS Stand 20472 pair #381715490

details

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

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	8.77813386917 seconds
cpu usage	8.767302775
max memory	1.26492672E8

stage attributes

key	value
output-size	160321
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 
  a!6220!6220add : [o * o] --> o 
  a!6220!6220dbl : [o] --> o 
  a!6220!6220first : [o * o] --> o 
  a!6220!6220half : [o] --> o 
  a!6220!6220sqr : [o] --> o 
  a!6220!6220terms : [o] --> o 
  add : [o * o] --> o 
  cons : [o * o] --> o 
  dbl : [o] --> o 
  first : [o * o] --> o 
  half : [o] --> o 
  mark : [o] --> o 
  nil : [] --> o 
  recip : [o] --> o 
  s : [o] --> o 
  sqr : [o] --> o 
  terms : [o] --> o 

  a!6220!6220terms(X) => cons(recip(a!6220!6220sqr(mark(X))), terms(s(X))) 
  a!6220!6220sqr(0) => 0 
  a!6220!6220sqr(s(X)) => s(a!6220!6220add(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))) 
  a!6220!6220dbl(0) => 0 
  a!6220!6220dbl(s(X)) => s(s(a!6220!6220dbl(mark(X)))) 
  a!6220!6220add(0, X) => mark(X) 
  a!6220!6220add(s(X), Y) => s(a!6220!6220add(mark(X), mark(Y))) 
  a!6220!6220first(0, X) => nil 
  a!6220!6220first(s(X), cons(Y, Z)) => cons(mark(Y), first(X, Z)) 
  a!6220!6220half(0) => 0 
  a!6220!6220half(s(0)) => 0 
  a!6220!6220half(s(s(X))) => s(a!6220!6220half(mark(X))) 
  a!6220!6220half(dbl(X)) => mark(X) 
  mark(terms(X)) => a!6220!6220terms(mark(X)) 
  mark(sqr(X)) => a!6220!6220sqr(mark(X)) 
  mark(add(X, Y)) => a!6220!6220add(mark(X), mark(Y)) 
  mark(dbl(X)) => a!6220!6220dbl(mark(X)) 
  mark(first(X, Y)) => a!6220!6220first(mark(X), mark(Y)) 
  mark(half(X)) => a!6220!6220half(mark(X)) 
  mark(cons(X, Y)) => cons(mark(X), Y) 
  mark(recip(X)) => recip(mark(X)) 
  mark(s(X)) => s(mark(X)) 
  mark(0) => 0 
  mark(nil) => nil 
  a!6220!6220terms(X) => terms(X) 
  a!6220!6220sqr(X) => sqr(X) 
  a!6220!6220add(X, Y) => add(X, Y) 
  a!6220!6220dbl(X) => dbl(X) 
  a!6220!6220first(X, Y) => first(X, Y) 
  a!6220!6220half(X) => half(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] a!6220!6220terms#(X) =#> a!6220!6220sqr#(mark(X))   
    1] a!6220!6220terms#(X) =#> mark#(X)   
    2] a!6220!6220sqr#(s(X)) =#> a!6220!6220add#(a!6220!6220sqr(mark(X)), a!6220!6220dbl(mark(X)))   
    3] a!6220!6220sqr#(s(X)) =#> a!6220!6220sqr#(mark(X))   
    4] a!6220!6220sqr#(s(X)) =#> mark#(X)   
    5] a!6220!6220sqr#(s(X)) =#> a!6220!6220dbl#(mark(X))   
    6] a!6220!6220sqr#(s(X)) =#> mark#(X)   
    7] a!6220!6220dbl#(s(X)) =#> a!6220!6220dbl#(mark(X))   
    8] a!6220!6220dbl#(s(X)) =#> mark#(X)   
    9] a!6220!6220add#(0, X) =#> mark#(X)   
    10] a!6220!6220add#(s(X), Y) =#> a!6220!6220add#(mark(X), mark(Y))   
    11] a!6220!6220add#(s(X), Y) =#> mark#(X)   
    12] a!6220!6220add#(s(X), Y) =#> mark#(Y)   
    13] a!6220!6220first#(s(X), cons(Y, Z)) =#> mark#(Y)   
    14] a!6220!6220half#(s(s(X))) =#> a!6220!6220half#(mark(X))   
    15] a!6220!6220half#(s(s(X))) =#> mark#(X)   
    16] a!6220!6220half#(dbl(X)) =#> mark#(X)   
    17] mark#(terms(X)) =#> a!6220!6220terms#(mark(X))   
    18] mark#(terms(X)) =#> mark#(X)   
    19] mark#(sqr(X)) =#> a!6220!6220sqr#(mark(X))   
    20] mark#(sqr(X)) =#> mark#(X)   
    21] mark#(add(X, Y)) =#> a!6220!6220add#(mark(X), mark(Y))   
    22] mark#(add(X, Y)) =#> mark#(X)   
    23] mark#(add(X, Y)) =#> mark#(Y)   
    24] mark#(dbl(X)) =#> a!6220!6220dbl#(mark(X))   
    25] mark#(dbl(X)) =#> mark#(X)   
    26] mark#(first(X, Y)) =#> a!6220!6220first#(mark(X), mark(Y))   
    27] mark#(first(X, Y)) =#> mark#(X)   
    28] mark#(first(X, Y)) =#> mark#(Y)   
    29] mark#(half(X)) =#> a!6220!6220half#(mark(X))   
    30] mark#(half(X)) =#> mark#(X)   
    31] mark#(cons(X, Y)) =#> mark#(X)   
    32] mark#(recip(X)) =#> mark#(X)

popout

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

job log

popout

actions all output return to TRS Stand 20472