An extension of the theory of learning systems

Summary The author's inquiry [1] on learning systems is generalized in the following respects: The process of learning, instead of coming to an end when the learning goal has been reached, is supposed to last for ever, so that the above definitive learning as well as phenomena such as forgetting, re-learning, changing the goal etc. become describable.We take over the notion of semi-uniform solvability of a set of learning problems (2.2), but now (trivial cases excluded) the whole capacity of a learning system is never s. u. solvable. Finite such sets are. The notion of a solving-basis of some is introduced and we can state necessary conditions that possess such a basis (2.14), so that examples of sets without a basis can be provided. On the other hand, any s. u. solvable has as basis. The notion of uniform solvability (3.1) reinforces that of s. u. solvability, and there are given sufficient conditions for to be uniformly solvable (3.6). In some finite cases, s. u. solvability, existence of a basis and uniform solvability coincide (3.7–3.9). At last we give the construction for the weakest learning system solving a uniformly solvable problem set (3.12–3.19).Eine deutsche Fassung wurde am 30. Mai 1972 eingereicht.     

Redesign of a Systems Engineering Language: Formalisation of χ

This paper describes the redesign of a systems engineering language called . This is an engineering language designed to specify and analyse industrial systems. The main objective of this redesign was to enable mathematical reasoning about specifications. We discuss the original language, the requirements and design decisions, and the resulting syntax and semantics of the new version of , called . In particular, we elaborate on semantical aspects of s time model.     

Proof Reflection in Coq

We formalize natural deduction for first-order logic in the proof assistant Coq, using de Bruijn indices for variable binding. The main judgment we model is of the form d[:], stating that d is a proof term of formula under hypotheses it can be viewed as a typing relation by the Curry–Howard isomorphism. This relation is proved sound with respect to Coq's native logic and is amenable to the manipulation of formulas and of derivations. As an illustration, we define a reduction relation on proof terms with permutative conversions and prove the property of subject reduction.     

Ordinals II: Some applications and a functorial approach

The first part of this paper is a presentation of some common applications of ordinals: definition of a system of ordinal notations for ordinals less than ₀, direct connection between Kruskal's theorem and ₀, consistency proofs in proof theory (such as the consistency of Peano arithmetic by means of transfinite induction up to ₀). In the second part of the paper, a functorial construction of ordinals and in particular of the Veblen hierarchy is explained. This approach, introduced by Girard (theory of dilators), allows the construction of ordinals greater than ₀ to be pursued in a more natural way than if the Bachmann hierarchy is used.     

Rate of convergence of schmidt pairs and rational functions corresponding to best approximants of truncated hankel operators

The problem of approximating Hankel operators of infinite rank by finite-rank Hankel operators is considered. For efficiency, truncated infinite Hankel matrices ⁿ of are utilized. In this paper for any compact Hankel operator of the Wiener class, we derive the rate of l₂-convergence of the Schmidt pairs of ⁿ to the corresponding Schmidt pairs of . For a certain subclass of Hankel operators of the Wiener class, we also obtain the rate of l₁-convergence. In addition, an upper bound for the rate of uniform convergence of the rational symbols of best rank-k Hankel approximants of ⁿ to the corresponding rational symbol of the best rank-k Hankel approximant to asn is derived.Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025 and also supported by the National Science Foundation under Grant No. DMS 89-01345.     

What holds in a context?

In order to establish that [A] = [B] follows from a set of assumptions often one provesA =B and then invokes the principle of substitution of equals for equals. It has been observed that in the ancillary proof ofA =B one is allowed to use, in addition to those assumptions of which are free for , certain (open) sentencesP which may not be part of and may not follow from , but are related to the context . We show that in an appropriate formal system there is a closed form solution to the problem of determining precisely what sentencesP can be used. We say that those sentenceshold in the context under the set of assumptions . We suggest how the solution could be exploited in an interactive theorem prover.     

Logical Comparison of Inconsistent Perspectives using Scoring Functions

The language for describing inconsistency is underdeveloped. If a database (a set of formulae) is inconsistent, there is usually no qualification of that inconsistency. Yet, it would seem useful to be able to say how inconsistent a database is, or to say whether one database is more inconsistent than another database. In this paper, we provide a more general characterization of inconsistency in terms of a scoring function for each database . A scoring function S is from the power set of into the natural numbers defined so that S() gives the number of minimally inconsistent subsets of that would be eliminated if the subset was removed from . This characterization offers an expressive and succinct means for articulating, in general terms, the nature of inconsistency in a set of formulae. We then compare databases using their scoring functions. This gives an intuitive ordering relation over databases that we can describe as more inconsistent than. These techniques are potentially useful in a wide range of problems including monitoring progress in negotiations between a number of participants, and in comparing heterogeneous sources of information.     

