On transformations of algorithms to multiply 2 × 2 matrices

Representing these algorithms by noncommulative polynomials, we construct first the optimal algorithm of Winograd. Then, using an invariant transformation—in the algebraic sense—we transform this algorithm into the algorithm of Strassen. Follow remarks on this family of algorithms.     

On the estimation of transfer functions,regularizations and Gaussian processes—Revisited

Intrigued by some recent results on impulse response estimation by kernel and nonparametric techniques, we revisit the old problem of transfer function estimation from input–output measurements. We formulate a classical regularization approach, focused on finite impulse response (FIR) models, and find that regularization is necessary to cope with the high variance problem. This basic, regularized least squares approach is then a focal point for interpreting other techniques, like Bayesian inference and Gaussian process regression. The main issue is how to determine a suitable regularization matrix (Bayesian prior or kernel). Several regularization matrices are provided and numerically evaluated on a data bank of test systems and data sets. Our findings based on the data bank are as follows. The classical regularization approach with carefully chosen regularization matrices shows slightly better accuracy and clearly better robustness in estimating the impulse response than the standard approach–the prediction error method/maximum likelihood (PEM/ML) approach. If the goal is to estimate a model of given order as well as possible, a low order model is often better estimated by the PEM/ML approach, and a higher order model is often better estimated by model reduction on a high order regularized FIR model estimated with careful regularization. Moreover, an optimal regularization matrix that minimizes the mean square error matrix is derived and studied. The importance of this result lies in that it gives the theoretical upper bound on the accuracy that can be achieved for this classical regularization approach.     

A modal contrastive logic: The logic of ‘but’

In this paper we present a modal approach to contrastive logic, the logic of contrasts as these appear in natural language conjunctions such as but. We use a simple modal logic, which is an extension of the well-knownS5 logic, and base the contrastive operators proposed by Francez in [2] on the basic modalities that appear in this logic. We thus obtain a logic for contrastive operators that is more in accord with the tradition of intensional logic, and that, moreover — we argue — has some more natural properties. Particularly, attention is paid to nesting contrastive operators. We show that nestings of but give quite natural results, and indicate how nestings of other contrastive operators can be done adequately. Finally, we discuss the example of the Hangman's Paradox and some similarities (and differences) with default reasoning. But but us no buts, as they say.Also partially supported by Nijmegen University, Toernooiveld, 6525 ED Nijmegen, The Netherlands.     

A characterization of answer sets for logic programs

Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems in answer set logic programming. Solving these problems using Gelfond and Lifschitz's original definition of answer sets is not an easy task. Alternative characterizations of answer sets for nested logic pro- grams by Erdem and Lifschitz, Lee and Lifschitz, and You et al. are based on the completion semantics and various notions of tightness. However, the notion of tightness is a local notion in the sense that for different answer sets there are, in general, different level mappings capturing their tightness. This makes it hard to be used in the design of algorithms for computing answer sets. This paper proposes a characterization of answer sets based on sets of generating rules. From this char- acterization new algorithms are derived for computing answer sets and for per- forming some other reasoning tasks. As an application of the characterization a sufficient and necessary condition for the equivalence between answer set seman- tics and completion semantics has been proven, and a basic theorem is shown on computing answer sets for nested logic programs based on an extended notion of loop formulas. These results on tightness and loop formulas are more general than that in You and Lin's work.     

Analysis of affinely equivalent Boolean functions

By some basic transforms and invariant theory, we give two results: 1) an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.     

PSD3××/4××/5××可编程单片机外围芯片

ＰＳＤ３××／４××／５××可编程单片机外围芯片ＰＳＤ３××／４××／５××ＰｒａｇｒａｍｍａｂｌｅＤｅｖｉｅｅ在当今嵌入式微处理器的产品设计中，人们越来越希望尽可能地缩短系统的设计时间；降低生产成本；减小系统功耗；简化电路设计，缩小印制板空间；使产...     

Implementing the ‘Fool's model’ of combinatory logic

This paper studies Fool's models of combinatory logic, and relates them to Hindley's D-completeness problem. A fool's model is a family of sets of formulas, closed under condensed detachment. Alternatively, it is a model ofCL in naive set theory. We examine Resolution; and the P-W problem. A sequel shows T is D-complete; also, its extensions. We close with an implementation FMO of these ideas.     

