In-place Graph Rewriting with Interaction Nets
An algorithm is in-place, or runs in-situ, when it does not need any additional memory to execute beyond a small constant amount. There are many algorithms that are efficient because of this feature, therefore it is an important aspect of an algorithm. In most programming languages, it is not obvio...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1609.03641v1 |
| _version_ | 1818203422463098880 |
|---|---|
| author | Ian Mackie Shinya Sato |
| author_facet | Ian Mackie Shinya Sato |
| author_sort | Ian Mackie |
| collection | DOAJ |
| description | An algorithm is in-place, or runs in-situ, when it does not need any additional memory to execute beyond a small constant amount. There are many algorithms that are efficient because of this feature, therefore it is an important aspect of an algorithm. In most programming languages, it is not obvious when an algorithm can run in-place, and moreover it is often not clear that the implementation respects that idea. In this paper we study interaction nets as a formalism where we can see directly, visually, that an algorithm is in-place, and moreover the implementation will respect that it is in-place. Not all algorithms can run in-place however. We can nevertheless still use the same language, but now we can annotate parts of the algorithm that can run in-place. We suggest an annotation for rules, and give an algorithm to find this automatically through analysis of the interaction rules. |
| first_indexed | 2024-12-12T03:25:05Z |
| format | Article |
| id | doaj.art-81b55619fa874f329e4db99ed3587633 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-12T03:25:05Z |
| publishDate | 2016-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-81b55619fa874f329e4db99ed35876332022-12-22T00:40:04ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-09-01225Proc. TERMGRAPH 2016152410.4204/EPTCS.225.4:5In-place Graph Rewriting with Interaction NetsIan Mackie0Shinya Sato1 LIX, Ecole Polytechnique, France Ibaraki University, Japan An algorithm is in-place, or runs in-situ, when it does not need any additional memory to execute beyond a small constant amount. There are many algorithms that are efficient because of this feature, therefore it is an important aspect of an algorithm. In most programming languages, it is not obvious when an algorithm can run in-place, and moreover it is often not clear that the implementation respects that idea. In this paper we study interaction nets as a formalism where we can see directly, visually, that an algorithm is in-place, and moreover the implementation will respect that it is in-place. Not all algorithms can run in-place however. We can nevertheless still use the same language, but now we can annotate parts of the algorithm that can run in-place. We suggest an annotation for rules, and give an algorithm to find this automatically through analysis of the interaction rules.http://arxiv.org/pdf/1609.03641v1 |
| spellingShingle | Ian Mackie Shinya Sato In-place Graph Rewriting with Interaction Nets Electronic Proceedings in Theoretical Computer Science |
| title | In-place Graph Rewriting with Interaction Nets |
| title_full | In-place Graph Rewriting with Interaction Nets |
| title_fullStr | In-place Graph Rewriting with Interaction Nets |
| title_full_unstemmed | In-place Graph Rewriting with Interaction Nets |
| title_short | In-place Graph Rewriting with Interaction Nets |
| title_sort | in place graph rewriting with interaction nets |
| url | http://arxiv.org/pdf/1609.03641v1 |
| work_keys_str_mv | AT ianmackie inplacegraphrewritingwithinteractionnets AT shinyasato inplacegraphrewritingwithinteractionnets |