The topos theory of computing: introduction to the mathematics of dataflow [pdf]

The topos theory of computing: introduction to the mathematics of dataflow [pdf](raw.githubusercontent.com)

5 points by johnbernier 3 years ago | 3 comments

Hello, I do research in the area of program data-flow analysis. The theory of data-flow analysis has been extensively studied. Data Flow Analysis: Theory and Practice by Khedker, Sanyal, and Sathe is a reference textbook. This subject essentially studies how programs move data from one memory location to another.

My work in this field has led me to search for new mathematical foundations for dataflow analysis. These foundations will abstract the concept and address a number of issues. Firstly, traditional dataflow analysis only works on explicitly defined product types like bit vectors. This provides a limited scope for the theory. To generalize from this, we can use partitions, which can model any type of information accessible by a function.

Then to model dataflow relations in this new abstracted setting, I have suggested the use of the Sierpinski topos. Using this fundamental topos, we can model dataflow relations between information locations represented with the highest level of generality. This forms a broad generalisation of the notion of congruences from abstract algebra.

082349872349872 3 years ago | |

You may be interested in: Hartmanis & Stearns, Algebraic Structure Theory of Sequential Machines (1966)

johnbernier 3 years ago | | |

Upon review, Hartmanis and Stearns appear to have come closest to my work. I would recommend readers take a look at Algebraic Structure Theory of Sequential Machines (1966) prior to my paper to get a background motivation for my treatment of the subject. The idea of partition pairs in that textbook coincides with epimorphism classes in the Sierpinski topos.

So basically, all I am doing is updating that prior work and turning it into a Topos Structure Theory of Sequential Machines. I arrived at the concept of partition pairs independently through the Sierpinski topos. Hartmans & Stearns came up with the same idea for its engineering applications. It often happens that when an idea is good, it tends to crop up independently in multiple different places.