most recent 30 from http://mathoverflow.net 2013-05-25T08:19:02Z http://mathoverflow.net/feeds/question/109762 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109762/looking-for-counterexamples-to-optimality-by-levy Anton Salikhmetov 2012-10-15T21:06:37Z 2012-10-17T21:40:46Z

<p>Let us encode $λ$-expressions into interaction nets as</p> <p><img src="http://ic.pics.livejournal.com/codedot/11832244/21617/21617_original.png" alt="usual"></p> <p>with both abstraction and application nodes being interaction combinator $γ$.</p> <p>For sharing nodes, let us choose such an agent $ψ$ that</p> <p>$$ ψ[γ(x, y), γ(z, t)] \bowtie γ[δ(x, z), δ(y, t)] $$</p> <p>and</p> <p>$$ ψ[δ(x, y), δ(z, t)] \bowtie δ[ψ(x, z), ψ(y, t)], $$</p> <p>with interaction combinator $δ$ involved.</p> <p>Please provide a counterexample to the resulting interaction system's optimality by Levy.</p>