Yuri Gurevich

According to our database1, Yuri Gurevich authored at least 217 papers between 1976 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1997, "Professor Yuri Gurevich is an internationally acclaimed researcher, educator, and leader in the field of foundational issues of computer science.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
An Invitation to Quantum Computing.
Bulletin of the EATCS, 2018

Negative probabilities, II What they are and what they are for.
Bulletin of the EATCS, 2018

Who needs category theory?
Bulletin of the EATCS, 2018

2017
On the Rectilinear Steiner Problem.
Bulletin of the EATCS, 2017

Common Denominator for Value and Expectation No-go Theorems: Extended Abstract.
Proceedings of the Proceedings 14th International Conference on Quantum Physics and Logic, 2017

2016
Basic primal infon logic.
J. Log. Comput., 2016

Past Present.
Int. J. Found. Comput. Sci., 2016

Fundamentals of p-values: Introduction.
Bulletin of the EATCS, 2016

The 1966 International Congress of Mathematicians: A micro-memoir.
Bulletin of the EATCS, 2016

EATCS Fellows' Advice to the Young Theoretical Computer Scientist.
Bulletin of the EATCS, 2016

Inverse privacy.
Commun. ACM, 2016

On Quantum Computation, Anyons, and Categories.
Proceedings of the Martin Davis on Computability, 2016

2015
Impugning alleged randomness.
Proceedings of the 2015 Annual Conference of the North American Fuzzy Information Processing Society (NAFIPS) held jointly with 2015 5th World Conference on Soft Computing (WConSC), 2015

2014
Propositional primal logic with disjunction.
J. Log. Comput., 2014

Primal Infon Logic with Conjunctions as Sets.
Proceedings of the Theoretical Computer Science, 2014

2013
Transitive Primal Infon Logic-ERRATUM.
Rew. Symb. Logic, 2013

Transitive Primal Infon Logic.
Rew. Symb. Logic, 2013

Abstract Hilbertian deductive systems, infon logic, and Datalog.
Inf. Comput., 2013

Explicating SDKs: Uncovering Assumptions Underlying Secure Authentication and Authorization.
Proceedings of the 22th USENIX Security Symposium, Washington, DC, USA, August 14-16, 2013, 2013

dkal ⋆ : Constructing Executable Specifications of Authorization Protocols.
Proceedings of the Engineering Secure Software and Systems - 5th International Symposium, 2013

2012
Impugning Randomness, Convincingly.
Studia Logica, 2012

What Is an Algorithm?
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

Datalog: A Perspective and the Potential.
Proceedings of the Datalog in Academia and Industry - Second International Workshop, 2012

Foundational Analyses of Computation.
Proceedings of the How the World Computes, 2012

From Primal Infon Logic with Individual Variables to Datalog.
Proceedings of the Correct Reasoning, 2012

2011
Logic of infons: The propositional case.
ACM Trans. Comput. Log., 2011

Persistent queries in the behavioral theory of algorithms.
ACM Trans. Comput. Log., 2011

Impugning Randomness, Convincingly.
Bulletin of the EATCS, 2011

Impugning Randomness, Convincingly.
Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

Zero-One Laws: Thesauri and Parametric Conditions.
Proceedings of the Proof, Computation and Agency - Logic at the Crossroads., 2011

2010
Content-dependent chunking for differential compression, the local maximum approach.
J. Comput. Syst. Sci., 2010

Preface.
Electr. Notes Theor. Comput. Sci., 2010

The Tower-of-Babel Problem, and Security Assesment Sharing.
Bulletin of the EATCS, 2010

Hilbertian Deductive Systems, Infon Logic, and Datalog.
Bulletin of the EATCS, 2010

Exact Exploration and Hanging Algorithms.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

Evidential Authorization.
Proceedings of the Future of Software Engineering., 2010

2009
A geometric zero-one law.
J. Symb. Log., 2009

Symbolic Bounded Model Checking of Abstract State Machines.
Int. J. Software and Informatics, 2009

Preface.
Electr. Notes Theor. Comput. Sci., 2009

Teh Logic of Infons.
Bulletin of the EATCS, 2009

When are two algorithms the same?
Bulletin of Symbolic Logic, 2009

Operational Semantics for DKAL: Application and Analysis.
Proceedings of the Trust, 2009

2008
Abstract state machines capture parallel algorithms: Correction and extension.
ACM Trans. Comput. Log., 2008

Program termination and well partial orderings.
ACM Trans. Comput. Log., 2008

Preface.
Electr. Notes Theor. Comput. Sci., 2008

Two Forms of One Useful Logic: Existential Fixed Point Logic and Liberal Datalog.
Bulletin of the EATCS, 2008

