Abstract A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if $A \le _{{\rm{T}}} \emptyset {\rm{'}}$ is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Φ such that if D is a coarse description of X, then ΦD is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees.

The modular group plays an important role in many branches of mathematics. We show that the membership problem for the modular group is decidable in polynomial time. To this end, we develop a new syllable‐based version of the known subgroup‐graph approach. The new approach can be used to prove additional results. We demonstrate this by using it to prove that the membership problem for a free group remains decidable in polynomial time when elements are written in a normal form with exponents.

The authors give a very simple uniform explanation of the persistence of exponential decidability. They follow M. Vardi and P. Wolper's theory (1986) that given a formula gamma of a temporal or dynamic logic, it is important to construct an equivalent automation M/sub gamma /. They characterize the weak monadic theory of the tree; it turns out that weak alternating automata greatly simplify design procedures.>

We have discovered a very strong connection between certain areas of theoretical computer science—the theory of context-free languages and pushdown automata, tiling problems, cellular automata, and vector addition systems—and certain concepts from group theory, topology, and second-order logic. We use these concepts to investigate a rather wide class of graphs which we call context-free graphs. Using the results obtained and Rabin's theorem that the monadic second-order theory of the infinite binary tree is decidable, we are able to show that the monadic second-order theory of any context-free graph is decidable. Cellular automata and vector addition systems are usually considered as involving the grid of integer lattice points in n-dimensional space. We show that such systems make sense on a very general class of graphs and, in contrast to the classical case, all the relevant algorithmic problems concerning such systems are solvable on context-free graphs.