Petri nets and Minsky machines in linear logic

Andres Ojamaa

Thursday, 27 April 2006, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B126


Abstract: In this talk a computational interpretation of linear logic suggested by Max I. Kanovich will be described. Using this framework it will be shown that the derivability problem of !-Horn fragment of linear logic is directly equivalent to the reachability problem for Petri nets. An encoding of standard Minsky machines into linear logic will also be presented.


Tarmo Uustalu
Last update 25.4.2006