Ordinals I: Basic notions

At the end of the last century, Cantor generalized the notion of natural integer by considering the order structure of integers. According to the idea of counting more and more, he introduced transfinite numbers over natural numbers. Thus an ordinal may be simply defined as a natural number or a transfinite number, and ordinal arithmetic extends usual one. The ordinals up to ₀ can be described in an intuitive way (with 0, 1, and the sum, product and exponentiation operations). In contrast, it cannot be done for ordinals beyond ₀. In order to describe greater ordinals, Veblen introduced a normal functions hierarchy (i.e. strictly increasing and continuous) from ordinals into ordinals. This construction allows us to describe ordinals until ₀, using ordinals preceding ₀. Therefore, ₀ and ₀ have a similar role if Veblen functions are used for ₀ in addition to the previous operations.     

Generating Boolean \mu-expressions

In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times , where E is the size ofE andn _m is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas [17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.     

Data encodings and their costs

Summary This paper is devoted to developing and studying a precise notion of the encoding of a logical data structure in a physical storage structure, that is motivated by considerations of computational efficiency. The development builds upon the notion of an encoding of one graph in another. The cost of such an encoding is then defined so as to reflect the structural compatibility of the two graphs, the (externally specified) costs of implementing the host graph, and the (externally specified) set of intended usage patterns of the guest graph. The stability of the constructed framework is demonstrated in terms of a number of results; the faithfulness of the formalism is argued in terms of a number of examples from the literature; and the tractability of the model is hinted at by several results and by further references to the literature.     

A Full Bayesian Approach to Curve and Surface Reconstruction

When interpolating incomplete data, one can choose a parametric model, or opt for a more general approach and use a non-parametric model which allows a very large class of interpolants. A popular non-parametric model for interpolating various types of data is based on regularization, which looks for an interpolant that is both close to the data and also smooth in some sense. Formally, this interpolant is obtained by minimizing an error functional which is the weighted sum of a fidelity term and a smoothness term.The classical approach to regularization is: select optimal weights (also called hyperparameters) that should be assigned to these two terms, and minimize the resulting error functional.However, using only the optimal weights does not guarantee that the chosen function will be optimal in some sense, such as the maximum likelihood criterion, or the minimal square error criterion. For that, we have to consider all possible weights.The approach suggested here is to use the full probability distribution on the space of admissible functions, as opposed to the probability induced by using a single combination of weights. The reason is as follows: the weight actually determines the probability space in which we are working. For a given weight , the probability of a function f is proportional to exp(– f² _uu du) (for the case of a function with one variable). For each different , there is a different solution to the restoration problem; denote it by f. Now, if we had known , it would not be necessary to use all the weights; however, all we are given are some noisy measurements of f, and we do not know the correct . Therefore, the mathematically correct solution is to calculate, for every , the probability that f was sampled from a space whose probability is determined by , and average the different f's weighted by these probabilities. The same argument holds for the noise variance, which is also unknown.Three basic problems are addressed is this work: Computing the MAP estimate, that is, the function f maximizing Pr(f/D) when the data D is given. This problem is reduced to a one-dimensional optimization problem. Computing the MSE estimate. This function is defined at each point x as f(x)Pr(f/D) f. This problem is reduced to computing a one-dimensional integral.In the general setting, the MAP estimate is not equal to the MSE estimate. Computing the pointwise uncertainty associated with the MSE solution. This problem is reduced to computing three one-dimensional integrals.     

A variotherm mold for micro metal injection molding

In this paper, a variotherm mold was designed and fabricated for the production of 316L stainless steel microstructures by micro metal injection molding (MIM). The variotherm mold incorporated a rapid heating/cooling system, vacuum unit, hot sprue and cavity pressure transducer. The design of the variotherm mold and the process cycle of MIM using the variotherm mold were described. Experiments were conducted to evaluate the molded microstructures produced using variotherm mold and conventional mold. The experiments showed that microstructures of higher aspect ratio such as 60 m × height 191 m and 40 m × height 174 m microstructures could be injection molded with complete filling and demolded successfully using the variotherm mold. Molded microstructures with dimensions of 60 m × height 191 m were successfully debound and sintered without visual defects.     

Hierarchies of polynomially solvable satisfiability problems

In this paper, we introduce general techniques for extending classes of polynomially solvable SAT instances. We generalize the approach of Gallo and Scutellà, who defined the hierarchy { _i }, where _l corresponds to the Generalized Horn class. We propose a family of polynomial hierarchies, where a polynomial hierarchy { _i } is a sequence of polynomially solvable classes that cover the whole set of CNF formulas, and such that _{i i+1} fori0. Following a different approach, based on a new decomposition technique, we define the class of Split-Horn formulas, which is an extension of _l. We discuss and compare the basic properties of the proposed classes; polynomial time algorithms for recognition and solution are provided.     

Über die Konvergenz des Relaxationsverfahrens bei nicht-negativen und diagonaldominanten Matrizen

Zusammenfassung In der folgenden Arbeit werden zunächst die Begriffe Gesamtschrittverfahren, Einzelschrittverfahren und Relaxationsverfahren allgemein formuliert und dann auf allgemeine lineare Gleichungssysteme angewandt. Im Spezialfall einer Matrix mit verschwindender Hauptdiagonale erhält man so die bekanntenJacobi-, Gauss-Seidel- und Relaxationsverfahren. Satz 1 macht eine Aussage über die Konvergenz des Einzelschrittverfahrens bei allgemeinen, nicht-negativen Matrizen. Der Beweis verläuft ähnlich wie in einem bereits 1948 vonStein undRosenberg [2] behandelten Spezialfall. Als Korollar ergibt sich eine Aussage über die Konvergenz des Relaxationsverfahrens bei nicht-negativen Matrizen. Es wird ferner der Satz 2 über die Konvergenz des Relaxationsverfahrens bei diagonaldominanten Matrizen beweisen.

---

Summary In this paper we give a general definition what is meant by total-step-, single-step- and successive relaxation iterative method and we apply these concepts on systems of linear equations. In the special case of a matrix with zero diagonal entries we obtain the well knownJacobi-, Gauss-Seidel- and Relaxation iterative method. Theorem 1 gives conditions for the convergence of the singlestep-iterative method for general, non-negative matrices. The proof is similar to that given byStein andRosenberg in [2] (1948) for a special case. A corollary gives conditions for the convergence of the relaxation-iterative method for non-negative matrices. Further on we prove theorem 2 about the convergence of the relaxation-iterative method with diagonally dominant matrices.

     

The Origins of the Translator's Workstation

The first proposals for various component tools of what is now called the translator's workstation or translator's workbench are traced back to the 1970s and early 1980s in various, often independent, proposals at different stages in the development of computers and in their use by translators.     

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     

Undivided and Indistinguishable Histories in Branching-Time Logics

In the tree-like representation of Time, two histories are undivided at a moment t whenever they share a common moment in the future of t. In the present paper, it will first be proved that Ockhamist and Peircean branching-time logics are unable to express some important sentences in which the notion of undividedness is involved. Then, a new semantics for branching-time logic will be presented. The new semantics is based on trees endowed with an indistinguishability function, a generalization of the notion of undividedness. It will be shown that Ockhamist and Peircean semantics can be viewed as limit cases of the semantics developed in this paper.     

Tractable Decision for a Constraint Language Implies Tractable Search

A constraint satisfaction problem (CSP) instance has a set of variables, each of which can take values in some domain. It also has a set of constraints, each of which restricts the variables in its scope to take values limited by its constraint relation.The language of a constraint satisfaction problem instance is the set of different constraint relations used in its specification. For a given set of relations over some domain we define the problem CSP () to the set of CSP instances whose language is contained in .The decision problem for a set of CSP instances is, given an instance in the class, to decide whether a solution exists. The search problem is to find such a solution. Here we address the connection between the tractability of the decision and search problems. We prove that given a constraint language over a finite domain for which the decision problem for CSP () is tractable, the search problem is always tractable.We define a surjective language over a finite domain in a standard way. We also show that we can determine in polynomial time whether an instance over a surjective language with a tractable decision problem has fewer than k solutions, and that we can generate all of its solutions with polynomial delay.     

A remark about a substitution property

S. A. Greibach proved in Chains of full AFL's a useful property concerning the substitution of full semi-AFL's. We prove here that this property remains true when the families of languages under considerations are assumed only to be full trios, i.e., closure under union is not required.