A subset algorithm for deterministic FSMs within determinisitic PDAs

Given a family F of k sets with cardinalities s₁, s₂, . . ., s_k and N = [EQUATION], we show that the size of the partial order graph induced by the subset relation (called the subset graph) is [EQUATION], where B = log (N/ log² N). This implies a ...

The distance to monotonicity of a sequence of n numbers is the minimum number of entries whose deletion leaves an increasing sequence. We give the first deterministic streaming algorithm that approximates the distance to monotonicity within a 1 + ε ...

We present a deterministic (1+o(1))-approximation O(n^1/2+o(1)+D^1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (...