A parallel method for computing Boolean expressions based on the properties of finite free Boolean algebras is presented. We also show how various finite combinatorial objects can be codded in the formalism of Boolean algebras and counted by this procedure. Particularly, using a translation of first order predicate formulas to propositional formulas, we give a […]

October 29, 2013 by hgpu

As Graphics Processing Units (GPUs) have gained in capability and GPU development environments have matured, developers are increasingly turning to the GPU to off-load the main host CPU of numerically-intensive, parallelizable computations. Modern GPUs feature hundreds of cores, and offer programming niceties such as double-precision floating point, and even limited recursion. This shift from CPU […]

May 1, 2013 by hgpu

We consider the problem of computing reachability probabilities: given a Markov chain, an initial state of the Markov chain, and a set of goal states of the Markov chain, what is the probability of reaching any of the goal states from the initial state? This problem can be reduced to solving a linear equation Ax=b […]

October 25, 2012 by hgpu

Many programming languages and tools, ranging from grep to the Java String library, contain regular expression matchers. Rather than first translating a regular expression into a deterministic finite automaton, such implementations typically match the regular expression on the fly. Thus they can be seen as virtual machines interpreting the regular expression much as if it […]

August 17, 2011 by hgpu