Comments on “general failure of logic programs”

The paper [1] purports to present a classification of the general failure sets of logic programs and a simple proof of the theorem on the soundness and completeness of the negation-as-failure rule. In this note we clarify some conflicting terminology between [1] and the papers [2, 3] to which it predominantly refers. Our main purpose, however, is to point out major errors, in particular, one in the proof of the above mentioned theorem.     

Complex-Valued Feature Masks by Directional Filtering of 3×3 Compass Feature Masks

: A two-dimensional (2D) N-directional edge detection filter was represented as a pair of real masks, i.e. by one complex-valued matrix [1]. The 3 × 3 compass gradient edge masks have often been used because of their simplicity, where N compass masks are constructed by rotating the kernel mask by an incremental angle of 2π/N. This paper presents complex-valued feature masks formulated by directional filtering of 3 × 3 feature masks (e.g. Prewitt, Sobel, Frei-Chen, Kirsch and roof masks), with the different number of directions N (= 8, 4 and 2). The same concept can be applied to any types of filtering/masks with arbitrary N. Received: 21 May 2001, Received in revised form: 15 November 2001, Accepted: 26 March 2002 ID="A1" Correspondence and offprint requests to: Professor Rae-Hong Park, Department of Electronic Engineering, Sogang University, C.P.O. Box 1142, Seoul 100–611, Korea. Email: rhpark@sogang.ac.kr     

Is the success of fuzzy logic really paradoxical?: Toward the actual logic behind expert systems

The formal concept of logical equivalence in fuzzy logic, while theoretically sound, seems impractical. The misinterpretation of this concept has led to some pessimistic conclusions. Motivated by practical interpretation of truth values for fuzzy propositions, we take the class (lattice) of all subintervals of the unit interval [0, 1] as the truth value space for fuzzy logic, subsuming the traditional class of numerical truth values from [0, 1]. The associated concept of logical equivalence is stronger than the traditional one. Technically, we are dealing with much smaller set of pairs of equivalent formulas, so that we are able to check equivalence algorithmically. The checking is done by showing that our strong equivalence notion coincides with the equivalence in logic programming. © 1996 John Wiley & Sons, Inc.     

Approximate syllogisms – on the logic of everyday life

Since Aristotle it is recognised that a valid syllogism cannot have two particular premises. However, that is not how a lay person sees it; at least as long as the premises read many, most etc, instead of a plain some. The lay people are right if one considers that these syllogisms do not have strict but approximate (Zadeh) validity. Typically there are only particular premises available in everyday life and one is dependent on such syllogisms. – Some rules on the usage of particular premises are given below.     

Theory of truth degrees of propositions in the logic system L_n~*

Approximate reasoning based on the idea of fuzzy sets was firstly proposed by Zadeh[1] in 1973, which differs from the one advocated in Artificial Intelligence. Indeed, Artificial Intelligence emphasizes symbolic manipulation and roots itself in logic, em…     

On the computation of the 〈3, 4, 5〉 curve skeleton of 3D objects

An algorithm to compute the curve skeleton of 3D objects in voxel images is presented. The skeleton is stable under isometric transformations of the object, since the algorithm is based on the use of the 〈3, 4, 5〉 weighted distance transform, which is a good approximation of the Euclidean distance transform. The 〈3, 4, 5〉 weighted distance transform is used both to identify suitable anchor points, and to efficiently check object voxels according to their distance to the background. The curve skeleton is symmetrically placed within the object, is topologically equivalent to the object, is unit-wide and provides a satisfactory representation of the object. Though the size of the object reconstructed from the curve skeleton via the reverse distance transformation is not as thick as that of the input, shape information is mostly retained by the skeleton, since all regions perceived as significant in the input can still be found in the reconstructed object.     

On the Equivalence of Some Models of Computation

In[1],a definition of computation was given.In[3],we have clarified the necessity of thedefinition.Here we prove the equivalence between the definition and some models ofcomputation.Hence the sufficiency of the definition is clear abundantly.