Logical omniscience as infeasibility

Logical theories for representing knowledge are often plagued by the so-called Logical Omniscience Problem. The problem stems from the clash between the desire to model rational agents, which should be capable of simple logical inferences, and the fact that any logical inference, however complex, almost inevitably consists of inference steps that are simple enough. This contradiction points to the fruitlessness of trying to solve the Logical Omniscience Problem qualitatively if the rationality of agents is to be maintained. We provide a quantitative solution to the problem compatible with the two important facets of the reasoning agent: rationality and resource boundedness. More precisely, we provide a test for the logical omniscience problem in a given formal theory of knowledge. The quantitative measures we use are inspired by the complexity theory. We illustrate our framework with a number of examples ranging from the traditional implicit representation of knowledge in modal logic to the language of justification logic, which is capable of spelling out the internal inference process. We use these examples to divide representations of knowledge into logically omniscient and not logically omniscient, thus trying to determine how much information about the reasoning process needs to be present in a theory to avoid logical omniscience.     

Self-tuning of fuzzy belief rule bases for engineering system safety analysis

A framework for modelling the safety of an engineering system using a fuzzy rule-based evidential reasoning (FURBER) approach has been recently proposed, where a fuzzy rule-base designed on the basis of a belief structure (called a belief rule base) forms a basis in the inference mechanism of FURBER. However, it is difficult to accurately determine the parameters of a fuzzy belief rule base (FBRB) entirely subjectively, in particular for complex systems. As such, there is a need to develop a supporting mechanism that can be used to train in a locally optimal way a FBRB initially built using expert knowledge. In this paper, the methods for self-tuning a FBRB for engineering system safety analysis are investigated on the basis of a previous study. The method consists of a number of single and multiple objective nonlinear optimization models. The above framework is applied to model the system safety of a marine engineering system and the case study is used to demonstrate how the methods can be implemented.     

The vetoers in a simple game with ordinal preferences

We consider a core of a simple game with ordinal preferences on a set of alternative outcomes Ω. When a player's strict preference relation takes any logically possible form of acyclic binary relation on Ω, necessary conditions for a simple game to have a nonempty core are given. If Ω is a finite set, the conditions are also sufficient. Further some related results are obtained.     

Simple calculation of moments of inertia for polygons

Recently the problem of finding the mass, centre of gravity and moments of inertia for laminae bounded by polygons arose in a programming course for first year civil engineering degree students. It was suggested that it would be useful for them to construct a program that would take as input the vertices of the polygon, and print out area, centroid and moment of inertia. In order to make the program have a logically simple structure, the method presented in this note was devised. After consultation with many standard textbooks and engineering handbooks it was discovered that the method was either original or completely neglected. Since in many respects the method compares favourably with the subdivision techniques of the standard sources it would appear to be worth publicising the technique.     

Automating Change of Representation for Proofs in Discrete Mathematics (Extended Version)

Representation determines how we can reason about a specific problem. Sometimes one representation helps us to find a proof more easily than others. Most current automated reasoning tools focus on reasoning within one representation. There is, therefore, a need for the development of better tools to mechanise and automate formal and logically sound changes of representation. In this paper we look at examples of representational transformations in discrete mathematics, and show how we have used tools from Isabelle’s Transfer package to automate the use of these transformations in proofs. We give an overview of a general theory of transformations that we consider appropriate for thinking about the matter, and we explain how it relates to the Transfer package. We show a few reasoning tactics we developed in Isabelle to improve the use of transformations, including the automation of search in the space of representations. We present and analyse some results of the use of these tactics.     

A general fuzzy control scheme for nonlinear processes with stability analysis

In this paper we develop a general fuzzy control scheme for nonlinear processes. Assuming little knowledge about the dynamics of the controlled process, the proposed scheme starts by probing the process at different points in its operating region to generate a fuzzy quantisation. A simple local controller is then designed at each fuzzy locality. A fuzzy inference mechanism then links up tje local controllers to form a global controller which can be further refined by the learning algorithm. By employing a newly developed structure-adaptive fuzzy modelling scheme, the appropriate fuzzy rule-base for the inference mechanism can be extracted stably and efficiently. The conditions for the stability of the global controller are rigourously established. Simulation results are presented to illustrate the effectiveness of the scheme.     