A Natural Axiomatization of Computability and Proof of Church's Thesis.
Bulletin of Symbolic Logic, 2008

One Useful Logic That Defines Its Own Truth.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

DKAL: Distributed-Knowledge Authorization Language.
Proceedings of the 21st IEEE Computer Security Foundations Symposium, 2008

Why Sets?
Proceedings of the Pillars of Computer Science, 2008

2007
Ordinary interactive small-step algorithms, III.
ACM Trans. Comput. Log., 2007

Ordinary interactive small-step algorithms, II.
ACM Trans. Comput. Log., 2007

Can abstract state machines be useful in language theory?
Theor. Comput. Sci., 2007

Membership Problem for the Modular Group.
SIAM J. Comput., 2007

Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem.
Logical Methods in Computer Science, 2007

Interactive Small-Step Algorithms I: Axiomatization.
Logical Methods in Computer Science, 2007

Preface.
Electr. Notes Theor. Comput. Sci., 2007

Background of Computation.
Bulletin of the EATCS, 2007

Zero-One Laws: Thesauri and Parametric Conditions.
Bulletin of the EATCS, 2007

Database Query Processing Using Finite Cursor Machines.
Proceedings of the Database Theory, 2007

A Theory of Stream Queries.
Proceedings of the Database Programming Languages, 11th International Symposium, 2007

Proving Church's Thesis.
Proceedings of the Computer Science, 2007

2006
Ordinary interactive small-step algorithms, I.
ACM Trans. Comput. Log., 2006

Preface.
Electr. Notes Theor. Comput. Sci., 2006

Preface.
Electr. Notes Theor. Comput. Sci., 2006

Can Abstract State Machines Be Useful in Language Theory?.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005
Partial updates.
Theor. Comput. Sci., 2005

Preface.
Electr. Notes Theor. Comput. Sci., 2005

Interactive Algorithms 2005.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Play to Test.
Proceedings of the Formal Approaches to Software Testing, 5th International Workshop, 2005

Behavioral Computation Theory 2005.
Proceedings of the 12th International Workshop on Abstract State Machines, 2005

2004
Abstract Communication Model for Distributed Systems.
IEEE Trans. Software Eng., 2004

Why Sets? (Column: Logic in Computer Science).
Bulletin of the EATCS, 2004

Abstract State Machines: An Overview of the Project.
Proceedings of the Foundations of Information and Knowledge Systems, 2004

Observations on the Decidability of Transitions.
Proceedings of the Abstract State Machines 2004. Advances in Theory and Practice, 2004

Intra-step Interaction.
Proceedings of the Abstract State Machines 2004. Advances in Theory and Practice, 2004

2003
Abstract state machines capture parallel algorithms.
ACM Trans. Comput. Log., 2003

Strong extension axioms and Shelah's zero-one law for choiceless polynomial time.
J. Symb. Log., 2003

Algorithms: A Quest for Absolute Definitions.
Bulletin of the EATCS, 2003

Spectra of Monadic Second-Order Formulas with One Unary Function.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Semantic Essence of AsmL.
Proceedings of the Formal Methods for Components and Objects, 2003

Partial Updates Exploration II.
Proceedings of the Abstract State Machines, 2003

2002
Definability in Rationals with Real Order in the Background.
J. Log. Comput., 2002

On Polynomial Time Computation over Unordered Structures.
J. Symb. Log., 2002

Algorithms vs. Machines.
Bulletin of the EATCS, 2002

Pairwise Testing.
Bulletin of the EATCS, 2002

Fixed point logics.
Bulletin of Symbolic Logic, 2002

Generating finite state machines from abstract state machines.
Proceedings of the International Symposium on Software Testing and Analysis, 2002

High-Level Executable Specification of the Universal Plug and Play Architecture.
Proceedings of the 35th Hawaii International Conference on System Sciences (HICSS-35 2002), 2002

2001
Inadequacy of computable loop invariants.
ACM Trans. Comput. Log., 2001

Partial Updates: Exploration.
J. UCS, 2001

Addendum to "Choiceless Polynomial Time": Ann. Pure Appl. Logic 100 (1999) 141-187.
Ann. Pure Appl. Logic, 2001

Logician in the Land of OS: Abstract State Machines in Microsoft.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

The Abstract State Machine Paradigm: What Is in and What Is out.
Proceedings of the Perspectives of System Informatics, 2001

The Sequential ASM Thesis.
Current Trends in Theoretical Computer Science, 2001

From Invariants to Canonization.
Current Trends in Theoretical Computer Science, 2001

Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand.
Current Trends in Theoretical Computer Science, 2001

