TY - GEN AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Davies, Jessica ID - 5443 SN - 2664-1690 TI - A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs ER - TY - JOUR AB - We present here the first integer-based algorithm for constructing a well-defined lattice sphere specified by integer radius and integer center. The algorithm evolves from a unique correspondence between the lattice points comprising the sphere and the distribution of sum of three square numbers in integer intervals. We characterize these intervals to derive a useful set of recurrences, which, in turn, aids in efficient computation. Each point of the lattice sphere is determined by resorting to only a few primitive operations in the integer domain. The symmetry of its quadraginta octants provides an added advantage by confining the computation to its prima quadraginta octant. Detailed theoretical analysis and experimental results have been furnished to demonstrate its simplicity and elegance. AU - Biswas, Ranita AU - Bhowmick, Partha ID - 5804 IS - 4 JF - Theoretical Computer Science SN - 0304-3975 TI - From prima quadraginta octant to lattice sphere through primitive integer operations VL - 624 ER - TY - JOUR AU - Biswas, Ranita AU - Bhowmick, Partha ID - 5807 IS - 11 JF - Theoretical Computer Science SN - 0304-3975 TI - On different topological classes of spherical geodesic paths and circles inZ3 VL - 605 ER - TY - JOUR AU - Biswas, Ranita AU - Bhowmick, Partha ID - 5808 IS - 6-8 JF - The Visual Computer SN - 0178-2789 TI - Layer the sphere VL - 31 ER - TY - JOUR AB - Transcription of eukaryotic protein-coding genes commences with the assembly of a conserved initiation complex, which consists of RNA polymerase II (Pol II) and the general transcription factors, at promoter DNA. After two decades of research, the structural basis of transcription initiation is emerging. Crystal structures of many components of the initiation complex have been resolved, and structural information on Pol II complexes with general transcription factors has recently been obtained. Although mechanistic details await elucidation, available data outline how Pol II cooperates with the general transcription factors to bind to and open promoter DNA, and how Pol II directs RNA synthesis and escapes from the promoter. AU - Sainsbury, Sarah AU - Bernecky, Carrie A AU - Cramer, Patrick ID - 594 IS - 3 JF - Nature Reviews Molecular Cell Biology TI - Structural basis of transcription initiation by RNA polymerase II VL - 16 ER -