@PhdThesis{Alexiev1999-thesis,
  author       = {Vladimir Alexiev},
  title        = {{Non-deterministic Interaction Nets}},
  school       = {University of Alberta},
  year         = 1999,
  url          = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis.pdf},
  url_Slides   = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesisPresentation.pdf},
  url_Other    = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis-2up.pdf},
  abstract     = {The Interaction Nets (IN) of Lafont are a graphical formalism used to model parallel computation. Their genesis can be traced back to the Proof Nets of Linear Logic. They enjoy several nice theoretical properties, amongst them pure locality of interaction, strong confluence, computational completeness, syntactically-definable deadlock-free fragments, combinatorial completeness (existence of a Universal IN). They also have nice "pragmatic" properties: they are simple and elegant, intuitive, can capture aspects of computation at widely varying levels of abstraction. Compared to term and graph rewriting systems, INs are much simpler (a subset of such systems that imposes several constraints on the rewriting process), but are still computationally complete (can capture the lambda-calculus). INs are a refinement of graph rewriting which keeps only the essential features in the system.
Conventional INs are strongly confluent, and are therefore unsuitable for the modeling of non-deterministic systems such as process calculi and concurrent object-oriented programming. We study four diffrent ways of "breaking" the confluence of INs by introducing various extensions:
- IN with Multiple (reduction) Rules (INMR); Allow more than one reduction rule per redex.
- IN with Multiple Principal Ports (INMPP): Allow more than one active port per node.
- IN with MultiPorts (INMP): Allow more than one connection per port.
- IN with Multiple Connections (INMC): Allow hyper-edges (in the graph-theoretical sense), i.e. connections between more than two ports.

We study in considerable detail the relative expressive power of these systems, both by representing various programming examples in them, and by constructing inter-representations that translate nets from one system to another.
We study formally a translation from the finite pi-calculus to a system that we call MultiInteraction Nets: MIN=INMP+NMPP. We prove the faithfulness of the translation to the pi-calculus processes that it represents, both structural and operational (completeness and soundness of reduction). We show that unlike the pi-calculus, our translation implements the Prefix operation of the pi-calculus in a distributed and purely local manner, and implements explicitly the distribution and duplication of values to the corresponding occurrences of a variable.
We compare our translation to other graphical and combinatory representations of the pi-calculus, such as the pi-nets of Milner, the Interaction Diagrams of Parrow, and the Concurrent Combinators of Honda and Yoshida.
The original paper on IN (Lafont, 1990) states that INs were designed to be simple and practical; to be a "programming language that can be used for the design of interactive software". However, to date INs have been used only for theoretical investigations. This thesis is mostly devoted to a hands-on exploration of applications of IN to various "programming problems".}
}

