Universal Hard Interaction for Clockless Computation

Issue title: Machines, Computations and Universality, Part II

Subtitle: Dem Glücklichen schlägt keine Stunde!

Article type: Research Article

Authors: Lippi, Sylvain

Affiliations: Université de Nice – EPU 930 Route des Colles BP 145, 06903 Sophia Antipolis Cedex, France. [email protected]

Note: [] Address for correspondence: Université de Nice – EPU, 930 Route des Colles BP 145, 06903 Sophia Antipolis Cedex, France

Abstract: 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.

Keywords: Hard interaction nets, abstract machine, asynchronous computation, digital circuits, graph relabeling

DOI: 10.3233/FI-2009-0048

Journal: Fundamenta Informaticae, vol. 91, no. 2, pp. 357-394, 2009