Yuri Gurevich

University of Michigan–Ann Arbor

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Andreas Blass

University of Michigan–Ann Arbor

108

Saharon Shelah

Hebrew University of Jerusalem

Margus Veanes

Microsoft (United States)

Igor Lashkevych

Instituto Politécnico Nacional

Egon Börger

University of Pisa

O. Yu. Titov

Mexican Institute of Petroleum

Erich Grädel

RWTH Aachen University

Wolfram Schulte

Microsoft (United States)

James K. Huggins

Kettering University

АВ

Андрей Воронков

University of Manchester

Cooperative Institutions

Instituto Politécnico Nacional

Microsoft (United States)

Microsoft Research (United Kingdom)

Center for Research and Advanced Studies of the National Polytechnic Institute

University of Michigan–Ann Arbor

Cornell University

Carnegie Mellon University

Utrecht University

Russian Academy of Sciences

RWTH Aachen University

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Generating finite state machines from abstract state machines

Wolfgang Grieskamp Yuri Gurevich Wolfram Schulte Margus Veanes

We give an algorithm that derives a finite state machine (FSM) from a given abstract state machine (ASM) specification. This allows us to integrate ASM specs with the existing tools for test case generation from FSMs. ASM specs are executable but have typically too many, often infinitely many states. We group ASM states into finitely many hyperstates which are the nodes of the FSM. The links of the FSM are induced by the ASM state transitions.

Executable

Abstract state machines

Extended finite-state machine

Finite state

Virtual finite-state machine

10.1145/566172.566190

Cite

Citations (73)

The composition method

Yuri Gurevich Alexis Manaster Ramer Ruth Suzanne Zeitman

The subject of this dissertation is a model-theoretic decidability technique for monadic second-order theories. This technique, which we call the composition method, was used by Saharon Shelah and Yuri Gurevich to extend decidability results for linear orders in some sense as far as possible. Many properties of structures that are of importance in computer science are expressible in monadic second-order logic. There is an close connection between this logic and the theory of finite automata and regular languages. Unfortunately, the composition method has remained relatively unknown. Part of the purpose of this dissertation is to present the technique in an accessible manner, and to show that it provides a clarifying and unifying approach to many decision problems. This is done in part by giving new applications of the technique to problems for which other and varied methods have been developed. Two of these applications concern classes of graphs whose tree-width is bounded by some fixed number, and are novel uses of the composition method in the sense that they allow identification of elements in components of the composition. We also give a new general template for the use of the method (which allows for the identification mentioned above) in the form of theorems that give sufficient conditions for its application.

Tree automaton

Source

Cite

Citations (7)

Monotone versus positive

Journal of the ACM (1987)

Miklós Ajtai Yuri Gurevich

In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P ( P ) is (semantically) monotone in a predicate symbol P on finite structures. Is P ( P ) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of P ? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits.

Counterexample

Constant (computer programming)

Sequence (biology)

Bitwise operation

10.1145/31846.31852

Cite

Citations (105)

Boundary conditions in theory of photothermal processes in solids

Review of Scientific Instruments (2003)

Yuri Gurevich Georgi Logvinov I. M. Lashkevich

In this work general boundary conditions are obtained for the linear nonstationary heat diffusion equation. It is shown that both surface heat conduction and surface heat accumulation must be taken into account for the validity of energy balance at the surface. The latter process is important at fast temperature variation in time.

Heat equation

10.1063/1.1515894

Cite

Citations (5)

ALGORITHMS: A QUEST FOR ABSOLUTE DEFINITIONS

WORLD SCIENTIFIC eBooks (2004)

Andreas Blass Yuri Gurevich

Absolute (philosophy)

10.1142/9789812562494_0051

Cite

Citations (100)

DISTRIBUTED-KNOWLEDGE AUTHORIZATION LANGUAGE JANUARY 2008 REVISION

Yuri Gurevich Itay Neeman

DKAL is an expressive declarative authorization language based on existential fixed-point logic. It is considerably more expressive than existing languages in the literature, and yet feasible. Our query algorithm is within the same bounds of computational complexity as e.g. that of SecPAL. DKAL’s distinguishing features include • explicit handling of knowledge and information, • targeted communication that is beneficial with respect to confidentiality, security, and liability protection, • the flexible use and nesting of functions, which in particular allows principals to quote (to other principals) whatever has been said to them, • flexible built-in rules for expressing and delegating trust, • information order that contributes to succinctness. January 2008 revision of Microsoft Research Technical Report MSR-TR-2007-116 of August 2007.

Succinctness

Executable

Source

Cite

Citations (0)

“The semantics of the C programming language”

Computer Science Logic (2006)

Yuri Gurevich James K. Huggins

10.1007/bfb0049341

Cite

Citations (4)

Optimal no-go theorem on hidden-variable predictions of effect expectations

Physical review. A/Physical review, A (2018)

Andreas Blass Yuri Gurevich

No-go theorems assert that hidden-variable theories, subject to appropriate hypotheses, cannot reproduce the predictions of quantum theory. We examine two species of such theorems, value no-go theorems and expectation no-go theorems. The former assert that hidden-variables cannot match the predictions of quantum theory about the possible values resulting from measurements; the latter assert that hidden-variables cannot match the predictions of quantum theory about the expectation values of measurements. We sharpen the known results of both species, which allows us to clarify the similarities and differences between the two species. We also repair some flaws in existing definitions and proofs.

Hidden variable theory

Value (mathematics)

Several complex variables

10.1103/physreva.97.032126

Cite

Citations (3)

Equivalence relations, invariants, and normal forms

Andreas Blass Yuri Gurevich

Equivalence relation

Equivalence class (music)

Source

Cite