{"_id":{"_str":"5351586a0b79f58e7a0001a5"},"__v":0,"authorIDs":["56ba0fcf16a1deb95500029f","Cy3yEAcX3dbuq4xMC","FrRQJytwCzTi3PiNC","T7F3ZKH8GpLhZMAzy","xDxoTrxKYWXDTNfy4"],"author_short":["Alexiev, V."],"bibbaseid":"alexiev-nondeterministicinteractionnets-1999","bibdata":{"bibtype":"phdthesis","type":"phdthesis","author":[{"firstnames":["Vladimir"],"propositions":[],"lastnames":["Alexiev"],"suffixes":[]}],"title":"Non-deterministic Interaction Nets","school":"University of Alberta","year":"1999","url":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis.pdf","url_slides":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesisPresentation.pdf","url_other":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis-2up.pdf","abstract":"The Interaction Nets (IN) of Lafont are a graphical formalism used to model parallel computation. Their genesis can be traced back to the Proof Nets of Linear Logic. They enjoy several nice theoretical properties, amongst them pure locality of interaction, strong confluence, computational completeness, syntactically-definable deadlock-free fragments, combinatorial completeness (existence of a Universal IN). They also have nice \"pragmatic\" properties: they are simple and elegant, intuitive, can capture aspects of computation at widely varying levels of abstraction. Compared to term and graph rewriting systems, INs are much simpler (a subset of such systems that imposes several constraints on the rewriting process), but are still computationally complete (can capture the lambda-calculus). INs are a refinement of graph rewriting which keeps only the essential features in the system. Conventional INs are strongly confluent, and are therefore unsuitable for the modeling of non-deterministic systems such as process calculi and concurrent object-oriented programming. We study four diffrent ways of \"breaking\" the confluence of INs by introducing various extensions: - IN with Multiple (reduction) Rules (INMR); Allow more than one reduction rule per redex. - IN with Multiple Principal Ports (INMPP): Allow more than one active port per node. - IN with MultiPorts (INMP): Allow more than one connection per port. - IN with Multiple Connections (INMC): Allow hyper-edges (in the graph-theoretical sense), i.e. connections between more than two ports. We study in considerable detail the relative expressive power of these systems, both by representing various programming examples in them, and by constructing inter-representations that translate nets from one system to another. We study formally a translation from the finite pi-calculus to a system that we call MultiInteraction Nets: MIN=INMP+NMPP. We prove the faithfulness of the translation to the pi-calculus processes that it represents, both structural and operational (completeness and soundness of reduction). We show that unlike the pi-calculus, our translation implements the Prefix operation of the pi-calculus in a distributed and purely local manner, and implements explicitly the distribution and duplication of values to the corresponding occurrences of a variable. We compare our translation to other graphical and combinatory representations of the pi-calculus, such as the pi-nets of Milner, the Interaction Diagrams of Parrow, and the Concurrent Combinators of Honda and Yoshida. The original paper on IN (Lafont, 1990) states that INs were designed to be simple and practical; to be a \"programming language that can be used for the design of interactive software\". However, to date INs have been used only for theoretical investigations. This thesis is mostly devoted to a hands-on exploration of applications of IN to various \"programming problems\".","bibtex":"@PhdThesis{Alexiev1999-thesis,\n author = {Vladimir Alexiev},\n title = {{Non-deterministic Interaction Nets}},\n school = {University of Alberta},\n year = 1999,\n url = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis.pdf},\n url_Slides = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesisPresentation.pdf},\n url_Other = {https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis-2up.pdf},\n abstract = {The Interaction Nets (IN) of Lafont are a graphical formalism used to model parallel computation. Their genesis can be traced back to the Proof Nets of Linear Logic. They enjoy several nice theoretical properties, amongst them pure locality of interaction, strong confluence, computational completeness, syntactically-definable deadlock-free fragments, combinatorial completeness (existence of a Universal IN). They also have nice \"pragmatic\" properties: they are simple and elegant, intuitive, can capture aspects of computation at widely varying levels of abstraction. Compared to term and graph rewriting systems, INs are much simpler (a subset of such systems that imposes several constraints on the rewriting process), but are still computationally complete (can capture the lambda-calculus). INs are a refinement of graph rewriting which keeps only the essential features in the system.\nConventional INs are strongly confluent, and are therefore unsuitable for the modeling of non-deterministic systems such as process calculi and concurrent object-oriented programming. We study four diffrent ways of \"breaking\" the confluence of INs by introducing various extensions:\n- IN with Multiple (reduction) Rules (INMR); Allow more than one reduction rule per redex.\n- IN with Multiple Principal Ports (INMPP): Allow more than one active port per node.\n- IN with MultiPorts (INMP): Allow more than one connection per port.\n- IN with Multiple Connections (INMC): Allow hyper-edges (in the graph-theoretical sense), i.e. connections between more than two ports.\n\nWe study in considerable detail the relative expressive power of these systems, both by representing various programming examples in them, and by constructing inter-representations that translate nets from one system to another.\nWe study formally a translation from the finite pi-calculus to a system that we call MultiInteraction Nets: MIN=INMP+NMPP. We prove the faithfulness of the translation to the pi-calculus processes that it represents, both structural and operational (completeness and soundness of reduction). We show that unlike the pi-calculus, our translation implements the Prefix operation of the pi-calculus in a distributed and purely local manner, and implements explicitly the distribution and duplication of values to the corresponding occurrences of a variable.\nWe compare our translation to other graphical and combinatory representations of the pi-calculus, such as the pi-nets of Milner, the Interaction Diagrams of Parrow, and the Concurrent Combinators of Honda and Yoshida.\nThe original paper on IN (Lafont, 1990) states that INs were designed to be simple and practical; to be a \"programming language that can be used for the design of interactive software\". However, to date INs have been used only for theoretical investigations. This thesis is mostly devoted to a hands-on exploration of applications of IN to various \"programming problems\".}\n}\n\n","author_short":["Alexiev, V."],"key":"Alexiev1999-thesis","id":"Alexiev1999-thesis","bibbaseid":"alexiev-nondeterministicinteractionnets-1999","role":"author","urls":{"Paper":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis.pdf"," slides":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesisPresentation.pdf"," other":"https://rawgit2.com/VladimirAlexiev/my/master/pubs/Alexiev1999-thesis-2up.pdf"},"metadata":{"authorlinks":{"alexiev, v":"https://rawgit2.com/VladimirAlexiev/my/master/index.html"}},"downloads":2},"bibtype":"phdthesis","biburl":"http://rawgit2.com/VladimirAlexiev/my/master/Alexiev-bibliography.bib","downloads":2,"keywords":[],"search_terms":["non","deterministic","interaction","nets","alexiev"],"title":"Non-deterministic Interaction Nets","year":1999,"dataSources":["fmPsPQKhqqQkXh5M4","GweCNx2ZyPa9cXx7D"]}