Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

Computing with Contexts

We investigate a representation of contexts, expressions with holes in them, that enables them to be meaningfully transformed, in particular -converted and -reduced. In particular we generalize the set of -expressions to include holes, and on these generalized entities define -reduction (i.e., substitution) and filling so that these operations preserve -congruence and commute. The theory is then applied to allow the encoding of reduction systems and operational semantics of call-by-value calculi enriched with control, imperative and concurrent features.     

Shape optimization of elasto-plastic bodies under plane strains: Sensitivity analysis and numerical implementation

Optimal shape design problems for an elastic body made from physically nonlinear material are presented. Sensitivity analysis is done by differentiating the discrete equations of equilibrium. Numerical examples are included.Notation U ^ad set of admissible continuous design parameters - U _h ^ad set of admissible discrete design parameters - function fromU _h ^ad defining shape of body - _h function fromU _h ^ad defining approximated shape of body - vector of nodal values of _h - { _n} sequence of functions tending to - () domain defined by - K bulk modulus - shear modulus - penalty parameter for contact condition - V() space of virtual displacements in() - V _h(_h) finite element approximation ofV() - J cost functional - J _h discretized cost functional - J algebraic form ofJ _h - (u) stress tensor - e(u) strain tensor - K stiffness matrix - f force vector - b(q) term arising from nonlinear boundary conditions - q vector of nodal degrees of freedom - p vector of adjoint state variables - J Jacobian of isoparametric mapping - |J| determinant ofJ - N vector of shape function values on parent element - L matrix of shape function derivatives on parent element - G matrix of Cartesian derivatives of shape functions - X matrix of nodal coordinates of element - D matrix of elastic coefficients - B strain-displacement matrix - _P part of boundary where tractions are prescribed - _u part of boundary where displacements are prescribed - variable part of boundary - strain invariant     

The co-invariant generator: An aid in deriving loop bodies

Given a loop invariant,I, and an assignment,, which decreases the variant, we define a constructive function, cg, called the co-invariant generator, which has the property thatI cg (, I) wp (, I), where wp (, I) is the weakest precondition for to establish I. Several results about the co-invariant generator are proved, important special cases are considered, and a non-trivial example of its use in deriving the body of a loop is given. We also define a function which performs a related constructive action on terms formed from binary operations. The coinvariant generator makes a useful contribution to formalising and automating a key step in program derivation.     

Deterministic polynomial-time quantum algorithms for Simon’s problem

D. R. Simon stated a problem, so-called Simons problem, whose computational complexity is in the class BQP but not in BPP, where is the function or oracle given in the problem. This result indicates that BPP may be strictly included in its quantum counterpart, BQP. Later, G. Brassard and P. Høyer showed that Simons problem and its extended version can be solved by a deterministic polynomial time quantum algorithm. That is, these problems are in the class EQP. In this paper, we show that Simons problem and its extended version can be deterministically solved in a simpler and more concrete way than that proposed by G. Brassard and P. Høyer.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

On the Characteristics of Growing Cell Structures (GCS) Neural Network

In this paper, a self-developing neural network model, namely the Growing Cell Structures (GCS) is characterized. In GCS each node (or cell) is associated with a local resource counter (t). We show that GCS has the conservation property by which the summation of all resource counters always equals , thereby s is the increment added to (t) of the wining node after each input presentation and (0 < < 1.0) is the forgetting (i.e., decay) factor applied to (t) of non-wining nodes. The conservation property provides an insight into how GCS can maximize information entropy. The property is also employed to unveil the chain-reaction effect and race-condition which can greatly influence the performance of GCS. We show that GCS can perform better in terms of equi-probable criterion if the resource counters are decayed by a smaller .     

More Church–Rosser Proofs

The proofs of the Church–Rosser theorems for , , and reduction in untyped -calculus are formalized in Isabelle/HOL, an implementation of Higher Order Logic in the generic theorem prover Isabelle. For -reduction, both the standard proof and Takahashi's are given and compared. All proofs are based on a general theory of commutating relations that supports an almost geometric style of reasoning about confluence diagrams.     

The π-Calculus in Direct Style

We introduce a calculus which is a direct extension of both the and the calculi. We give a simple type system for it, that encompasses both Curry's type inference for the -calculus, and Milner's sorting for the -calculus as particular cases of typing. We observe that the various continuation passing style transformations for -terms, written in our calculus, actually correspond to encodings already given by Milner and others for evaluation strategies of -terms into the -calculus. Furthermore, the associated sortings correspond to well-known double negation translations on types. Finally we provide an adequate CPS transform from our calculus to the -calculus. This shows that the latter may be regarded as an assembly language, while our calculus seems to provide a better programming notation for higher-order concurrency. We conclude by discussing some alternative design decisions.     

Mathematical Analysis and Optimization of Infiltration Processes

A variety of infiltration techniques can be used to fabricate solid materials, particularly composites. In general these processes can be described with at least one time dependent partial differential equation describing the evolution of the solid phase, coupled to one or more partial differential equations describing mass transport through a porous structure. This paper presents a detailed mathematical analysis of a relatively simple set of equations which is used to describe chemical vapor infiltration. The results demonstrate that the process is controlled by only two parameters, and . The optimization problem associated with minimizing the infiltration time is also considered. Allowing and to vary with time leads to significant reductions in the infiltration time, compared with the conventional case where and are treated as constants.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Reasoning about programs in continuation-passing style

