TRS Stand 20472 pair #381712265

details
property	value
status	complete
benchmark	lse.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n014.star.cs.uiowa.edu
space	CiME_04
run statistics
property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.508018016815 seconds
cpu usage	0.497343036
max memory	1.697792E7
stage attributes
key	value
output-size	27125
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.

  Case : [o * o * o] --> o 
  Concat : [o * o] --> o 
  Cons!6220sum : [o * o * o] --> o 
  Cons!6220usual : [o * o * o] --> o 
  Frozen : [o * o * o * o] --> o 
  Id : [] --> o 
  Left : [] --> o 
  Right : [] --> o 
  Sum!6220constant : [o] --> o 
  Sum!6220sub : [o * o] --> o 
  Sum!6220term!6220var : [o] --> o 
  Term!6220app : [o * o] --> o 
  Term!6220inl : [o] --> o 
  Term!6220inr : [o] --> o 
  Term!6220pair : [o * o] --> o 
  Term!6220sub : [o * o] --> o 
  Term!6220var : [o] --> o 

  Term!6220sub(Case(X, Y, Z), U) => Frozen(X, Sum!6220sub(Y, U), Z, U) 
  Frozen(X, Sum!6220constant(Left), Y, Z) => Term!6220sub(X, Z) 
  Frozen(X, Sum!6220constant(Right), Y, Z) => Term!6220sub(Y, Z) 
  Frozen(X, Sum!6220term!6220var(Y), Z, U) => Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
  Term!6220sub(Term!6220app(X, Y), Z) => Term!6220app(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220pair(X, Y), Z) => Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
  Term!6220sub(Term!6220inl(X), Y) => Term!6220inl(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220inr(X), Y) => Term!6220inr(Term!6220sub(X, Y)) 
  Term!6220sub(Term!6220var(X), Id) => Term!6220var(X) 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Z 
  Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
  Term!6220sub(Term!6220sub(X, Y), Z) => Term!6220sub(X, Concat(Y, Z)) 
  Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
  Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
  Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U) 
  Concat(Concat(X, Y), Z) => Concat(X, Concat(Y, Z)) 
  Concat(Cons!6220usual(X, Y, Z), U) => Cons!6220usual(X, Term!6220sub(Y, U), Concat(Z, U)) 
  Concat(Cons!6220sum(X, Y, Z), U) => Cons!6220sum(X, Y, Concat(Z, U)) 
  Concat(Id, 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] Term!6220sub#(Case(X, Y, Z), U) =#> Frozen#(X, Sum!6220sub(Y, U), Z, U)   
    1] Term!6220sub#(Case(X, Y, Z), U) =#> Sum!6220sub#(Y, U)   
    2] Frozen#(X, Sum!6220constant(Left), Y, Z) =#> Term!6220sub#(X, Z)   
    3] Frozen#(X, Sum!6220constant(Right), Y, Z) =#> Term!6220sub#(Y, Z)   
    4] Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(X, U)   
    5] Frozen#(X, Sum!6220term!6220var(Y), Z, U) =#> Term!6220sub#(Z, U)   
    6] Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(X, Z)   
    7] Term!6220sub#(Term!6220app(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    8] Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(X, Z)   
    9] Term!6220sub#(Term!6220pair(X, Y), Z) =#> Term!6220sub#(Y, Z)   
    10] Term!6220sub#(Term!6220inl(X), Y) =#> Term!6220sub#(X, Y)   
    11] Term!6220sub#(Term!6220inr(X), Y) =#> Term!6220sub#(X, Y)   
    12] Term!6220sub#(Term!6220var(X), Cons!6220usual(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   
    13] Term!6220sub#(Term!6220var(X), Cons!6220sum(Y, Z, U)) =#> Term!6220sub#(Term!6220var(X), U)   
    14] Term!6220sub#(Term!6220sub(X, Y), Z) =#> Term!6220sub#(X, Concat(Y, Z))   
    15] Term!6220sub#(Term!6220sub(X, Y), Z) =#> Concat#(Y, Z)   
    16] Sum!6220sub#(X, Cons!6220sum(Y, Z, U)) =#> Sum!6220sub#(X, U)   
    17] Sum!6220sub#(X, Cons!6220usual(Y, Z, U)) =#> Sum!6220sub#(X, U)   
    18] Concat#(Concat(X, Y), Z) =#> Concat#(X, Concat(Y, Z))   
    19] Concat#(Concat(X, Y), Z) =#> Concat#(Y, Z)   
    20] Concat#(Cons!6220usual(X, Y, Z), U) =#> Term!6220sub#(Y, U)   
    21] Concat#(Cons!6220usual(X, Y, Z), U) =#> Concat#(Z, U)   
    22] Concat#(Cons!6220sum(X, Y, Z), U) =#> Concat#(Z, U)   

  Rules R_0:

    Term!6220sub(Case(X, Y, Z), U) => Frozen(X, Sum!6220sub(Y, U), Z, U) 
    Frozen(X, Sum!6220constant(Left), Y, Z) => Term!6220sub(X, Z) 
    Frozen(X, Sum!6220constant(Right), Y, Z) => Term!6220sub(Y, Z) 
    Frozen(X, Sum!6220term!6220var(Y), Z, U) => Case(Term!6220sub(X, U), Y, Term!6220sub(Z, U)) 
    Term!6220sub(Term!6220app(X, Y), Z) => Term!6220app(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
    Term!6220sub(Term!6220pair(X, Y), Z) => Term!6220pair(Term!6220sub(X, Z), Term!6220sub(Y, Z)) 
    Term!6220sub(Term!6220inl(X), Y) => Term!6220inl(Term!6220sub(X, Y)) 
    Term!6220sub(Term!6220inr(X), Y) => Term!6220inr(Term!6220sub(X, Y)) 
    Term!6220sub(Term!6220var(X), Id) => Term!6220var(X) 
    Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Z 
    Term!6220sub(Term!6220var(X), Cons!6220usual(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
    Term!6220sub(Term!6220var(X), Cons!6220sum(Y, Z, U)) => Term!6220sub(Term!6220var(X), U) 
    Term!6220sub(Term!6220sub(X, Y), Z) => Term!6220sub(X, Concat(Y, Z)) 
    Sum!6220sub(X, Id) => Sum!6220term!6220var(X) 
    Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220constant(Z) 
    Sum!6220sub(X, Cons!6220sum(Y, Z, U)) => Sum!6220sub(X, U) 
    Sum!6220sub(X, Cons!6220usual(Y, Z, U)) => Sum!6220sub(X, U)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions all output return to TRS Stand 20472