My Papers in Computer Science

My dissertation "Mathematics of Domains" is available below.
Our review paper linked from Michael Bukatin, Ralph Kopperman, Steve Matthews, and Homeira Pajoohesh. Partial Metric Spaces. American Mathematical Monthly, 116 (2009), 708-718.
Our Tbilisi paper: Michael Bukatin and Steve Matthews. Linear Models of Computation and Program Learning. GCAI 2015, EasyChair Proceedings in Computing, 36, 66-78.

Our new paper: Michael Bukatin and Jon Anthony. Dataflow Matrix Machines and V-values: a Bridge between Programs and Neural Nets. In "K + K = 120" Festschrift, 2017.

Generalized Distances and Generalized Equalities Coincide

Partial Inconsistency and Vector Semantics of Programming Languages

Dataflow Matrix Machines (since 2017)

Measures and Distances on Approximation Domains

Analytic Properties of Approximation-Based Models of Computations: a Tutorial is available as This tutorial explains key ideas of our work on partial and relaxed metrics and co-continuous valuations and measures on approximation domains via a simple example of interval numbers.

Negative Information and Tolerances:

Michael A. Bukatin, Svetlana Yu. Shorina. On a Smyth Conjecture. Topology Proceedings, 24 (1999), 57-70. Free PDF on the site of Topology Proceedings

This electronic version of 06/19/00 is the same as the text published in the proceedings of 14th Summer Conference on General Topology and its Applications.

This paper is a follow-up of the following paper:

Michael A. Bukatin, Svetlana Yu. Shorina. Relaxed Metrics, Maximal Points, and Negative Information.

A preliminary draft is available as The comments and critique are welcome. Currently available is Version 0.6 of September 24, 1998.

This paper was presented at MFPS 14 conference (see also) and is a follow-up of our earlier paper on relationships between measures and generalized distances on domains:

Co-continuous Measures and How They Yield Relaxed Distances:

Michael A. Bukatin, Svetlana Yu. Shorina. Partial Metrics and Co-continuous Valuations. In M. Nivat, ed., Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science, 1378, 125-139, Springer, 1998.

This electronic version of 01/08/98 is the same as the text published in LNCS 1378 --- the proceedings of the FoSSaCS, a part of ETAPS'98.

An extended preliminary version (Version 0.5 of October 14, 1997) is available as

The paper introduces a new notion of co-continuity for valuations and shows how to build continuous partial and relaxed metrics from co-continuous valuations on domains.

Relaxed Distances --- Computable Distances between Programs:

Michael A. Bukatin, Joshua S. Scott. Towards Computing Distances between Programs via Scott Domains. In S. Adian, A. Nerode, eds., Logical Foundations of Computer Science, Lecture Notes in Computer Science, 1234, 33-43, Springer, 1997.

This electronic version of 03/07/97 is the same as the text published in LNCS 1234 --- the proceedings of the 4th International Symposium on Logical Foundations of Computer Science (LFCS'97).

We show that a computable distance between two equal partially defined objects, x=y, must be non-zero under very weak assumptions, thus making partial metrics by Steve Matthews and our own relaxed metrics the preferable way to define semantically meaningful distances between programs.

My co-author Joshua Scott received his undergraduate degree in Math from Brandeis (Spring 1996) and now studies at Northeastern. The key results were obtained during our joint studies on July 4, 1996 holidays.

Some extra details and an inductive, rather than deductive, angle of presentation can be found at Towards Computing Distances between Programs via Domains (version of 12/05/96). It has a scary subtitle: a Symmetric Continuous Generalized Metric for Scott Topology on Continuous Scott Domains with Countable Bases. The inductive presentation means that the results are presented in the sequence and order they were discovered, and guiding motivations at each step are emphasized, not hidden. The deductive presentation (as in the published version of our paper) means that the results are arranged into an elegant logical scheme, from the general versions of definitions to partial cases, but the traces of how this scheme was obtained are largely erased.

The previous version of this paper (version 3.0 of 10/06/96) is somewhat longer, but it does not contain the references to the related papers by S. G. Matthews and by S. J. O'Neill and discussion of the differences between our construction and the one by O'Neill, as we did not know that these results are related. It was presented on 10/09/96.

I discussed my latest efforts in this direction during my talk Relaxed Metrics on Domains, Measures and Invariance given at Third Northeastern Conference on Topological Methods in Programming Language Semantics.

Logic of Fixed Points for Approximation Domains

The following three papers study domains for denotational semantics as sets of theories of logical calculi. They are reviewed in my dissertation proposal.

Subdomains for Algebraic Information Systems solves the question "which subsets of domains should be considered subdomains?".

Information Systems and Retractions: an Elementary Treatment studies finitary retractions.

Information Systems and Complete Lattices is an abstract of my talk on the intuition behind the use of non-reflexive logics for description of non-algebraic domains (see my dissertation proposal for details).

This material was published as:

Michael A. Bukatin. Logic of Fixed Points and Scott Topology. Topology Proceedings, 26, 2002, 433-468.

Dissertation Materials

My dissertation proposal is a review of the field and a position paper. It is fairly controversial, because it is trying to make a case that things are pretty bad in the programming language theory and practice, and because it is also trying to explain why they are so bad. Comments and flames are welcome at this e-mail address. To retrieve it click on the title:

Continuous Functions as Models for Programs: Mathematics and Applications.

The current version of the complete dissertation is available below.

Final version (January 6, 2002), 135 pages.

Dissertation draft (gzipped PostScript, 245K): Mathematics of Domains (PDF, 571K): Mathematics-of-Domains.pdf

Back to Mishka's home page