TRS Stand 20472 pair #381716850

details

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

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.26464009285 seconds
cpu usage	0.260599225
max memory	1.359872E7

stage attributes

key	value
output-size	8754
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.

  0 : [] --> o 
  U11 : [o * o * o * o] --> o 
  U12 : [o * o] --> o 
  activate : [o] --> o 
  afterNth : [o * o] --> o 
  and : [o * o] --> o 
  cons : [o * o] --> o 
  fst : [o] --> o 
  head : [o] --> o 
  n!6220!6220natsFrom : [o] --> o 
  n!6220!6220s : [o] --> o 
  natsFrom : [o] --> o 
  nil : [] --> o 
  pair : [o * o] --> o 
  s : [o] --> o 
  sel : [o * o] --> o 
  snd : [o] --> o 
  splitAt : [o * o] --> o 
  tail : [o] --> o 
  take : [o * o] --> o 
  tt : [] --> o 

  U11(tt, X, Y, Z) => U12(splitAt(activate(X), activate(Z)), activate(Y)) 
  U12(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) 
  afterNth(X, Y) => snd(splitAt(X, Y)) 
  and(tt, X) => activate(X) 
  fst(pair(X, Y)) => X 
  head(cons(X, Y)) => X 
  natsFrom(X) => cons(X, n!6220!6220natsFrom(n!6220!6220s(X))) 
  sel(X, Y) => head(afterNth(X, Y)) 
  snd(pair(X, Y)) => Y 
  splitAt(0, X) => pair(nil, X) 
  splitAt(s(X), cons(Y, Z)) => U11(tt, X, Y, activate(Z)) 
  tail(cons(X, Y)) => activate(Y) 
  take(X, Y) => fst(splitAt(X, Y)) 
  natsFrom(X) => n!6220!6220natsFrom(X) 
  s(X) => n!6220!6220s(X) 
  activate(n!6220!6220natsFrom(X)) => natsFrom(activate(X)) 
  activate(n!6220!6220s(X)) => s(activate(X)) 
  activate(X) => 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] U11#(tt, X, Y, Z) =#> U12#(splitAt(activate(X), activate(Z)), activate(Y))   
    1] U11#(tt, X, Y, Z) =#> splitAt#(activate(X), activate(Z))   
    2] U11#(tt, X, Y, Z) =#> activate#(X)   
    3] U11#(tt, X, Y, Z) =#> activate#(Z)   
    4] U11#(tt, X, Y, Z) =#> activate#(Y)   
    5] U12#(pair(X, Y), Z) =#> activate#(Z)   
    6] afterNth#(X, Y) =#> snd#(splitAt(X, Y))   
    7] afterNth#(X, Y) =#> splitAt#(X, Y)   
    8] and#(tt, X) =#> activate#(X)   
    9] sel#(X, Y) =#> head#(afterNth(X, Y))   
    10] sel#(X, Y) =#> afterNth#(X, Y)   
    11] splitAt#(s(X), cons(Y, Z)) =#> U11#(tt, X, Y, activate(Z))   
    12] splitAt#(s(X), cons(Y, Z)) =#> activate#(Z)   
    13] tail#(cons(X, Y)) =#> activate#(Y)   
    14] take#(X, Y) =#> fst#(splitAt(X, Y))   
    15] take#(X, Y) =#> splitAt#(X, Y)   
    16] activate#(n!6220!6220natsFrom(X)) =#> natsFrom#(activate(X))   
    17] activate#(n!6220!6220natsFrom(X)) =#> activate#(X)   
    18] activate#(n!6220!6220s(X)) =#> s#(activate(X))   
    19] activate#(n!6220!6220s(X)) =#> activate#(X)   

  Rules R_0:

    U11(tt, X, Y, Z) => U12(splitAt(activate(X), activate(Z)), activate(Y)) 
    U12(pair(X, Y), Z) => pair(cons(activate(Z), X), Y) 
    afterNth(X, Y) => snd(splitAt(X, Y)) 
    and(tt, X) => activate(X) 
    fst(pair(X, Y)) => X 
    head(cons(X, Y)) => X 
    natsFrom(X) => cons(X, n!6220!6220natsFrom(n!6220!6220s(X))) 
    sel(X, Y) => head(afterNth(X, Y)) 
    snd(pair(X, Y)) => Y 
    splitAt(0, X) => pair(nil, X) 
    splitAt(s(X), cons(Y, Z)) => U11(tt, X, Y, activate(Z)) 
    tail(cons(X, Y)) => activate(Y) 
    take(X, Y) => fst(splitAt(X, Y)) 
    natsFrom(X) => n!6220!6220natsFrom(X) 
    s(X) => n!6220!6220s(X) 
    activate(n!6220!6220natsFrom(X)) => natsFrom(activate(X)) 
    activate(n!6220!6220s(X)) => s(activate(X)) 
    activate(X) => X

popout

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

job log

popout

actions all output return to TRS Stand 20472