Parthenon: A parallel theorem prover for non-horn clauses

We describe a parallel resolution theorem prover, called Parthenon, that handles full first order logic. Although there has been much work on parallel implementations of logic programming languages, Parthenon is the first general purpose theorem prover to be developed for a multiprocessor. The system is based on a modification of Warren's SRI model for or-parallelism and implements a variant of Loveland's model elimination procedure. It has been evaluated on various shared memory multiprocessors including a 16-processor Encore Multimax and IBM's 64-processor RP3. We have found that many theorem proving problems exhibit a great deal of potential parallelism. Parthenon has been able to exploit much of this parallelism, producing both good absolute run times and near-linear speedup curves in many cases.This research was partially supported by NSF grant CCR-87-226-33. An earlier version of this paper appeared in the Fourth IEEE Symposium on Logic in Computer Science, Asilomar, CA, June 1989. D.E.L. was partially supported by an NSF graduate fellowship. S.M. was partially supported by an IBM graduate fellowship.     

A parallel approach for theorem proving in prepositional logic

In this paper, the divide-and-conquer strategy and a pipelining discipline are applied to theorem proving in propositional logic. The strategy is itself logically complete and sound. Based on this strategy a parallel proof procedure can be constructed. With a pipelined execution model, we show that the processing time using our parallel approach to solve such an NP-complete problem is of O(mn), where m is the number of clauses and n is the number of distinct Boolean variables in the given formula. The approach is simpler than those using explicit inference rules, since the deductions are performed implicitly by only simple checking and deleting operations on each clause.     

Uniform Tauberian theorem in differential games

This paper establishes the uniform Tauberian theorem for differential zero-sum games. Under rather mild conditions imposed on the dynamics and running cost, two parameterized families of games are considered, i.e., the ones with the payoff functions defined as the Cesaro mean and Abel mean of the running cost. The asymptotic behavior of value in these games is investigated as the game horizon tends to infinity and the discounting parameter tends to zero, respectively. It is demonstrated that the uniform convergence of value on an invariant subset of the phase space in one family implies the uniform convergence of value in the other family and that the limit values in the both families coincide. The dynamic programming principle acts as the cornerstone of proof.     

The parallel projection operators of a nonlinear feedback system

This paper defines and studies a pair of nonlinear parallel projection operators associated with a nonlinear feedback system. These operators have been seen to play an important role in the robustness and design of linear systems especially in the theory of the gap metric, the use of weighted gaps in control system design and Glover-McFarlane loop-shaping. We show that the input-output L₂-stability of a feedback system amounts to a ‘coordinatization’ of the input and output spaces, which is also equivalent to the existence of a pair of nonlinear parallel projection operators onto the graph of the plant and the inverse graph of the controller respectively. These projections are shown to have equal norms whenever one of the feedback elements is linear. A bound on this norm is given in the case of passive systems with unity negative feedback.     

A metric for positional games

We define an extended real-valued metric, ρ, for positional games and prove that this class of games is a topological semigroup. We then show that two games are finitely separated iff they are path-connected and iff two closely related Conway games are equivalent. If two games are at a finite distance then this distance is bounded by the maximum difference of any two atoms found in the games. We may improve on this estimate when two games have the same form, as given by a form match. Finally, we show that if ρ(G,H)=∞ then for all X we have G+X H+X, a step towards proving cancellation for positional games.     

GPU-based parallel solver via the Kantorovich theorem for the nonlinear Bernstein polynomial systems

This paper proposes a parallel solver for the nonlinear systems in Bernstein form based on subdivision and the Newton-Raphson method, where the Kantorovich theorem is employed to identify the existence of a unique root and guarantee the convergence of the Newton-Raphson iterations. Since the Kantorovich theorem accommodates a singular Jacobian at the root, the proposed algorithm performs well in a multiple root case. Moreover, the solver is designed and implemented in parallel on Graphics Processing Unit(GPU) with SIMD architecture; thus, efficiency for solving a large number of systems is improved greatly, an observation validated by our experimental results.     

A theorem for locating eigenvalues

The primary conclusion derived in this paper is that the leading principal minors of matrixB-ωA (whereB is a symmetric positive definite matrix andA is Hermite matrix) have properties similar to those of Sturm sequences, which is the theoretical basis of the Determinant Search Method for solving the eigenvalue-problem of damped structural systems [1]–[5], correcting the errors in a statement given by K. K. Gupta in [1]–[5].     

