Provably correct theories of action
We investigate logical formalization of the effects of actions in the situation calculus. We propose a formal criterion against which to evaluate theories of deterministic actions. We show how the criterion provides us a formal foundation upon which to ...
A randomized linear-time algorithm to find minimum spanning trees
We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning ...
Decomposition of magic rewriting
The magic rewriting focuses on relevant data but suffers from additional rules, predicates, and tuples that are generated in search for the relevant data. Reducing the arity of predicates can cut down the number of such rules, predicates, and tuples by ...
On the average communication complexity of asynchronous distributed algorithms
We study the communication complexity of asynchronous distributed algorithms. Such algorithms can generate excessively many messages in the worst case. Nevertheless, we show that, under certain probabilistic assumptions, the expected number of messages ...
NP trees and Carnap's modal logic
In this paper we consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general dag and ...
Three logics for branching bisimulation
Three temporal logics are introduced that induce on labeled transition systems the same identifications as branching bisimulation, a behavioral equivalence that aims at ignoring invisible transitions while preserving the branching structure of systems. ...
Las Vegas algorithms for linear and integer programming when the dimension is small
This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expected O(d2n) + (log n)O(d)d/2+O(1) + O(d4√nlog n) arithmetic operations, as n→∞. The constant factors ...
Nearly optimal algorithms and bounds for multilayer channel routing
This paper presents algorithms for routing channels with L≥2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d + O(√d) tracks to route two-terminal net problems and 2d + O(√d) ...