Universal Hard Interaction for Clockless Computation. Dem Glücklichen schägt keine Stunde!

• Autorzy: Lippi S.
• Języki publikacji: EN

Abstrakty

EN

We give a self-contained presentation of Hard Interaction, a rewriting system on fixed graphs. We discuss the universality of natural subclasses of hard systems and highlight the main ideas that lead to a universal system with 7 rules called Hard Combinators.

Słowa kluczowe

EN

hard interaction nets; abstract machine; asynchronous computations; digital circuits; graph relabeling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 357--394
• Opis fizyczny: Bibliogr. 19 poz., wykr.

Twórcy

autor

Lippi S.

• Université de Nice - EPU 930 Route des Colles BP 145, 06903 Sophia Antipolis Cedex, France,

Bibliografia

• [1] Andrea Asperti and Stefano Guerrini. The Optimal Implementation of Functional Programming Languages, volume 45 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1998.
• [2] Kenneth E. Batcher. Sorting networks and their applications. In Spring Joint Computer Conference. AFIPS Proc. vol. 32, 1968.
• [3] Denis Béchet and Sylvain Lippi. Hard combinators. In International Workshop on Term Graph Rewriting (TERMGRAPH 2007). ENTCS, Elsevier, 2007.
• [4] Denis Béchet and Sylvain Lippi. Universal boolean systems. In International Workshop on Term Graph Rewriting (TERMGRAPH 2007). ENTCS, Elsevier, 2007.
• [5] Arjan Bink, Mark de Clercq, and Richard York. Arm996hs synthetisable cpu with clockless technology. Information Quarterly (ARM internal journal), 5(4):20-24, 2006.
• [6] Jérémie Chalopin, Yves Métivier, andWieslaw Zielonka. Local computations in graphs: The case of cellular edge local computations. Fundamenta Informaticae, 74(1):85-114, 2006.
• [7] Thierry Champion. Les réseaux d'interaction durs. Technical report, Rapport de stage, Laboratoire de Mathématiques Discrètes, 1995.
• [8] Jean-Yves Girard. Linear logic. Theoretical Computer Science 50, 50(1):1-102, 1987.
• [9] Yves Lafont. Interaction nets. In proceedings of the 17th Annnual ACM Symposium on Principles of Programming Languages, Orlando (Fla., USA), pages 95-108, 1990.
• [10] Yves Lafont. The paradigm of interaction. Technical report, Laboratoire d'Informatique Ecole Normale Supérieure, 1992.
• [11] Yves Lafont. From proof-nets to interaction nets. In Advances in Linear Logic, London Mathematical Society Lecture Note Series 222. Cambridge University Press, 1995.
• [12] Yves Lafont. Interaction combinators. Information and Computation, 137(1):69-101, 1997.
• [13] Sylvain Lippi. Encoding left reduction in the lambda-calculus with interaction nets. Mathematical Structures in Computer Science, 12(6), December 2002.
• [14] Sylvain Lippi. inin: a graphical interpreter for the interaction nets. In Proceedings of Rewriting Techniques and Applications (RTA '02). Springer Verlag, 2002.
• [15] Ian Mackie. Yale: Yet another lambda evaluator based on intetaction nets. In Proceedings of the 3rd ACM SIGPLAN International Conference on Functional Programming (ICFP'98). ACM Press, 1998.
• [16] Bruno Martin. Cellular automata universality revisited. In proceedings of the FCT '97, volume 1279, pages 329-339. Lecture Notes in Computer Science, 1997.
• [17] Damiano Mazza. Multiport interaction nets and concurrency. In Proceedings of CONCUR 2005, LNCS 3653, pages 21-35, 2005.
• [18] Jorge Sousa Pinto. Implantation parallèle avec la logique linéaire (applications des réseaux d'interaction et de la géométrie de l'interaction). PhD thesis, Ecole Polytechnique, 2001.
• [19] Jean Vuillemin. On circuits and numbers. IEEE Trans. on Computers, 43(8):868-79, 1994.