/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:

    bind : [] --> Ta -> a -> Ta -> Ta 
    return : [] --> a -> Ta 

  Rules:

    bind (return x) (/\y.f y) => f x 
    bind x (/\y.return y) => x 
    bind (bind x (/\y.f y)) (/\z.g z) => bind x (/\u.bind (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:

    bind : [Ta * a -> Ta] --> Ta 
    return : [a] --> Ta 
    ~AP1 : [a -> Ta * a] --> Ta 

  Rules:

    bind(return(X), /\x.~AP1(F, x)) => ~AP1(F, X) 
    bind(X, /\x.return(x)) => X 
    bind(bind(X, /\x.~AP1(F, x)), /\y.~AP1(G, y)) => bind(X, /\z.bind(~AP1(F, z), /\u.~AP1(G, u))) 
    bind(return(X), /\x.return(x)) => return(X) 
    bind(bind(X, /\x.return(x)), /\y.~AP1(F, y)) => bind(X, /\z.bind(return(z), /\u.~AP1(F, u))) 
    bind(bind(X, /\x.~AP1(F, x)), /\y.return(y)) => bind(X, /\z.bind(~AP1(F, z), /\u.return(u))) 
    bind(bind(X, /\x.return(x)), /\y.return(y)) => bind(X, /\z.bind(return(z), /\u.return(u))) 
    ~AP1(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.