On the cubic convergence of the Paardekooper method

We show a simple way how asymptotic convergence results can be conveyed from a simple Jacobi method to a block Jacobi method. Our pilot methods are the well known symmetric Jacobi method and the Paardekooper method for reducing a skew-symmetric matrix to the real Schur form. We show resemblance in the quadratic and cubic convergence estimates, but also discrepances in the asymptotic assumptions. By numerical tests we confirm that our asymptotic assumptions for the Paardekooper method are most general.     

A distributed approach to capacity allocation in logical networks

We consider a dynamic capacity reallocation scheme in a logically fully-connected telecommunications network. We show that the problem of optimal capacity allocation can be solved in a distributed manner, an essential feature of such a scheme. Our continuous-capacity reallocation scheme can be used as a foundation for a discrete system. This is useful from the perspective of practical implementation.     

面向多部门多属性的群决策应急方案调整方法

针对具有多部门多属性的基于案例推理的应急方案生成问题,提出了一种新的群决策应急方案调整方法。首先,各部门根据关注的属性生成案例库,并应用检索方法得到最相似历史案例,再运用置信规则库进行应急方案调整来生成各部门应急方案;然后,各部门对每个部门生成的应急方案进行评价;在此基础上,根据各部门的评价信息确定权重,进而对各部门生成的应急方案进行集结得到目标案例的应急方案。最后,通过一个算例验证了所提出方法的可行性和有效性。     

Book review of spectral theory of linear operators and spectral systems in banach algebras,operator theory: advances and applications,Vladimir Müller,Birkhäuser Verlag,Basel-Boston-Berlin, 2003, Volume 139, 381 pages. ISBN 3-7643-6912-4

We explore how randomization can help asymptotic convergence properties of simple directional search-based optimization methods. Specifically, we develop a cheap, iterative randomized Hessian estimation scheme. We then apply this technique and analyse how it enhances a random directional search method. Then, we proceed to develop a conjugate-directional search method that incorporates estimated Hessian information without requiring the direct use of gradients.     

Constructivism,Factoring, and Beliefs

The errors made by remedial intermediate algebra students in factoring polynomials were analyzed in the light of student definitions of factoring. Certain belief sets about factoring are found to logically entail many of the errors made. The vocabulary of epistemic semantics is used to describe how beliefs are changed. It is suggested that belief-based teaching can be successful in teaching factoring.     

An Experiment in Teaching College Mathematics†

Kac has observed that the ideal preparation in mathematics, especially for non‐mathematicians, should focus not on acquiring skills but on acquiring certain attitudes. We administered a special attitude questionnaire to a sample of graduate students in mathematics and undergraduate speech majors. We found significant differences on 10 of 27 items on this test. We then administered this test to a mixed group of undergraduates at the beginning and at the end of a special experimental mathematics ‘course’ designed to modify and shape attitudes. We found changes in attitudes in the intended direction. The primary aims of the experimental course were to:

1. Get students without any prior acquaintance with mathematics or a fear thereof to approach their studies more analytically.

2. Acquire orientation to and acquaintance with 25‐75 basic concepts and methods covering sets, algebra, logic, computers, analysis, probability, math‐statistics and topology in an over‐all map of how they logically fit together and how they relate to problems of modern life.

3. Read, with appreciation, mathematical literature previously incomprehensible to them. These aims were met.

     

Partially ordered sets and stratification

We employ partially ordered sets to describe the stratification of a social system, using rank to define the strata. We present a simple method of computing the matrix corresponding to the Hasse diagram and prove its correctness. This methodology is applied to analyze the hierarchy of countries that have won at least one Olympic medal. Four different definitions of dominance are given, leading to four different hierarchies and Hasse diagrams. We also prove that any of these definitions preserve any ordering based on giving different weights to gold, silver, and bronze medals. We study dominance between adjacent strata and note how the system changes with time. We present a case analysis for Poland as an illustration of the set of data that can be computed for any country.     

Generalized resolution and cutting planes