The Value, if Any, of Decidability.
Current Trends in Theoretical Computer Science, 2001

AMAST'91 Banquet Talk.
Current Trends in Theoretical Computer Science, 2001

Herbrand's Theorem and Equational Reasoning: Problems and Solutions.
Current Trends in Theoretical Computer Science, 2001

The Underlying Logic of Hoare Logic.
Current Trends in Theoretical Computer Science, 2001

2000
Sequential abstract-state machines capture sequential algorithms.
ACM Trans. Comput. Log., 2000

Decidability and complexity of simultaneous rigid E-unification with one variable and related results.
Theor. Comput. Sci., 2000

Definability and Undefinability with Real Order at The Background.
J. Symb. Log., 2000

The Logic of Choice.
J. Symb. Log., 2000

Existential second-order logic over strings.
J. ACM, 2000

The Underlying Logic of Hoare Logic.
Bulletin of the EATCS, 2000

A New Zero-One Law and Strong Extension Axioms.
Bulletin of the EATCS, 2000

Choiceless Polynominal Time Computation and the Zero-One Law.
Proceedings of the Computer Science Logic, 2000

Background, Reserve, and Gandy Machines.
Proceedings of the Computer Science Logic, 2000

Investigating Java Concurrency Using Abstract State Machines.
Proceedings of the Abstract State Machines, 2000

Partially Ordered Runs: A Case Study.
Proceedings of the Abstract State Machines, 2000

Abstract State Machines and Computationally Complete Query Languages.
Proceedings of the Abstract State Machines, 2000

Using Abstract State Machines at Microsoft: A Case Study.
Proceedings of the Abstract State Machines, 2000

Invited Talk: ASM Formalware in the Software Engineering Cycle.
Proceedings of the Algebraic Methodology and Software Technology. 8th International Conference, 2000

1999
Monadic Simultaneous Rigid E-unification.
Theor. Comput. Sci., 1999

Logic with Equality: Partisan Corroboration and Shifted Pairing.
Inf. Comput., 1999

The Sequential ASM Thesis.
Bulletin of the EATCS, 1999

Choiceless Polynomial Time.
Ann. Pure Appl. Logic, 1999

1998
A Variation on the Zero-One Law.
Inf. Process. Lett., 1998

The Decidability of Simultaneous Rigid E-Unification with One Variable.
Proceedings of the Rewriting Techniques and Applications, 9th International Conference, 1998

The Complexity of Query Reliability.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

Existential Second-Order Logic over Strings.
Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1997
Equivalence is in the Eye of the Beholder.
Theor. Comput. Sci., 1997

Formalizing Database Recovery.
J. UCS, 1997

Recursive Abstract State Machines.
J. UCS, 1997

Gurevich Abstract State Machines and Schoenhage Storage Modification Machines.
J. UCS, 1997

The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs.
J. UCS, 1997

From Invariants to Canonization.
Bulletin of the EATCS, 1997

Monadic Simultaneous Rigid E-Unification and Related Problems.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Syntax vs. Semantics on Finite Structures.
Proceedings of the Structures in Logic and Computer Science, 1997

The Classical Decision Problem
Perspectives in Mathematical Logic, Springer, 1997

1996
On Finite Rigid Structures.
J. Symb. Log., 1996

Herbrand's Theorem and Equational Reasoning: Problems and Solutions.
Bulletin of the EATCS, 1996

Normal Forms for Second-Order Logic over Finite Structures, and Classification of NP Optimization Problems.
Ann. Pure Appl. Logic, 1996

1995
Matrix Transformation Is Complete for the Average Case.
SIAM J. Comput., 1995

Tailoring Recursion for Complexity.
J. Symb. Log., 1995

The Value, if any, of Decidability.
Bulletin of the EATCS, 1995

Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand.
Bulletin of the EATCS, 1995

A Tribute to Dirk van Dalen - Preface.
Ann. Pure Appl. Logic, 1995

The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions.
Proceedings of the Computer Science Logic, 9th International Workshop, 1995

Formalizing Recovery in Transaction-Oriented Database Systems.
COMAD, 1995

1994
Logic activities in Europe.
SIGACT News, 1994

Datalog vs First-Order Logic.
J. Comput. Syst. Sci., 1994

McColm's Conjecture
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Metafinite Model Theory.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

Evolving Algebras and Partial Evaluation.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

Evolving Algebras.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

Evolving Algebras and Linear Time Hierarchy.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

Tailoring Recursing for Complexity.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

1993
Zero-One Laws.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Evolving Algebras: an Attempt to Discover Semantics.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On the Classical Decision Problem.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

