A quantitative solution to Constraint Satisfaction Problem (CSP)

Constraint Satisfaction Problem (CSP) is an important problem in artificial intelligence and operations research. Many practical problems can be formulated as CSP, i.e., finding a consistent value assignment to variables subject to a set of constraints. In this paper, we give a quantitative approach to solve the CSPs which deals uniformly with binary constraints as well as high order,k-ary (k ≥ 2) constraints. In this quantitative approach, using variable transformation and constraint transformation, a CSP is transformed into a satisfiability (SAT) problem. The SAT problem is then solved within a continuous search space. We will evaluate the performance of this method based on randomly generated SAT problem instances and regularly generatedk-ary (k ≥ 2) CSP problem instances.     

An artificial brain ATR's CAM-Brain Project aims to build/evolve an artificial brain with a million neural net modules inside a trillion cell Cellular Automata Machine

ATR's Evolutionary Systems Department aims to build (i.e. grow/evolve) an artificial brain by the year 2001. This artificial brain should initially contain thousands of interconnected artificial neural network modules, and be capable of controlling approximately 1000 “behaviors” in a “robot kitten”. The name given to this research project is “CAM-Brain”, because the neural networks (based on cellular automata) will be grown inside special hardware called Cellular Automata Machines (CAMs). Using a family of CAMs, each with its own processor to measure the performance quality or fitness of the evolved neural circuits, will allow the neural modules and their interconnections to be grown/evolved at electronic speeds. State of the art in CAM design is about 10 to the power 9 or 10 cells. Since a neural module of about 15 connected neurons can fit inside a cube of 100 cells on a side (1 million cells), a CAM which is specially adapted for CAM-Brain could contain thousands of interconnected modules, i.e. an artificial brain.     

The learning convergence of CMAC in cyclic learning

In this paper we discuss the learning convergence of the cerebellar model articulation controller (CMAC) in cyclic learning.We prove the following results.First,if the training samples are noiseless,the training algorithm converges if and only if the learning rate is chosen from (0,2).Second,when the training samples have noises,the learning algorithm will converge with a probability of one if the learning rate is dynamically decreased.Third,in the case with noises,with a small but fixed learning rate ε the mean square error of the weight sequences generated by the CMAC learning algorithm will be bounded by O(ε).Some simulation experiments are carried out to test these results.     

Granularity analysis for exploiting adaptive parallelism of declarative programs on multiprocessors

Declarative Programming Languages (DPLs) apply a grocess model of Horn clauses such as PARLOG^[8] or a reduction model of λ-calculus such as SML^[7] and are,in principle,well suited to multiprocessor implementation.However,the performance of a paralled declarative program can be impaired by a mismatch between the parallelism available in an application and the parallelism available in the architecture.A particularly attractive solution is to automatically match the parallelism of the program to the parallelism of the target hardware as a compilation step.In this paper,we present an optimizing compilation technique called granularity analysis which identifies and removes excess parallelism that would degrade performance.The main steps are:an analysis of the flow of data to form an attributed call graph between function (or predicate) arguments;and an asymptotic estimation of granularity of a function (or predicate) to generate approximate grain size.Compiled procedure calls can be annotated with grain size and a task scheduler can make scheduling decisions with the classification scheme of grains to control parallelism at run-time.The resulting granularity analysis scheme is suitable for exploiting adaptive parallelism of declarative programming languages on multiprocessors.     

Implementing specifications by dynamic inheritance

An extended form of logic programming is presented which combines SLD-resolution with a dynamic form of inheritance between modules. The resulting inference system supports the notion of ‘implementation’ as a process of computing mappings between specifications and technologies—both formulated as sets of clausal-form theories—in order to satisfy requirements posed as queries. Besides detailing the operational features of the formalism, the paper also explores its semantics and its practical value in two case studies.     

Distributed programming with Logic Tuple Spaces

