Yuri Gurevich

From MaRDI portal



List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Interactive classical algorithms: preview
Bulletin of the European Association for Theoretical Computer Science EATCS
2026-05-12Paper
Reversify any sequential algorithm2026-04-29Paper
The umbilical cord of finite model theory
Journal of Logic and Computation
2025-10-29Paper
Primal logic of information
ACM Transactions on Computational Logic
2025-06-04Paper
On a measure of intelligence
Bulletin of the European Association for Theoretical Computer Science EATCS
2025-04-22Paper
On logic and generative AI
Bulletin of the European Association for Theoretical Computer Science EATCS
2024-08-21Paper
The railroad crossing problem: an experiment with instantaneous actions and immediate reactions2024-06-21Paper
Logical foundations: personal perspective
Logic Journal of the IGPL
2024-02-20Paper
What are kets?2024-02-06Paper
scientific article; zbMATH DE number 7800881 (Why is no real title available?)2024-02-06Paper
Metafinite model theory
Lecture Notes in Computer Science
2023-12-12Paper
Primal logic of information2023-07-12Paper
scientific article; zbMATH DE number 7701441 (Why is no real title available?)
(available as arXiv preprint)
2023-06-26Paper
scientific article; zbMATH DE number 7701434 (Why is no real title available?)2023-06-26Paper
scientific article; zbMATH DE number 7701441 (Why is no real title available?)2023-06-26Paper
scientific article; zbMATH DE number 7699974 (Why is no real title available?)
(available as arXiv preprint)
2023-06-22Paper
Software science view on quantum circuit algorithms
Information and Computation
2023-05-19Paper
Negative probabilities: what are they for? <sup>*</sup>
Journal of Physics A: Mathematical and Theoretical
2023-02-10Paper
The 1966 International Congress of Mathematicians: A Micro-memoir
Fundamenta Informaticae
2022-10-07Paper
Novosibirsk algebra and logic in the mid 1960s: A personal perspective2022-09-29Paper
Quantum circuits with classical channels and the principle of deferred measurements
Theoretical Computer Science
2022-05-17Paper
Boris Abramovich Trakhtenbrot
Russian Mathematical Surveys
2022-05-09Paper
Wigner's quasidistribution and Dirac's kets
(available as arXiv preprint)
2022-04-28Paper
Wigner's quasidistribution and Dirac's kets2022-04-28Paper
Logical foundations: personal perspective
Bulletin of the European Association for Theoretical Computer Science EATCS
2022-04-19Paper
Reversify any sequential algorithm
(available as arXiv preprint)
2022-04-19Paper
Reversify any sequential algorithm2022-04-19Paper
Common denominator for value and expectation no-go theorems: extended abstract2021-12-17Paper
Common denominator for value and expectation no-go theorems: extended abstract
(available as arXiv preprint)
2021-12-17Paper
Simple circuit simulations of classical and quantum Turing machines2021-11-21Paper
Means-fit effectivity
(available as arXiv preprint)
2021-08-30Paper
Means-fit effectivity2021-08-30Paper
Quantum circuits with classical channels and the principle of deferred measurements
(available as arXiv preprint)
2021-07-17Paper
Witness algebra and anyon braiding
Mathematical Structures in Computer Science
2020-12-08Paper
Negative probabilities2020-11-24Paper
Negative probabilities: What they are and what they are for
(available as arXiv preprint)
2020-09-22Paper
On quantum computation, anyons, and categories
Outstanding Contributions to Logic
2020-08-06Paper
Braided distributivity
Theoretical Computer Science
2020-01-22Paper
Circuit pedantry
(available as arXiv preprint)
2020-01-13Paper
Circuit pedantry2020-01-13Paper
Unconstrained Church-Turing thesis cannot possibly be true
(available as arXiv preprint)
2020-01-13Paper
Unconstrained Church-Turing thesis cannot possibly be true2020-01-13Paper
scientific article; zbMATH DE number 7150615 (Why is no real title available?)2020-01-13Paper
Negative probabilities. II. What they are and what they are for
(available as arXiv preprint)
2019-12-09Paper
Negative probabilities. II. What they are and what they are for2019-12-09Paper
Fundamentals of p-values: Introduction
(available as arXiv preprint)
2019-07-03Paper
The 1966 International Congress of Mathematicians: A micro-memoir2019-07-03Paper
The 1966 International Congress of Mathematicians: A micro-memoir
(available as arXiv preprint)
2019-07-03Paper
On the rectilinear Steiner problem2019-07-03Paper
scientific article; zbMATH DE number 7075944 (Why is no real title available?)2019-07-03Paper
Fundamentals of p-values: Introduction2019-07-03Paper
Negative probability
(available as arXiv preprint)
2019-07-03Paper
Negative probability2019-07-03Paper
scientific article; zbMATH DE number 7075944 (Why is no real title available?)
(available as arXiv preprint)
2019-07-03Paper
Tailoring recursion for complexity
Automata, Languages and Programming
2019-04-29Paper
Monadic simultaneous rigid E-unification and related problems
Automata, Languages and Programming
2018-07-04Paper
Semantics-to-Syntax Analyses of Algorithms
Turing’s Revolution
2018-04-18Paper
Ordinary interactive small-step algorithms. I
ACM Transactions on Computational Logic
2017-07-12Paper
Ordinary interactive small-step algorithms, II
ACM Transactions on Computational Logic
2017-07-12Paper
Ordinary interactive small-step algorithms, III
ACM Transactions on Computational Logic
2017-07-12Paper
Program termination and well partial orderings
ACM Transactions on Computational Logic
2017-07-12Paper
Abstract state machines capture parallel algorithms: correction and extension
ACM Transactions on Computational Logic
2017-07-12Paper
Abstract state machines capture parallel algorithms
ACM Transactions on Computational Logic
2017-06-13Paper
Sequential abstract-state machines capture sequential algorithms
ACM Transactions on Computational Logic
2017-06-13Paper
Inadequacy of computable loop invariants
ACM Transactions on Computational Logic
2017-06-13Paper
Past present
International Journal of Foundations of Computer Science
2016-06-23Paper
A variation on the zero-one law
Information Processing Letters
2016-06-09Paper
Basic primal infon logic
Journal of Logic and Computation
2016-04-28Paper
Optimal ancilla-free Pauli+V circuits for axial rotations
Journal of Mathematical Physics
2016-01-12Paper
Logic of infons, the propositional case
ACM Transactions on Computational Logic
2015-09-17Paper
Persistent queries in the behavioral theory of algorithms
ACM Transactions on Computational Logic
2015-09-17Paper
Ancilla-approximable quantum state transformations
Journal of Mathematical Physics
2015-05-15Paper
Zero-one laws: thesauri and parametric conditions
Proof, Computation and Agency
2015-04-17Paper
Primal infon logic with conjunctions as sets
Advanced Information Systems Engineering
2014-09-15Paper
Propositional primal logic with disjunction
Journal Of Logic And Computation
2014-04-01Paper
Abstract Hilbertian deductive systems, infon logic, and Datalog
Information and Computation
2014-01-16Paper
Interactive Algorithms 2005 with Added Appendix
Interactive Computation
2013-06-18Paper
Transitive primal infon logic
The Review of Symbolic Logic
2013-06-18Paper
Impugning randomness, convincingly2013-01-28Paper
Hilbertian deductive systems, infon logic, and Datalog2013-01-28Paper
Impugning randomness, convincingly
Studia Logica
2012-10-01Paper
Foundational analyses of computation
Lecture Notes in Computer Science
2012-08-14Paper
From primal infon logic with individual variables to Datalog
Correct Reasoning
2012-07-23Paper
What is an algorithm?
SOFSEM 2012: Theory and Practice of Computer Science
2012-06-15Paper
scientific article; zbMATH DE number 5823846 (Why is no real title available?)2010-12-08Paper
Exact exploration and hanging algorithms
Computer Science Logic
2010-09-03Paper
Content-dependent chunking for differential compression, the local maximum approach
Journal of Computer and System Sciences
2010-05-25Paper
A geometric zero-one law
Journal of Symbolic Logic
2009-09-29Paper
scientific article; zbMATH DE number 5606348 (Why is no real title available?)2009-09-22Paper
scientific article; zbMATH DE number 5605141 (Why is no real title available?)2009-09-19Paper
scientific article; zbMATH DE number 5605119 (Why is no real title available?)2009-09-19Paper
Zero-one laws: thesauri and parametric conditions.2009-09-19Paper
scientific article; zbMATH DE number 5604097 (Why is no real title available?)2009-09-15Paper
scientific article; zbMATH DE number 5604128 (Why is no real title available?)2009-09-15Paper
scientific article; zbMATH DE number 5604063 (Why is no real title available?)2009-09-15Paper
Database query processing using finite cursor machines
Theory of Computing Systems
2009-08-06Paper
When are Two Algorithms the Same?
The Bulletin of Symbolic Logic
2009-06-17Paper
Foundations of Information and Knowledge Systems
Lecture Notes in Computer Science
2009-05-14Paper
Abstract State Machines 2004. Advances in Theory and Practice
Lecture Notes in Computer Science
2009-04-30Paper
Abstract State Machines 2004. Advances in Theory and Practice
Lecture Notes in Computer Science
2009-04-30Paper
A Natural Axiomatization of Computability and Proof of Church's Thesis
The Bulletin of Symbolic Logic
2009-03-25Paper
One Useful Logic That Defines Its Own Truth
Lecture Notes in Computer Science
2009-02-03Paper
Proving Church’s Thesis
Computer Science – Theory and Applications
2008-06-03Paper
Membership Problem for the Modular Group
SIAM Journal on Computing
2008-04-22Paper
Interactive Small-Step Algorithms I: Axiomatization
Logical Methods in Computer Science
2008-04-01Paper
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem
Logical Methods in Computer Science
2008-04-01Paper
Why Sets?
Pillars of Computer Science
2008-03-25Paper
Can abstract state machines be useful in language theory?
Theoretical Computer Science
2007-05-11Paper
Play to Test
Formal Approaches to Software Testing
2007-05-02Paper
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science
2006-10-20Paper
scientific article; zbMATH DE number 5064388 (Why is no real title available?)2006-10-16Paper
Semantic essence of AsmL
Theoretical Computer Science
2005-11-01Paper
Formal Methods for Components and Objects
Lecture Notes in Computer Science
2005-08-22Paper
Partial updates
Theoretical Computer Science
2005-06-10Paper
scientific article; zbMATH DE number 2155182 (Why is no real title available?)2005-04-11Paper
scientific article; zbMATH DE number 2155186 (Why is no real title available?)2005-04-11Paper
scientific article; zbMATH DE number 2155187 (Why is no real title available?)2005-04-11Paper
scientific article; zbMATH DE number 2155189 (Why is no real title available?)2005-04-11Paper
scientific article; zbMATH DE number 2084324 (Why is no real title available?)2004-08-06Paper
Spectra of Monadic Second-Order Formulas with One Unary Function2004-04-07Paper
Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
Journal of Symbolic Logic
2004-03-25Paper
scientific article; zbMATH DE number 2013198 (Why is no real title available?)2003-12-04Paper
On polynomial time computation over unordered structures
Journal of Symbolic Logic
2003-10-06Paper
scientific article; zbMATH DE number 1951184 (Why is no real title available?)2003-07-21Paper
Existential second-order logic over strings
Journal of the ACM
2003-06-25Paper
scientific article; zbMATH DE number 1860676 (Why is no real title available?)2003-05-21Paper
scientific article; zbMATH DE number 1860669 (Why is no real title available?)2003-01-28Paper
Logic with equality: Partisan corroboration and shifted pairing
Information and Computation
2003-01-14Paper
Abstract state machines and computationally complete query languages
Information and Computation
2003-01-14Paper
Fixed Point Logics
The Bulletin of Symbolic Logic
2003-01-13Paper
Definability in Rationals with Real Order in the Background
Journal Of Logic And Computation
2002-11-28Paper
scientific article; zbMATH DE number 1820018 (Why is no real title available?)2002-10-23Paper
Addendum to ``Choiceless polynomial time''
Annals of Pure and Applied Logic
2002-03-25Paper
scientific article; zbMATH DE number 1696889 (Why is no real title available?)2002-01-28Paper
scientific article; zbMATH DE number 1670468 (Why is no real title available?)2001-12-03Paper
The Logic of Choice
Journal of Symbolic Logic
2001-11-23Paper
scientific article; zbMATH DE number 1670467 (Why is no real title available?)2001-11-11Paper
scientific article; zbMATH DE number 1670504 (Why is no real title available?)2001-11-11Paper
scientific article; zbMATH DE number 1670510 (Why is no real title available?)2001-11-11Paper
scientific article; zbMATH DE number 1670511 (Why is no real title available?)2001-11-11Paper
scientific article; zbMATH DE number 1670522 (Why is no real title available?)2001-11-11Paper
The classical decision problem.
Universitext
2001-09-30Paper
scientific article; zbMATH DE number 1512073 (Why is no real title available?)2001-09-04Paper
A new zero-one law and strong extension axioms
Bulletin of the European Association for Theoretical Computer Science EATCS
2001-07-18Paper
Definability and undefinability with real order at the background
Journal of Symbolic Logic
2001-06-18Paper
scientific article; zbMATH DE number 1543044 (Why is no real title available?)2001-02-26Paper
scientific article; zbMATH DE number 1543042 (Why is no real title available?)2001-02-26Paper
scientific article; zbMATH DE number 1543040 (Why is no real title available?)2001-02-26Paper
scientific article; zbMATH DE number 1543039 (Why is no real title available?)2001-02-26Paper
scientific article; zbMATH DE number 1555194 (Why is no real title available?)2001-01-22Paper
scientific article; zbMATH DE number 1860674 (Why is no real title available?)2001-01-01Paper
scientific article; zbMATH DE number 1860671 (Why is no real title available?)2001-01-01Paper
scientific article; zbMATH DE number 1860670 (Why is no real title available?)2001-01-01Paper
scientific article; zbMATH DE number 1860668 (Why is no real title available?)2001-01-01Paper
Choiceless polynomial time
Annals of Pure and Applied Logic
2000-04-13Paper
scientific article; zbMATH DE number 1392308 (Why is no real title available?)2000-01-25Paper
Monadic simultaneous rigid E-unification
Theoretical Computer Science
2000-01-12Paper
scientific article; zbMATH DE number 1354170 (Why is no real title available?)1999-10-28Paper
scientific article; zbMATH DE number 1343482 (Why is no real title available?)1999-09-22Paper
scientific article; zbMATH DE number 1189065 (Why is no real title available?)1998-08-13Paper
Equivalence is in the eye of the beholder
Theoretical Computer Science
1998-07-22Paper
Metafinite model theory
Information and Computation
1998-05-04Paper
scientific article; zbMATH DE number 1086487 (Why is no real title available?)1998-04-01Paper
scientific article; zbMATH DE number 1091108 (Why is no real title available?)1997-11-25Paper
scientific article; zbMATH DE number 1004365 (Why is no real title available?)1997-04-27Paper
On finite rigid structures
Journal of Symbolic Logic
1997-04-21Paper
scientific article; zbMATH DE number 965572 (Why is no real title available?)1997-01-14Paper
Evolving Algebras 1993: Lipari Guide
(available as arXiv preprint)
1996-12-11Paper
scientific article; zbMATH DE number 868108 (Why is no real title available?)1996-08-18Paper
Normal forms for second-order logic over finite structures, and classification of NP optimization problems
Annals of Pure and Applied Logic
1996-07-24Paper
scientific article; zbMATH DE number 868110 (Why is no real title available?)1996-04-21Paper
Matrix Transformation Is Complete for the Average Case
SIAM Journal on Computing
1996-01-08Paper
Tailoring recursion for complexity
Journal of Symbolic Logic
1995-12-19Paper
scientific article; zbMATH DE number 743583 (Why is no real title available?)1995-04-18Paper
Datalog vs first-order logic
Journal of Computer and System Sciences
1995-01-15Paper
scientific article; zbMATH DE number 515739 (Why is no real title available?)1994-06-02Paper
scientific article; zbMATH DE number 512968 (Why is no real title available?)1994-03-10Paper
Randomizing Reductions of Search Problems
SIAM Journal on Computing
1993-12-20Paper
scientific article; zbMATH DE number 176768 (Why is no real title available?)1993-05-18Paper
scientific article; zbMATH DE number 176207 (Why is no real title available?)1993-05-18Paper
scientific article; zbMATH DE number 58300 (Why is no real title available?)1992-09-27Paper
scientific article; zbMATH DE number 8772 (Why is no real title available?)1992-06-25Paper
scientific article; zbMATH DE number 4779 (Why is no real title available?)1992-06-25Paper
scientific article; zbMATH DE number 8775 (Why is no real title available?)1992-06-25Paper
Average case completeness
Journal of Computer and System Sciences
1992-06-25Paper
Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
Journal of the ACM
1990-01-01Paper
scientific article; zbMATH DE number 4101157 (Why is no real title available?)1989-01-01Paper
On matijasevitch's nontraditional approach to search problems
Information Processing Letters
1989-01-01Paper
On the strength of the interpretation method
Journal of Symbolic Logic
1989-01-01Paper
Time polynomial in input or output
Journal of Symbolic Logic
1989-01-01Paper
scientific article; zbMATH DE number 4114620 (Why is no real title available?)1989-01-01Paper
scientific article; zbMATH DE number 4123320 (Why is no real title available?)1988-01-01Paper
scientific article; zbMATH DE number 4080902 (Why is no real title available?)1988-01-01Paper
Monotone versus positive
Journal of the ACM
1987-01-01Paper
scientific article; zbMATH DE number 4055578 (Why is no real title available?)1987-01-01Paper
Expected Computation Time for Hamiltonian Path problem
SIAM Journal on Computing
1987-01-01Paper
Definability by constant-depth polynomial-size circuits
Information and Control
1986-01-01Paper
On the number of active nodes in a multicomputer system
Networks
1986-01-01Paper
Henkin quantifiers and complete problems
Annals of Pure and Applied Logic
1986-01-01Paper
Fixed-point extensions of first-order logic
Annals of Pure and Applied Logic
1986-01-01Paper
The decision problem for linear temporal logic
Notre Dame Journal of Formal Logic
1985-01-01Paper
The decision problem for branching time logic
Journal of Symbolic Logic
1985-01-01Paper
scientific article; zbMATH DE number 4006233 (Why is no real title available?)1985-01-01Paper
A zero-one law for logic with a fixed-point operator
Information and Control
1985-01-01Paper
The monadic theory and the ''next world''
Israel Journal of Mathematics
1984-01-01Paper
scientific article; zbMATH DE number 3868613 (Why is no real title available?)1984-01-01Paper
Equivalence Relations, Invariants, and Normal Forms
SIAM Journal on Computing
1984-01-01Paper
A decidable subclass of the minimal Gödel class with identity
Journal of Symbolic Logic
1984-01-01Paper
The word problem for cancellation semigroups with zero
Journal of Symbolic Logic
1984-01-01Paper
A logic for constant-depth circuits
Information and Control
1984-01-01Paper
scientific article; zbMATH DE number 4008383 (Why is no real title available?)1984-01-01Paper
Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
Journal of the ACM
1984-01-01Paper
The Theory of Ordered Abelian Groups does not have the Independence Property1984-01-01Paper
Decision problem for separated distributive lattices
Journal of Symbolic Logic
1983-01-01Paper
The Word Problem for Lattice-Order Groups
Transactions of the American Mathematical Society
1983-01-01Paper
Random models and the Gödel case of the decision problem
Journal of Symbolic Logic
1983-01-01Paper
Rabin's uniformization problem
Journal of Symbolic Logic
1983-01-01Paper
The monadic theory of <i>ω</i><sub>2</sub>
Journal of Symbolic Logic
1983-01-01Paper
Interpreting second-order logic in the monadic theory of order
Journal of Symbolic Logic
1983-01-01Paper
On the unique satisfiability problem
Information and Control
1982-01-01Paper
Monadic theory of order and topology in ZFC
Annals of Mathematical Logic
1982-01-01Paper
The inference problem for template dependencies
Information and Control
1982-01-01Paper
Prefix classes of krom formulae with identity
Archiv für mathematische Logik und Grundlagenforschung
1982-01-01Paper
Existential interpretation. II
Archiv für Mathematische Logik und Grundlagenforschung
1982-01-01Paper
scientific article; zbMATH DE number 3813598 (Why is no real title available?)1982-01-01Paper
Rigid homogeneous chains
Mathematical Proceedings of the Cambridge Philosophical Society
1981-01-01Paper
Recognizing the Real Line1981-01-01Paper
scientific article; zbMATH DE number 3801594 (Why is no real title available?)1981-01-01Paper
scientific article; zbMATH DE number 3695274 (Why is no real title available?)1980-01-01Paper
Two notes on formalized topology
Fundamenta Mathematicae
1980-01-01Paper
Monadic theory of order and topology. II
Israel Journal of Mathematics
1979-01-01Paper
Modest theory of short chains. I
Journal of Symbolic Logic
1979-01-01Paper
Modest theory of short chains. II
Journal of Symbolic Logic
1979-01-01Paper
scientific article; zbMATH DE number 3573854 (Why is no real title available?)1978-01-01Paper
Intuitionistic logic with strong negation
Studia Logica
1977-01-01Paper
Expanded theory of ordered Abelian groups
Annals of Mathematical Logic
1977-01-01Paper
Monadic theory of order and topology, I
Israel Journal of Mathematics
1977-01-01Paper
Semi-conservative reduction
Archiv für Mathematische Logik und Grundlagenforschung
1976-01-01Paper
The decision problem for standard classes
Journal of Symbolic Logic
1976-01-01Paper
scientific article; zbMATH DE number 3443696 (Why is no real title available?)1974-01-01Paper
A resolving procedure for the extended theory of ordered abelian groups
Siberian Mathematical Journal
1974-01-01Paper
scientific article; zbMATH DE number 3467075 (Why is no real title available?)1973-01-01Paper
scientific article; zbMATH DE number 3463622 (Why is no real title available?)1973-01-01Paper
Remarks on Berger's paper on the domino problem
Siberian Mathematical Journal
1972-01-01Paper
scientific article; zbMATH DE number 3380607 (Why is no real title available?)1972-01-01Paper
A decision problem for decision problems
Algebra and Logic
1971-01-01Paper
The decision problem for the logic of predicates and of operations
Algebra and Logic
1971-01-01Paper
scientific article; zbMATH DE number 3496135 (Why is no real title available?)1970-01-01Paper
scientific article; zbMATH DE number 3316038 (Why is no real title available?)1969-01-01Paper
scientific article; zbMATH DE number 3335023 (Why is no real title available?)1969-01-01Paper
scientific article; zbMATH DE number 3302387 (Why is no real title available?)1967-01-01Paper
scientific article; zbMATH DE number 3264940 (Why is no real title available?)1967-01-01Paper
scientific article; zbMATH DE number 3254893 (Why is no real title available?)1966-01-01Paper
scientific article; zbMATH DE number 3261616 (Why is no real title available?)1966-01-01Paper
scientific article; zbMATH DE number 3285229 (Why is no real title available?)1966-01-01Paper
scientific article; zbMATH DE number 3392429 (Why is no real title available?)1966-01-01Paper
scientific article; zbMATH DE number 3316037 (Why is no real title available?)1966-01-01Paper
Elementary properties of ordered abelian groups
Eleven Papers on Number Theory, Algebra and Functions of a Complex Variable
1965-01-01Paper
scientific article; zbMATH DE number 3460261 (Why is no real title available?)1965-01-01Paper
scientific article; zbMATH DE number 3501768 (Why is no real title available?)1963-01-01Paper
scientific article; zbMATH DE number 3304949 (Why is no real title available?)1963-01-01Paper
McColm conjecture
(available as arXiv preprint)
N/APaper


Research outcomes over time


This page was built for person: Yuri Gurevich