The challenger-Solver Game: variations on the Theme of P=NP.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Infinite Games.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On Kolmogorov Machines and Related Issues.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Logic in Computer Science.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Curb Your Theory! A Circumspective Approach for Inclusive Interpretation of Disjunctive Information.
Proceedings of the 13th International Joint Conference on Artificial Intelligence. Chambéry, France, August 28, 1993

ERRATA to "The Semantics of the C Programming Language".
Proceedings of the Computer Science Logic, 7th Workshop, 1993

The bakery algorithm: yet another specification and verification.
Proceedings of the Specification and validation methods, 1993

Group membership protocol: specification and verification.
Proceedings of the Specification and validation methods, 1993

Evolving algebras 1993: Lipari guide.
Proceedings of the Specification and validation methods, 1993

1992
Zero-One Laws.
Bulletin of the EATCS, 1992

The Semantics of the C Programming Language.
Proceedings of the Computer Science Logic, 6th Workshop, 1992

1991
Average Case Completeness.
J. Comput. Syst. Sci., 1991

Average Case Complexity.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Randomizing Reductions of Search Problems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

1990
Preface
Inf. Comput., 1990

On the Classical Desicion Problem.
Bulletin of the EATCS, 1990

Matrix Decomposition Problem Is Complete for the Average Case
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On the Reduction Theory for Average Case Complexity.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989
Time Polynomial in Input or Output.
J. Symb. Log., 1989

On the Strength of the Interpretation Method.
J. Symb. Log., 1989

On Matijasevitch's Nontraditional Approach to Search Problems.
Inf. Process. Lett., 1989

The Logic in computer science Column.
Bulletin of the EATCS, 1989

Logic in Computer Science Column.
Bulletin of the EATCS, 1989

Datalog vs. First-Order Logic
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Nearly Linear Time.
Proceedings of the Logic at Botik '89, 1989

Algebraic Operational Semantics and Occam.
Proceedings of the CSL '89, 1989

1988
Logic in computer Science Column.
Bulletin of the EATCS, 1988

Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987
Expected Computation Time for Hamiltonian Path Problem.
SIAM J. Comput., 1987

Monotone versus positive.
J. ACM, 1987

Algenraic Operational Semantics.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987

Complete and Incomplete Randomized NP Problems
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Algebraic Operational Semantics and Modula-2.
Proceedings of the CSL '87, 1987

Existential Fixed-Point Logic.
Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986
On the number of active nodes in a multicomputer system.
Networks, 1986

Definability by Constant-Depth Polynomial-Size Circuits
Information and Control, 1986

Fixed-point extensions of first-order logic.
Ann. Pure Appl. Logic, 1986

Henkin quantifiers and complete problems.
Ann. Pure Appl. Logic, 1986

1985
The decision problem for linear temporal logic.
Notre Dame Journal of Formal Logic, 1985

The Decision Problem for Branching Time Logic.
J. Symb. Log., 1985

A Zero-One Law for Logic with a Fixed-Point Operator
Information and Control, 1985

Fixed-Point Extensions of First-Order Logic
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
A Logic for Constant-Depth Circuits
Information and Control, April, 1984

The Word Problem for Cancellation Semigroups with Zero.
J. Symb. Log., 1984

A Decidable Subclass of the Minimal Godel Class with Identity.
J. Symb. Log., 1984

Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems.
J. ACM, 1984

1983
Random Models and the Godel Case of the Decision Problem.
J. Symb. Log., 1983

Rabin's Uniformization Problem.
J. Symb. Log., 1983

Interpreting Second-Order Logic in the Monadic Theory of Order.
J. Symb. Log., 1983

The Monadic Theory of omega12.
J. Symb. Log., 1983

Decision Problem for Separated Distributive Lattices.
J. Symb. Log., 1983

Equivalence relations, invariants, and normal forms.
Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983

Algebras of Feasible Functions
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
The Inference Problem for Template Dependencies
Information and Control, 1982

On the Unique Satisfiability Problem
Information and Control, 1982

Trees, Automata, and Games
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

The Inference Problem for Template Dependencies.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

Can Message Buffers be Characterized in Linear Temporal Logic?
Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1982

1980
Existential interpretation. II.
Arch. Math. Log., 1980

Prefix classes of krom formulae with identity.
Arch. Math. Log., 1980

1979
Modest Theory of Short Chains. II.
J. Symb. Log., 1979

Modest Theory of Short Chains. I.
J. Symb. Log., 1979

1977
Semi-conservative reduction.
Arch. Math. Log., 1977

1976
The Decision Problem for Standard Classes.
J. Symb. Log., 1976


  Loading...