From the point of view of distributed programming one of the most interesting communication mechanisms is associative tuple matching in a shared dataspace, as exemplified in the Linda coordination language. Linda has been used as a coordination layer to parallelize several sequential programming languages, such as C and Scheme. In this paper we study the combination of Linda with a logic language, whose result is the language Extended Shared Prolog (ESP). We show that ESP is based on a new programming model called PoliS, that extends Linda with Multiple Tuple Spaces. A class of applications for ESP is discussed, introducing the concept of “open multiple tuple spaces”. Finally, we show how the distributed implementation of ESP uses the network version of Linda’s tuple space.     

Acyclic programs

We study here a natural subclass of the locally stratified programs which we call acyclic. Acyclic programs enjoy several natural properties. First, they terminate for a large and natural class of general goals, so they could be used as terminating PROLOG programs. Next, their semantics can be defined in several equivalent ways. In particular we show that the immediate consequence operator of an acyclic programP has a unique fixpointM _p , which coincides with the perfect model ofP, is the unique Herbrand model of the completion ofP and can be identified with the unique fixpoint of the 3-valued immediate consequence operator associated withP. The completion of an acylic programP is shown to satisfy an even stronger property: addition of a domain closure axiom results in a theory which is complete and decidable with respect to a large class of formulas including the variable-free ones. This implies thatM _p is recursive. On the procedural side we show that SLS-resolution and SLDNF-resolution for acyclic programs coincide, are effective, sound and (non-floundering) complete with respect to the declarative semantics. Finally, we show that various forms of temporal reasoning, as exemplified by the so-called Yale Shooting Problem, can be naturally described by means of acyclic programs.     

Domains of attraction in autoassociative memory networks

An autoassociative memory network is constructed by storing reference pattern vectors whose components consist of a small positive number ∈ and 1-∈. Although its connection weights can not be determined only by this storing condition, it is proved that the output function of the network becomes a contraction mapping in a region around each stored pattern if ∈ is sufficiently small. This implies that the region is a domain of attraction in the network. The shape of the region is clarified in our analysis. Domains of attraction larger than this region are also found. Any noisy pattern vector in such domains, which may have real valued components, can be recognized as one of the stored patterns. We propose a method for determining connection weights of the network, which uses the shape of the domains of attraction. The model obtained by this method has symmetric connection weights and is successfully applied to character pattern recognition.     

Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

Let G be any finite graph. A mapping c:E(G)→{1,…,k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that for every graph G which satisfies the condition that |E(G^′)|?t|V(G^′)|−1 for each subgraph G^′⊆G, where t?2 is a given integer, the constant p=2t³−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.     

Enclosing the solution set of linear systems with inaccurate data by iterative methods based on incomplete LU-decompositions

We present a class of iterative methods to enclose the solution set by an interval vector;A is varying in ann×n intervalH-Matrix andb is varying in an interval vector . The algorithm taken into consideration generalizes an iterative method of Meijerink/van der Vorst based on an incompleteLU-decomposition of anM-MatrixA. Theorems concerning the feasibility of the algorithm, its rate of convergence and its quality of enclosure are given. Since the original method of Meijerink/van der Vorst is a special case of our algorithm we have thus shown its applicability to the larger class ofH-matrices. Furthermore we relate theR ₁-factor (as defined in Ortega/Rheinboldt [9]) of the original method to the underlying setP of indices.     

On quasi-interpretations of grammar forms

The notions of a grammar form and its interpretations were introduced to describe families of structurally related grammars. Basically, a grammar formG is a (context-free) grammar serving as a master grammar and the interpretation operator defines a family of grammars, each structurally related toG. In this paper, a new operator yielding a family of grammars, is introduced as a variant of . There are two major results. The first is that and commute. The second is that for each grammar formG, the collection of all families of grammars ,G′ in , is finite. Expressed otherwise, the second result is that for each grammar formG there is only a bounded number of grammar forms in (G) no two of which are strongly equivalent.     

Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.     

Generalized symmetric Runge-Kutta methods

In this paper the concept of symmetry for Runge-Kutta methods is generalized to include composite methods. The extrapolations of the usual compositions of a symmetric method ? of the form are shown not to beA-stable. However, this limitation can be overcome by considering composite methods of the form where represents a non-symmetric and possiblyL-stable method called a symmetrizer satisfying . While no longer symmetric, these composite methods yet satisfy and thus share with symmetric methods the important property of admitting asymptotic error expansions in even powers of 1/n. Composite methods that are constructed in this way and presented in this paper have implementation costs comparable to that for the symmetric method. They generalize those based on the implicit midpoint and trapezoidal rules used with the standard smoothing formulae and thus extend the class of methods for acceleration techniques of extrapolation and defect correction. A characterization ofL-stable symmetrizers for 2-stage symmetric methods is given and studied for a particular stiff model problem. The analysis suggests that certainL-stable symmetrizers can play an important role in suppressing order defect effects for stiff problems.     

About acyclic edge colourings of planar graphs

Let G=(V,E) be any finite simple graph. A mapping is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529].In this paper we prove that for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that if G is planar.     

