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


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


MAYBE
We consider the system theBenchmark.

  Alphabet:

    abs : [] --> a -> a -> aa 
    app : [] --> aa -> a -> a 
    let : [] --> ta -> a -> ta -> ta 
    return : [] --> a -> ta 

  Rules:

    app (abs (/\x.f x)) y => f y 
    abs (/\x.app y x) => y 
    let (return x) (/\y.f y) => f x 
    let x (/\y.return y) => x 
    let (let x (/\y.f y)) (/\z.g z) => let x (/\u.let (f u) (/\v.g v)) 

Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term.

We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0).  This leads to the following AFSM:

  Alphabet:

    abs : [a -> a] --> aa 
    app : [aa * a] --> a 
    let : [ta * a -> ta] --> ta 
    return : [a] --> ta 
    ~AP1 : [a -> a * a] --> a 
    ~AP2 : [a -> ta * a] --> ta 

  Rules:

    app(abs(/\x.~AP1(F, x)), X) => ~AP1(F, X) 
    abs(/\x.app(X, x)) => X 
    let(return(X), /\x.~AP2(F, x)) => ~AP2(F, X) 
    let(X, /\x.return(x)) => X 
    let(let(X, /\x.~AP2(F, x)), /\y.~AP2(G, y)) => let(X, /\z.let(~AP2(F, z), /\u.~AP2(G, u))) 
    app(abs(/\x.app(X, x)), Y) => app(X, Y) 
    let(return(X), /\x.return(x)) => return(X) 
    let(let(X, /\x.return(x)), /\y.~AP2(F, y)) => let(X, /\z.let(return(z), /\u.~AP2(F, u))) 
    let(let(X, /\x.~AP2(F, x)), /\y.return(y)) => let(X, /\z.let(~AP2(F, z), /\u.return(u))) 
    let(let(X, /\x.return(x)), /\y.return(y)) => let(X, /\z.let(return(z), /\u.return(u))) 
    ~AP1(F, X) => F X 
    ~AP2(F, X) => F X 


+++ Citations +++

[Kop11]  C. Kop.  Simplifying Algebraic Functional Systems.  In Proceedings of CAI 2011, volume 6742 of LNCS.  201--215, Springer, 2011.