This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as inequalities, then the resolvent of two clauses corresponds to a certain cutting plane in integer programming. By properly enlarging the class of cutting planes to cover clauses that state that at least a specified number of literals are true, we obtain a generalization of resolution that involves both cancellation-type and circulant-type sums. We show its completeness by proving that it generates all prime implications, generalizing an early result by Quine. This leads to a cutting-plane algorithm as well as a generalized resolution algorithm for checking whether a set of propositions, perhaps representing a knowledge base, logically implies a given proposition. The paper is intended to be readable by persons with either an operations research or an artificial intelligence background.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Eigenvectors for a random walk on a left-regular band

We present a simple construction of the eigenvectors for the transition matrices of random walks on a class of semigroups called left-regular bands. These walks were introduced and analyzed by Brown, and they include the hyperplane chamber walks of Bidigare, Hanlon and Rockmore. This construction leads to new concise proofs of several of the known results about these walks. We also explain how tools from poset topology can be used to extract an eigenbasis for the transition matrices of the hyperplane chamber walks, and indicate the connection with a method recently described by Denham.     

Symmetry,validation, and scattering matrices for time–domain scattering in waveguides

We outline a method to compute the solution in the frequency–domain for scattering in a waveguide by exploiting symmetry. The method is illustrated by considering a simple scattering example, where soft hard boundary conditions are alternated. We show how the straightforward mode matching or eigenfunction matching solution can be easily converted to scattering and transmission matrices when symmetry is exploited. We then show how the solution for two scatterers can be found explicitly, using symmetry which allows validation of our subsequent solution by scattering matrices. We also give a series of identities which the scattering matrix must satisfy for further numerical validation. Using these frequency–domain solutions we compute the time-domain scattering by incident Gaussian wave–packets.     

Method for solving hyperbolic systems with initial data on non-characteristic manifolds with applications to the shallow water wave equations

We are concerned with hyperbolic systems of order-one linear PDEs originated on non-characteristic manifolds. We put forward a simple but effective method of transforming such initial conditions to standard initial conditions (i.e. when the solution is specified at an initial moment of time). We then show how our method applies in fluid mechanics. More specifically, we present a complete solution to the problem of long waves run-up in inclined bays of arbitrary shape with nonzero initial velocity.     

Nonlinear mapping and distance geometry

Distance Geometry Problem (DGP) and Nonlinear Mapping (NLM) are two well established questions: DGP is about finding a Euclidean realization of an incomplete set of distances in a Euclidean space, whereas Nonlinear Mapping is a weighted Least Square Scaling (LSS) method. We show how all these methods (LSS, NLM, DGP) can be assembled in a common framework, being each identified as an instance of an optimization problem with a choice of a weight matrix. We study the continuity between the solutions (which are point clouds) when the weight matrix varies, and the compactness of the set of solutions (after centering). We finally study a numerical example, showing that solving the optimization problem is far from being simple and that the numerical solution for a given procedure may be trapped in a local minimum.

     

Lanczos-type Methods for Continuation Problems

We study the Lanczos type methods for continuation problems. First we indicate how the symmetric Lanczos method may be used to solve both positive definite and indefinite linear systems. Furthermore, it can be used to monitor the simple bifurcation points on the solution curve of the eigenvalue problems. This includes computing the minimum eigenvalue, the minimum singular value, and the condition number of the partial tridiagonalizations of the coefficient matrices. The Ritz vector thus obtained can be applied to compute the tangent vector at the bifurcation point for branch-switching. Next, we indicate that the block or band Lanczos method can be used to monitor the multiple bifurcations as well as to solve the multiple right hand sides. We also show that the unsymmetric Lanczos method can be exploited to compute the minimum eigenvalue of a nearly symmetric matrix, and therefore to detect the simple bifurcation point as well. Some preconditioning techniques are discussed. Sample numerical results are reported. Our test problems include second order semilinear elliptic eigenvalue problems. © 1997 by John Wiley & Sons, Ltd.     

An axiomatic characterization of the Owen–Shapley spatial power index

We present an axiomatic characterization of the Owen–Shapley spatial power index for the case where issues are elements of two-dimensional space. This characterization employs a version of the transfer condition, which enables us to unravel a spatial game into spatial games connected to unanimity games. The other axioms include two conditions concerned particularly with the spatial positions of the players, besides spatial versions of anonymity and dummy. The last condition says that dummy players can be left out in a specific way without changing the power of the other players. We show that this condition can be weakened to requiring dummies to have zero power if we add a condition of positional continuity. We also show that the axioms in our characterization(s) are logically independent.