Plotkin's _v -calculus for call-by-value programs is weaker than the -calculus for the same programs in continuation-passing style (CPS). To identify the call-by-value axioms that correspond to on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformation, we determine the precise language of CPS terms closed under -transformations, as well as the call-by-value axioms that correspond to the so-called administrative -reductions on CPS terms. Using the inverse mapping, we map the remaining and equalities on CPS terms to axioms on call-by-value terms. On the pure (constant free) set of -terms, the resulting set of axioms is equivalent to Moggi's computational -calculus. If the call-by-value language includes the control operatorsabort andcall-with-current-continuation, the axioms are equivalent to an extension of Felleisenet al.'s _v -C-calculus and to the equational subtheory of Talcott's logic IOCC.This article is a revised and extended version of the conference paper with the same title [42]. The technical report of the same title contains additional material.The authors were supported in part by NSF grant CCR 89-17022 and by Texas ATP grant 91-003604014.     

Computing Optimal Diameter-Bounded Polygon Partitions

The minimum -small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most , for a given > 0. This paper considers the version of this problem that disallows Steiner points. This problem is motivated by applications in mesh generation and collision detection. The main result in the paper is a polynomial-time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NP-completeness result for the minimum -small partition problem for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any > 0, an (+)-small partition with no more polygons than in an optimal -small partition. We also present an exact polynomial-time algorithm for the minimum -small partition problem with the additional constraint that each piece in the partition be convex.     

A Mathematical Analysis of Pānini’s <Emphasis Type="Italic">Śivasūtras</Emphasis>

In Pninis grammar of Sanskrit one finds the ivastras, a table which defines the natural classes of phonological segments in Sanskrit by intervals. We present a formal argument which shows that, using his representation method, Pninis way of ordering the phonological segments to represent the natural classes is optimal. The argument is based on a strictly set-theoretical point of view depending only on the set of natural classes and does not explicitly take into account the phonological features of the segments, which are, however, implicitly given in the way a language clusters its phonological inventory. The key idea is to link the graph of the Hasse-diagram of the set of natural classes closed under intersection to ivastra-style representations of the classes. Moreover, the argument is so general that it allows one to decide for each set of sets whether it can be represented with Pninis method. Actually, Pnini had to modify the set of natural classes to define it by the ivastras (the segment h plays a special role). We show that this modification was necessary and, in fact, the best possible modification. We discuss how every set of classes can be modified in such a way that it can be defined in a ivastra-style representation.¹     

Complex-Weighted One-Unit ‘Rigid-Bodies’ Learning Rule for Independent Component Analysis

Over the recent years, noticeable theoretical efforts have been devoted to the understanding of the role of networks' parameter spaces in neural learning. One of the contributions in this field concerns the study of weight-flows on Stiefel manifold, which is the natural parameter-space's algebraic-structure in some unsupervised (information-theoretic) learning task. An algorithm belonging to the class of learning equations generating Stiefel-flows is based on the rigid-body theory, introduced by the present Author in 1996. The aim of this Letter is to present an investigation on the capability of a complex-weighted neuron, trained by a rigid-bodies learning theory, with application to blind source separation of complex-valued independent signals for telecommunication systems.     

Distributivity in Łℵ0 and Other Sentential Logics

Certain distributivity results for ukasiewicz's infinite-valued logic ₀ are proved axiomatically (for the first time) with the help of the automated reasoning program OTTER. In addition, nondistributivity results are established for a wide variety of positive substructural logics by the use of logical matrices discovered with the automated model-finding programs MACE and MAGIC.     

The way stylized language means: Pattern matching in the child ballads

This paper suggests ways in which the pattern-matching capability of the computer can be used to further our understanding of stylized ballad language. The study is based upon a computer-aided analysis of the entire 595,000- word corpus of Francis James Child'sThe English and Scottish Popular Ballads (1882–1892), a collection of 305 textual traditions, most of which are represented by a variety of texts. The paper focuses on the Mary Hamilton tradition as a means of discussing the function of phatic language in the ballad genre and the significance of textual variation.Cathy Lynn Preston is a Research Associate, Computer Research in the Humanities, at the University of Colorado, Boulder. She is interested in folklore, particularly oral narrative; popular literature of the 18th- and 19th-century, particularly broadside and chapbook; the works of John Gay, Jonathan Swift, Thomas Hardy; Middle English romance and lyric. Her major publications areA KWIC Concordance to Jonathan Swift's A Tale of a Tub, The Battle of the Books, and A Discourse Concerning the Mechanical Operation of the Spirit, A Fragment, (New York: Garland Publishing, 1984) (co-authored with Harold D. Kelling), andA KWIC Concordance to Thomas Hardy's Tess of the d'Urbervilles, (New York: Garland Publishing, 1989).     

Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

Conditions for the Light-Traffic Insensitivity to Loss Probability in a GI/G/m/0 Queueing System

A loss queueing system GI/G/m/0 is considered. Let a(x) be a p.d.f. of interarrival intervals. Assume that this function behaves like cx^-1 for small x. Further let B(x) be a d.f. of service time; (1/) be the mean service time. Conditions are derived for the light-traffic insensitivity of the loss probability to the form of B(x) as (/ ) 0. In particular, the condition = 1 is necessary. Estimates for the loss probability are obtained.