HRS union beta 16688 pair #381734935

details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	0.817744970322 seconds
cpu usage	1.665343725
max memory	7.6361728E7

stage attributes

key	value
output-size	8592
starexec-result	YES

output

/export/starexec/sandbox/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
We consider the system theBenchmark.

  Alphabet:

    0 : [] --> a 
    cons : [c * c] --> c 
    copy : [a * c * c] --> c 
    f : [c] --> c 
    false : [] --> b 
    filter : [c -> b * c] --> c 
    filter2 : [b * c -> b * c * c] --> c 
    map : [c -> c * c] --> c 
    n : [] --> a 
    nil : [] --> c 
    s : [a] --> a 
    true : [] --> b 

  Rules:

    f(cons(nil, x)) => x 
    f(cons(f(cons(nil, x)), y)) => copy(n, x, y) 
    copy(0, x, y) => f(y) 
    copy(s(x), y, z) => copy(x, y, cons(f(y), z)) 
    map(g, nil) => nil 
    map(g, cons(x, y)) => cons(g x, map(g, y)) 
    filter(g, nil) => nil 
    filter(g, cons(x, y)) => filter2(g x, g, x, y) 
    filter2(true, g, x, y) => cons(x, filter(g, y)) 
    filter2(false, g, x, y) => filter(g, y) 

This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0).

We observe that the rules contain a first-order subset:

  f(cons(nil, X)) => X 
  f(cons(f(cons(nil, X)), Y)) => copy(n, X, Y) 
  copy(0, X, Y) => f(Y) 
  copy(s(X), Y, Z) => copy(X, Y, cons(f(Y), Z)) 

Moreover, the system is finitely branching.  Thus, by [Kop12, Thm. 7.55], we may omit all first-order dependency pairs from the dependency pair problem (DP(R), R) if this first-order part is Ce-terminating when seen as a many-sorted first-order TRS.

According to the external first-order termination prover, this system is indeed Ce-terminating:

 || proof of resources/system.trs
 || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616
 || 
 || 
 || Termination w.r.t. Q of the given QTRS could be proven:
 || 
 || (0) QTRS
 || (1) DependencyPairsProof [EQUIVALENT]
 || (2) QDP
 || (3) DependencyGraphProof [EQUIVALENT]
 || (4) QDP
 || (5) QDPSizeChangeProof [EQUIVALENT]
 || (6) YES
 || 
 || 
 || ----------------------------------------
 || 
 || (0)
 || Obligation:
 || Q restricted rewrite system:
 || The TRS R consists of the following rules:
 || 
 ||    f(cons(nil, %X)) -> %X
 ||    f(cons(f(cons(nil, %X)), %Y)) -> copy(n, %X, %Y)
 ||    copy(0, %X, %Y) -> f(%Y)
 ||    copy(s(%X), %Y, %Z) -> copy(%X, %Y, cons(f(%Y), %Z))
 ||    ~PAIR(%X, %Y) -> %X
 ||    ~PAIR(%X, %Y) -> %Y
 || 
 || Q is empty.
 || 
 || ----------------------------------------
 || 
 || (1) DependencyPairsProof (EQUIVALENT)
 || Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
 || ----------------------------------------
 || 
 || (2)
 || Obligation:
 || Q DP problem:
 || The TRS P consists of the following rules:
 || 
 ||    F(cons(f(cons(nil, %X)), %Y)) -> COPY(n, %X, %Y)
 ||    COPY(0, %X, %Y) -> F(%Y)
 ||    COPY(s(%X), %Y, %Z) -> COPY(%X, %Y, cons(f(%Y), %Z))
 ||    COPY(s(%X), %Y, %Z) -> F(%Y)
 || 
 || The TRS R consists of the following rules:
 || 
 ||    f(cons(nil, %X)) -> %X

popout

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

job log

popout

actions all output return to HRS union beta 16688