Articles Grouped by Research Areas

An entry gives only the title and a URL to a fuller description in Annotated Articles. Admittedly, the categorization is somewhat arbitrary. The intersection between two categories is not necessarily empty. Abstract state machines & behavioral computation theory Algebra and model theory AI, automated reasoning and related Average-case computational complexity Classical decision problem and related Computational complexity Database theory including stream processing Distributed systems Finite model theory Game theory Logic and foundations of mathematics Operation research Philosophy Programming theory Specifications, testing and related Temporal logic Odds and ends Abstract State Machines and Behavioral Computation Theory 176 General Interactive Small Step Algorithms 174 Interactive Algorithms 2005 171 Ordinary Interactive Small-Step Algorithms, III 170 Ordinary Interactive Small-Step Algorithms, II 169a Semantic Essence of AsmL: Extended Abstract 169 Semantic Essence of AsmL 168 Observations on the Decidability of Transitions 167 Intra-Step Interaction 166 Ordinary Interactive Small-Step Algorithms, I 165 Abstract State Machines: An Overview of the Project 164 Algorithms: A Quest for Absolute Definitions 161 Partial Updates 159 Abstract Communication Model for Distributed Systems 158 Algorithms vs. Machines 157 Abstract State Machines Capture Parallel Algorithms 155 Partial Updates: Exploration 155 Toward Industrial Strength Abstract State Machines 154 Generating Finite State Machines from Abstract State Machines 153 Universal Plug and Play Machine Models 151 Logician in the land of OS: Abstract State Machines at Microsoft 150a A Quick Update on the Open Problems in article [150] 150 On Polynomial Time Computation Over Unordered Structures 145-2 Table ASMs 145-1 Using Abstract State Machines at Microsoft: A Case Study 144 Choiceless Polynomial Time Computation and the Zero-One Law 143 Background, Reserve, and Gandy Machines 141b Finite Work 141a Sequential Abstract State Machines capture Sequential Algorithms Russian translation 141 Sequential Abstract State Machines capture Sequential Algorithms 140 Investigating Java Concurrency Using Abstract State Machines 139 Abstract state machines and computationally complete query languages 138 Partially Ordered Runs: a Case Study 137 Typed Abstract State Machines 136 The Sequential ASM Thesis 129 May 1997 Draft of the ASM Guide 122 A Formal Approach to Recovery in Transaction-Oriented Database Systems 121 Gurevich Abstract State Machines and Schoenhage Storage Modification Machines 120 Choiceless Polynomial Time 118 Recursive Abstract State Machines 118 The Linear Time Hierarchy Theorems for RAMs and Abstract State Machines 117 Equivalence is in the Eye of the Beholder 116 The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions 112 Evolving Algebras 111 Evolving Algebras and Partial Evaluation 110 Evolving Algebras and Linear Time Hierarchy 107 The Bakery Algorithm: Yet Another Specification and Verification 106 Group Membership Protocol: Specification and Verification 103 Evolving Algebra 1993: Lipari Guide 98 The Semantics of the C Programming Language 92 Evolving Algebras: An Introductory Tutorial 89 Algebraic Operational Semantics and Occam 77 Algebraic operational semantics and Modula-2 75 Algorithms in the world of bounded resources 64.5 A New Thesis 60.5 Reconsidering Turing's thesis (toward more realistic semantics of programs) Algebra and Model Theory 175. Membership Problem for Modular Group 147 Definability in Rationals with Real Order in the Background 144 Choiceless Polynomial Time Computation and the Zero-One Law 135 The Logic of Choice 134 Existential Second-Order Logic over Strings 130 Definability and Undefinability with Real Order at the Background 109 Metafinite Model Theory 97 Matrix Transformation is Complete for the Average Case 88 Matrix Decomposition Problem is Complete for the Average Case 79 On the strength of the interpretation method 64 Monadic second-order theories 57 The monadic theory and the `next world' 53 The word problem for cancellation semigroups with zero 52 The theory of ordered abelian groups does not have the independence property 49 The word problem for lattice-ordered groups 47 Rabin's Uniformization Problem 46 Interpreting second-order logic in the monadic theory of order 45 The monadic theory of ω2 44. Decision problem for separated distributive lattices 37 Monadic theory of order and topology in ZFC 36 Existential interpretation, II 34 Crumbly spaces 33 Elementary theory of automorphism groups of doubly homogeneous chains 32 Rigid homogeneous chains 31 Recognizing the real line 30 Two notes on formalized topology 29 Modest theory of short chains, II 28 Modest theory of short chains, I 27 Monadic theory of order and topology, II 26 Monadic theory of order and topology, I 25 Expanded theory of ordered abelian groups 19 The decision problem for the expanded theory of ordered abelian groups 13 The decision problem for logic of predicates and operations 12 The decision problem for some algebraic theories. Doctor of math. thesis 11 A new decision procedure for the theory of ordered abelian groups 10 Lattice-ordered abelian groups and K-lineals 9 Hereditary undecidability of the theory of lattice-ordered abelian groups 8 The word problem for some classes of semigroups 4 Existential interpretation 3 Elementary properties of ordered abelian groups. Ph.D. Thesis 2 Universal equivalence of ordered abelian groups 1 Groups covered by proper characteristic subgroups AI 128b Monadic Simultaneous Rigid E-Unification 128a Monadic Simultaneous Rigid E-Unification and Related Problems 127b Decidability and Complexity of Simultaneous Rigid E-Unification with One Variable and Related Results 127a The Decidability of Simultaneous Rigid E-Unification with One Variable 126 Logic with Equality: Partisan Corroboration and Shifted Pairing 125 Herbrand's Theorem and Equational Reasoning: Problems and Solutions 99 Curb Your Theory! A Circumscriptive Approach for Inclusive Interpretation of Disjunctive Information Average Case Computational Complexity 97 Matrix Transformation is Complete for the Average Case 96 Randomizing Reductions of Search Problems 94 Average Case Complexity 93 On the Reduction Theory for Average-Case Complexity 88 Matrix Decomposition Problem is Complete for the Average Case 85 The Challenger-Solver game: Variations on the Theme of P=?NP 76 Average case completeness 71 Expected computation time for Hamiltonian Path Problem Classical Decision Problem and Related Stuff 115 The Value, if any, of Decidability 91 On the Classical Decision Problem 58 A decidable subclass of the minimal Goedel case with identity 48 Random models and the Goedel case of the decision problem 39 A review of two books on the decision problem 36 Existential interpretation, II 35 Prefix classes of Krom formulas with identity 22 Semi-conservative reduction 21 The decision problem for standard classes 20 The decision problem for first-order logic 18 Formulas with one universal quantifier 17 Strengthening a result of Suranyi 16 Minsky machines and the AEA&E* case of the decision problem 15 Minsky machines and the AEA&E* case of the decision problem 14 The decision problem for decision problems 12 The decision problem for some algebraic theories. Doctor of math. thesis 7 Recognizing satisfiability of predicate formulas 6 The decision problem for predicate logic 5 On the decision problem for pure predicate logic 4 Existential interpretation Computational Complexity 175. Membership Problem for Modular Group 146 Inadequacy of Computable Loop Invariants 139 Abstract state machines and computationally complete query languages 134 Existential Second-Order Logic over Strings 133 The Complexity of Query Reliability 132 A Variation on the Zero-One Law 131 From Invariants to Canonization 121 Gurevich Abstract State Machines and Schoenhage Storage Modification Machines 120 Choiceless Polynomial Time 118 The Linear Time Hierarchy Theorems for RAMs and Abstract State Machines 115 The Value, if any, of Decidability 110 Evolving Algebras and Linear Time Hierarchy 104 Tailoring Recursion for Complexity 87 Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space 85 The Challenger-Solver game: Variations on the Theme of P=?NP 82 Nearly linear time 81 On Matiyasevich's non-traditional approach to search problems 80 Time polynomial in input or output 78 On Kolmogorov machines and related issues 56 Equivalence relations, invariants, and normal forms, II 55 Equivalence relations, invariants, and normal forms 54 Solving NP-hard problems on graphs that are almost trees, and an application to facility location problems 42 On the unique satisfiability problem Database theory including stream processing 189 A Theory of Stream Queries 184 Database query processing using finite cursor machines 133 The Complexity of Query Reliability 122 A Formal Approach to Recovery in Transaction-Oriented Database Systems 41 The inference problem for template dependencies Distributed Systems 159 Abstract Communication Model for Distributed Systems 153 Universal Plug and Play Machine Models 140 Investigating Java Concurrency Using Abstract State Machines 138 Partially Ordered Runs: a Case Study 122 A Formal Approach to Recovery in Transaction-Oriented Database Systems 117 Equivalence is in the Eye of the Beholder 116 The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions 107 The Bakery Algorithm: Yet Another Specification and Verification 106 Group Membership Protocol: Specification and Verification 103 Evolving Algebra 1993: Lipari Guide 68 On the number of active nodes in a multicomputer system Finite Model Theory 162. Spectra of Monadic Second-Order Formulas with One Unary Function 152 Fixed Point Logics 150a A Quick Update on the Open Problems in article [150] 150 On Polynomial Time Computation Over Unordered Structures 149 Strong Extension Axioms and Shelah's Zero-One Law for Choiceless Polynomial Time 148 New Zero-One Law and Strong Extension Axioms 144 Choiceless Polynomial Time Computation and the Zero-One Law 139 Abstract state machines and computationally complete query languages 135 The Logic of Choice 134 Existential Second-Order Logic over Strings 133 The Complexity of Query Reliability 131 From Invariants to Canonization 124 Syntax vs. Semantics on Finite Structures 120 Choiceless Polynomial Time 115 The Value, if any, of Decidability 113 On Rigid Structures 109 Metafinite Model Theory 108 McColm's Conjecture 104 Tailoring Recursion for Complexity 95 Zero-One Laws 90 On Finite Model Theory 83 Datalog vs First-Order Logic 74 Logic and the Challenge of Computer Science 73 Existential fixed-point logic 72 Monotone versus positive 70 Fixed-point extensions of first-order logic 67 Definability by constant-depth polynomial-size circuits 66 Henkin quantifiers and complete problems 65 A zero-one law for logic with a fixed-point operator 60 Toward logic tailored for computational complexity 59 A logic for constant depth circuits 51 Algebras of feasible functions 48 Random models and the Goedel case of the decision problem Game Theory 173 Play to Test 86 Games people play 85 The Challenger-Solver game: Variations on the Theme of P=?NP 84 Infinite games 40 Automata, trees, and games Logic and Foundations of Mathematics 172 Why Sets? 164 Algorithms: A Quest for Absolute Definitions 152 Fixed Point Logics 142 The Underlying Logic of Hoare Logic 135 The Logic of Choice 127b Decidability and Complexity of Simultaneous Rigid E-Unification with One Variable and Related Results 127a The Decidability of Simultaneous Rigid E-Unification with One Variable 126 Logic with Equality: Partisan Corroboration and Shifted Pairing 125 Herbrand's Theorem and Equational Reasoning: Problems and Solutions 123 Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand 109 Metafinite Model Theory 24 Intuitionistic logic with strong negation Operation Research 38. Homogeneous optimal fleet 23. Constructing an optimal fleet for a transportation schedule Philosophy 172 Why Sets? 123 Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand Programming Theory 169a Semantic Essence of AsmL: Extended Abstract 169 Semantic Essence of AsmL 155 Toward Industrial Strength Abstract State Machines 146 Inadequacy of Computable Loop Invariants 142 The Underlying Logic of Hoare Logic 140 Investigating Java Concurrency Using Abstract State Machines 98 The Semantics of the C Programming Language 89 Algebraic Operational Semantics and Occam 77 Algebraic operational semantics and Modula-2 50. Critiquing a critique of Hoare's programming logics Specifications, Testing and Related Stuff 173 Play to Test 168 Observations on the Decidability of Transitions 163 Scenario-oriented Modeling in AsmL and Its Instrumentation for Testing 160 Pairwise Testing 154 Generating Finite State Machines from Abstract State Machines 153 Universal Plug and Play Machine Models 145 Using Abstract State Machines at Microsoft: A Case Study 117 Equivalence is in the Eye of the Beholder 107 The Railroad Crossing Problem: An Experiment with Instantaneous Actions and Immediate Reactions 107 The Bakery Algorithm: Yet Another Specification and Verification 106 Group Membership Protocol: Specification and Verification 89 Algebraic Operational Semantics and Occam 98 The Semantics of the C Programming Language Temporal Logic 63 The decision problem for branching time logic 62 To the decision problem for branching time logic 61 The decision problem for linear temporal logic 43 Can message buffers be characterized in linear temporal logic? Odds and Ends 105 Logic Activities in Europe 101 The AMAST Phenomenon 69 What does O(n) mean?