Iterative weighted least squares algorithms for neural networks classifiers

This paper discusses learning algorithms of layered neural networks from the standpoint of maximum likelihood estimation. At first we discuss learning algorithms for the most simple network with only one neuron. It is shown that Fisher information of the network, namely minus expected values of Hessian matrix, is given by a weighted covariance matrix of input vectors. A learning algorithm is presented on the basis of Fisher's scoring method which makes use of Fisher information instead of Hessian matrix in Newton's method. The algorithm can be interpreted as iterations of weighted least squares method. Then these results are extended to the layered network with one hidden layer. Fisher information for the layered network is given by a weighted covariance matrix of inputs of the network and outputs of hidden units. Since Newton's method for maximization problems has the difficulty when minus Hessian matrix is not positive definite, we propose a learning algorithm which makes use of Fisher information matrix, which is non-negative, instead of Hessian matrix. Moreover, to reduce the computation of full Fisher information matrix, we propose another algorithm which uses only block diagonal elements of Fisher information. The algorithm is reduced to an iterative weighted least squares algorithm in which each unit estimates its own weights by a weighted least squares method. It is experimentally shown that the proposed algorithms converge with fewer iterations than error back-propagation (BP) algorithm.     

On the approximate solution of first-kind integral equations of Volterra type

The present paper deals with the approximate solution of integral equations of the first kind, ( y)x∈I:=[a, b], where denotes a (linear) integral operator of Volterra (or Abel) type, and whereg∈C(I), withg(a)=0. The given functiong is approximated uniformly onI (or on a finite subsetZ?I by using certain weak Chebyshev systems onI which are obtained in a natural way. By the linearity of this yields an approximation to the exact solutiony onI. Questions of uniqueness and characterization of such approximating functions, as well as numerical aspects of the approximation problem are discussed.     

Least common container of tree pattern queries and its applications

Tree patterns represent important fragments of XPath. In this paper, we show that some classes \({\mathcal{C}}\) of tree patterns exhibit such a property that, given a finite number of compatible tree patterns \({P_1, \ldots, P_n\in \mathcal{C}}\), there exists another pattern P such that P ₁, . . . , P _n are all contained in P, and for any tree pattern \({Q\in \mathcal{C}}\), P ₁, . . . , P _n are all contained in Q if and only if P is contained in Q. We experimentally demonstrate that the pattern P is usually much smaller than P ₁, . . . , P _n combined together. Using the existence of P above, we show that testing whether a tree pattern, P, is contained in another, \({Q\in \mathcal{C}}\), under an acyclic schema graph G, can be reduced to testing whether P _G , a transformed version of P, is contained in Q without any schema graph, provided that the distinguished node of P is not labeled *. We then show that, under G, the maximal contained rewriting (MCR) of a tree pattern Q using a view V can be found by finding the MCR of Q using V _G without G, when there are no *-nodes on the distinguished path of V and no *-nodes in Q.