Skip to main content
PRL Project

Mark Bickford

Senior Researcher

Mark Bickford at 2011 Seminar
Mark Bickford


Ph.D., Mathematics, University of Wisconsin, 1983

Publications List


After a thorough education in logic, recursion theory, and set theory at UW and three year appointment in mathematics at the University of Texas, Dr. Mark Bickford joined ATC-NY (then called Odyssey Research Associates) in 1986 where he has devoted his career to the development of formal methods tools. Early projects at ATC-NY included building a theorem prover (Clio) based on combinatory logic and domain theory which was used to verify a pipelined micro-processor, called MiniCayuga, designed at Cornell. He also built the theorem proving component (based on MIT's Larch methodology) for ATC-NY's tool, Penelope, for verification of Ada programs; and, using the same Larch theorem prover, went on to build a new tool for verification of hardware designs written in VHDL. He also created a theorem prover for concurrent algorithms expressed in UNITY and used it to verify asynchronous hardware designs. In addition, he is a user of other theorem proving tools such as Otter, SAT solvers, PVS, HOL.

Since 1999 he has been collaborating with Professor Constable and the Nuprl group and has made major contributions to Nuprl's type theory and its application to verification and synthesis of software. Some of his innovations include a type of unguessable atoms which he used to model cryptographic primitives such as nonces and cipher-texts, allowing Nuprl to completely automate the proofs of authentication protocols. He has created the theory of event-orderings and event-classes that comprise the logic-of-events and has supervised the design and construction of the EventML programming language and tools. He and the Nuprl group have successfully used these tools to synthesize correct-by-construction fault-tolerant consensus protocols. As a major user of Nuprl he has influenced many aspects of the design of Nuprl's library and theory maintenance tools. He has devoted much effort towards synthesizing efficient code from proofs. For example, he has discovered how intersection types can be to express a new kind of uniform quantification which is now used throughout Nuprl. Synthesized code extracted from proofs of uniformly quantified theorems is more efficient than code extracted from theorems stated with the usual quantifiers, and uniform quantification is used in the statement of the new result on completeness of constructive first-order logic.