A projection method for closed-loop identification

A new method for closed-loop identification that allows fitting the model to the data with arbitrary frequency weighting is described and analyzed. Just as the direct method, this new method is applicable to systems with arbitrary feedback mechanisms. This is in contrast to other methods, such as the indirect method and the two-stage method, that assume linear feedback. The finite sample behavior of the proposed method is illustrated in a simulation study.     

A Generate-Test-Aggregate parallel programming library for systematic parallel programming

The Generate-Test-Aggregate (GTA for short) algorithm is modeled following a simple and straightforward programming pattern, for combinatorial problems. First, generate all candidates; second, test and filter out invalid ones; finally, aggregate valid ones to make the final result. These three processing steps can be specified by three building blocks namely, generator, tester, and aggregator. Despite the simplicity of algorithm design, implementing the GTA algorithm naively following the three processing steps, i.e., brute-force, will result in an exponential-cost computation, and thus it is impractical for processing large data. The theory of GTA illustrates that if the definitions of generator, tester, and aggregator satisfy certain conditions, an efficient (usually near-linear cost) MapReduce program can be automatically derived from the GTA algorithm.     

A framework for tailorable games: toward inclusive end-user development of inclusive games

Universal Access in the Information Society - One strategy toward universalizing play is enabling more people to develop their own games. In this paper, our efforts toward a framework for inclusive...     

A cellular automaton for blocking queen games

We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as Blocking Wythoff Nim, consists of moving a queen as in chess, but always towards (0, 0), and it may not be moved to any of \(k-1\) temporarily “blocked” positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of k is a parameter that defines the game, and the pattern of winning positions can be very sensitive to k. As k becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of k. The patterns for large k display an unprecedented amount of self-organization at many scales, and here we attempt to describe the self-organized structure that appears. This paper extends a previous study (Cook et al. in Cellular automata and discrete complex systems, AUTOMATA 2015, Lecture Notes in Computer Science, vol 9099, pp 71–84, 2015), containing further analysis and new insights into the long term behaviour and structures generated by our blocking queen cellular automaton.     

A hookup theorem for multilevel security

A security property for trusted multilevel systems, restrictiveness, is described. It restricts the inferences a user can make about sensitive information. This property is a hookup property, or composable, meaning that a collection of secure restrictive systems when hooked together form a secure restrictive composite system. It is argued that the inference control and composability of restrictiveness make it an attractive choice for a security policy on trusted systems and processes     

A new method for quantifying entanglement of multipartite entangled states

We propose a new way for quantifying entanglement of multipartite entangled states which have a symmetrical structure and can be expressed as valence-bond-solid states. We put forward a new concept ‘unit.’ The entangled state can be decomposed into a series of units or be reconstructed by multiplying the units successively, which simplifies the analyses of multipartite entanglement greatly. We compute and add up the generalized concurrence of each unit to quantify the entanglement of the whole state. We verify that the new method coincides with concurrence for two-partite pure states. We prove that the new method is a good entanglement measure obeying the three necessary conditions for all good entanglement quantification methods. Based on the method, we compute the entanglement of multipartite GHZ, cluster and AKLT states.     

A Mezei-Wright theorem for categorical algebras

The main result of this paper is a generalization of the Mezei-Wright theorem, a result on solutions of a system of fixed point equations. In the typical setting, one solves a system of fixed point equations in an algebra equipped with a suitable partial order; there is a least element, suprema of ω-chains exist, the operations preserve the ordering and least upper bounds of ω-chains. In this setting, one solution of this kind of system is provided by least fixed points. The Mezei-Wright theorem asserts that such a solution is preserved by a continuous, order preserving algebra homomorphism.In several settings such as (countable) words or synchronization trees there is no well-defined partial order but one can naturally introduce a category by considering morphisms between the elements. The generalization of this paper consists in replacing ordered algebras by “categorical algebras”; the least element is replaced by an initial element, and suprema of ω-chains are replaced by colimits of ω-diagrams. Then the Mezei-Wright theorem for categorical algebras is that initial solutions are preserved by continuous morphisms. We establish this result for initial solutions of parametric fixed point equations.One use of the theorem is to characterize an “algebraic” element as one that can arise as a solution of some system of fixed point equations. In familiar examples, an algebraic element is one that is context-free, regular or rational. Then, if h:A→B is a continuous morphism of categorical algebras, the algebraic objects in B are those isomorphic to h-images of algebraic objects in A.