Andreas Blass

TCS Journal 2022 Journal Article

Quantum circuits with classical channels and the principle of deferred measurements

• Yuri Gurevich
• Andreas Blass

TCS Journal 2020 Journal Article

Braided distributivity

• Andreas Blass
• Yuri Gurevich

CSL Conference 2010 Conference Paper

Exact Exploration and Hanging Algorithms

• Andreas Blass
• Nachum Dershowitz
• Yuri Gurevich

Abstract Recent analysis of sequential algorithms resulted in their axiomatization and in a representation theorem stating that, for any sequential algorithm, there is an abstract state machine (ASM) with the same states, initial states and state transitions. That analysis, however, abstracted from details of intra-step computation, and the ASM, produced in the proof of the representation theorem, may and often does explore parts of the state unexplored by the algorithm. We refine the analysis, the axiomatization and the representation theorem. Emulating a step of the given algorithm, the ASM, produced in the proof of the new representation theorem, explores exactly the part of the state explored by the algorithm. That frugality pays off when state exploration is costly. The algorithm may be a high-level specification, and a simple function call on the abstraction level of the algorithm may hide expensive interaction with the environment. Furthermore, the original analysis presumed that state functions are total. Now we allow state functions, including equality, to be partial so that a function call may cause the algorithm as well as the ASM to hang. Since the emulating ASM does not make any superfluous function calls, it hangs only if the algorithm does.

MFCS Conference 2008 Invited Paper

One Useful Logic That Defines Its Own Truth

• Andreas Blass
• Yuri Gurevich

Abstract Existential fixed point logic (EFPL) is a natural fit for some applications, and the purpose of this talk is to attract attention to EFPL. The logic is also interesting in its own right as it has attractive properties. One of those properties is rather unusual: truth of formulas can be defined (given appropriate syntactic apparatus) in the logic. We mentioned that property elsewhere, and we use this opportunity to provide the proof.

CSL Conference 2000 Invited Paper

Background, Reserve, and Gandy Machines

• Andreas Blass
• Yuri Gurevich

Abstract The reserve of a state of an abstract state machine was defined to be a “naked set”. In applications, it may be convenient to have tuples, sets, lists, arrays, etc. defined ahead of time on all elements, including the reserve elements. We generalize the notion of reserve appropriately. As an application, we solve a foundational problem in Gandy’s formalization of mechanical devices.

CSL Conference 2000 Invited Paper

Choiceless Polynominal Time Computation and the Zero-One Law

• Andreas Blass
• Yuri Gurevich

Abstract This paper is a sequel to [ 2 ], a commentary on [ 7 ], and an abridged version of a planned paper that will contain complete proofs of all the results presented here.

CSL Conference 1994 Conference Paper

Is Game Semantics Necessary?

• Andreas Blass

Abstract We discuss the extent to which game semantics is implicit in the basic concepts of linear logic.

CSL Conference 1991 Conference Paper

On the Reduction Theory for Average Case Complexity

• Andreas Blass
• Yuri Gurevich

Abstract This is an attempt to simplify and justify the notions of deterministic and randomized reductions, an attempt to derive these notions from (more or less) first principles.