Supporting the formal verification of mathematical texts

The formal verification of mathematical texts is one of the most interesting applications for computer systems. In fact, we argue that the expert language of mathematics is the natural choice for achieving efficient mathematician–machine interaction. Our empirical approach, the analysis of carefully authored textbook proofs, forces us to focus on the language and the reasoning pattern that mathematician use when presenting proofs to colleagues and students. Enabling a machine to understand and follow such language and argumentation is seen to be the key to usable and acceptable math assistant systems. In this paper, we first perform an analysis of three textbook proofs by hand; we then describe a computational framework that aims at mechanising such an analysis. The resulting proof-of-concept implementation is capable of processing simple textbook proofs and constitutes promising steps towards a natural mathematician–machine interface for proof development and verification.     

Computer supported mathematics with Ωmega

Classical automated theorem proving of today is based on ingenious search techniques to find a proof for a given theorem in very large search spaces—often in the range of several billion clauses. But in spite of many successful attempts to prove even open mathematical problems automatically, their use in everyday mathematical practice is still limited.The shift from search based methods to more abstract planning techniques however opened up a paradigm for mathematical reasoning on a computer and several systems of that kind now employ a mix of interactive, search based as well as proof planning techniques.The Ωmega system is at the core of several related and well-integrated research projects of the Ωmega research group, whose aim is to develop system support for a working mathematician as well as a software engineer when employing formal methods for quality assurance. In particular, Ωmega supports proof development at a human-oriented abstract level of proof granularity. It is a modular system with a central proof data structure and several supplementary subsystems including automated deduction and computer algebra systems. Ωmega has many characteristics in common with systems like NuPrL, CoQ, Hol, Pvs, and Isabelle. However, it differs from these systems with respect to its focus on proof planning and in that respect it is more similar to the proof planning systems Clam and λClam at Edinburgh.     

SAD as a mathematical assistant—how should we go from here to there?

The System for Automated Deduction (SAD) is developed in the framework of the Evidence Algorithm research project and is intended for automated processing of mathematical texts. The SAD system works on three levels of reasoning: (a) the level of text presentation where proofs are written in a formal natural-like language for subsequent verification; (b) the level of foreground reasoning where a particular theorem proving problem is simplified and decomposed; (c) the level of background deduction where exhaustive combinatorial inference search in classical first-order logic is applied to prove end subgoals.

We present an overview of SAD describing the ideas behind the project, the system's design, and the process of problem formalization in the fashion of SAD. We show that the choice of classical first-order logic as the background logic of SAD is not too restrictive. For example, we can handle binders like Σ or lim without resort to second order or to a full-powered set theory. We illustrate our approach with a series of examples, in particular, with the classical problem .     

Mapclus: A mathematical programming approach to fitting the adclus model

We present a new algorithm, MAPCLUS (MAthematicalProgrammingCLUStering), for fitting the Shepard-Arabie ADCLUS (forADditiveCLUStering) model. MAPCLUS utilizes an alternating least squares method combined with a mathematical programming optimization procedure based on a penalty function approach, to impose discrete (0,1) constraints on parameters defining cluster membership. This procedure is supplemented by several other numerical techniques (notably a heuristically based combinatorial optimization procedure) to provide an efficient general-purpose computer implemented algorithm for obtaining ADCLUS representations. MAPCLUS is illustrated with an application to one of the examples given by Shepard and Arabie using the older ADCLUS procedure. The MAPCLUS solution uses half as many clusters to achieve nearly the same level of goodness-of-fit. Finally, we consider an extension of the present approach to fitting a three-way generalization of the ADCLUS model, called INDCLUS (INdividualDifferencesCLUStering).We are indebted to Scott A. Boorman, W. K. Estes, J. A. Hartigan, Lawrence J. Hubert, Carol L. Krumhansl, Joseph B. Kruskal, Sandra Pruzansky, Roger N. Shepard, Edward J. Shoben, Sigfrid D. Soli, and Amos Tversky for helpful discussions of this work, as well as the anonymous referees for their suggestions and corrections on an earlier version of this paper. We are also grateful to Pamela Baker and Dan C. Knutson for technical assistance. The research reported here was supported in part by LEAA Grant 78-NI-AX-0142 and NSF Grants SOC76-24512 and SOC76-24394.     

Error analysis of digital filters using HOL theorem proving

When a digital filter is realized with floating-point or fixed-point arithmetics, errors and constraints due to finite word length are unavoidable. In this paper, we show how these errors can be mechanically analysed using the HOL theorem prover. We first model the ideal real filter specification and the corresponding floating-point and fixed-point implementations as predicates in higher-order logic. We use valuation functions to find the real values of the floating-point and fixed-point filter outputs and define the error as the difference between these values and the corresponding output of the ideal real specification. Fundamental analysis lemmas have been established to derive expressions for the accumulation of roundoff error in parametric Lth-order digital filters, for each of the three canonical forms of realization: direct, parallel, and cascade. The HOL formalization and proofs are found to be in a good agreement with existing theoretical paper-and-pencil counterparts.     

A mixed-method approach to post-retirement career planning

In times of rising longevity and shortage of skilled workers, post-retirement work has become increasingly prevalent in many countries. However, not much is known about the expectations and facilitating factors associated with work-related activities after retirement. In two studies we draw on the social cognitive career theory and investigated the role of outcome expectations and facilitating factors in post-retirement career planning. First, we interviewed 22 older employees and subject matter experts in a German aerospace company to learn more about expectations of post-retirement work and its facilitating factors to build a theoretical model. Second, to test our theoretical model, 212 employees of the same company aged 50 to 65 completed a web-based survey. Results showed that outcome expectations and the facilitating factors identified in the interview study were significantly related to post-retirement career intention. Further, the facilitating factor social approval moderated the relationship between outcome expectations and post-retirement career intention. We discuss implications of our findings in terms of how they inform retirement counselors, organizations, and society to help increase engagement in work-related activities after retirement.     

Theorema: Towards computer-aided mathematical theory exploration

Theorema is a project that aims at supporting the entire process of mathematical theory exploration within one coherent logic and software system. This survey paper illustrates the style of Theorema-supported mathematical theory exploration by a case study (the automated synthesis of an algorithm for the construction of Gröbner Bases) and gives an overview on some reasoners and organizational tools for theory exploration developed in the Theorema project.     

A multicriteria approach for material yard planning

The material yard is the origin of the production process for manufacturing firms. If materials are not stored at appropriate locations of the yard, then the stacking operation and the subsequent reclaiming operation will be inefficient in terms of time. In this paper a multicriteria approach which utilizes local trade-offs between different criteria in the absence of an explicit overall preference function is proposed to solve the material yard planning problem. The idea is to linearize the unknown preference function at a given point in the solution space. If the trade-offs between different criteria at this point can be determined via some mechanism, then a better solution can be derived. This process is continued until it converges to a stationary point, namely the optimal solution. To illustrate this idea, a case of the China Steel Co. in Taiwan is presented. The results from a simulation study indicate that the proposed approach is able to find a very good solution which satisfies all the criteria in a rather short transition period. © 1997 John Wiley & Sons, Ltd.     

Proof theory and mathematical meaning of paraconsistent C-systems

A proof-theoretic analysis and new arithmetical semantics are proposed for some paraconsistent C-systems, which are a relevant sub-class of Logics of Formal Inconsistency (LFIs) introduced by W.A. Carnielli et al. (2002, 2005) [8] and [9]. The sequent versions BC, CI, CIL of the systems bC, Ci, Cil presented in Carnielli et al. (2002, 2005) [8] and [9] are introduced and examined. BC, CI, CIL admit the cut-elimination property and, in general, a weakened sub-formula property. Moreover, a formal notion of constructive paraconsistent system is given, and the constructivity of CI is proven. Further possible developments of proof theory and provability logic of CI-based arithmetical systems are sketched, and a possible weakened Hilbert?s program is discussed. As to the semantical aspects, arithmetical semantics interprets C-system formulas into Provability Logic sentences of classical Arithmetic PA (Artemov and Beklemishev (2004) [2], Japaridze and de Jongh (1998) [19], Gentilini (1999) [15], Smorynski (1991) [22]): thus, it links the notion of truth to the notion of provability inside a classical environment. It makes true infinitely many contradictions B∧¬B and falsifies many arbitrarily complex instances of non-contradiction principle ¬(A∧¬A). Moreover, arithmetical models falsify both classical logic LK and intuitionistic logic LJ, so that a kind of metalogical completeness property of LFI-paraconsistent logic w.r.t. arithmetical semantics is proven. As a work in progress, the possibility to interpret CI-based paraconsistent Arithmetic PACI into Provability Logic of classical Arithmetic PA is discussed, showing the role that PACIarithmetical models could have in establishing new meta-mathematical properties, e.g. in breaking classical equivalences between consistency statements and reflection principles.     

A kinematic approach to the conceptual representations of this and that

The Italian demonstrative pronouns questo/a (‘this_[mas/fem]’) and quello/a (‘that_[mas/fem]’) implicitly convey information about objects’ distance with respect to the speaker. Our study investigated the referents of questo/a (‘this_[mas/fem]’) and quello/a (‘that_[mas/fem]’) by analysing their influence on reach-to-grasp actions towards objects located near to (12 cm) or far from (30 cm) the participant. Upon acoustic instruction containing one or the other pronoun, participants had to reach for and grasp a target object. Results showed an effect of pronoun on movement planning. When the object was in the far position, reaction times were faster for the congruent pronoun quello/a, whereas when it was in the near position they were faster for the congruent pronoun questo/a. Interactions between implied and real target distance suggest that the conceptual spaces of questo/a and quello/a do not map onto a strict distinction between peripersonal and extrapersonal space.     

A contribution to the mathematical biophysics of psychophysical discrimination

The properties of a simple neural mechanism are developed theoretically and interpreted in terms of observable variables. The results are discussed in connection with experimental data in cases for which the latter are available.     

Investigating the impact of mindfulness meditation training on working memory: A mathematical modeling approach

We investigated whether mindfulness training (MT) influences information processing in a working memory task with complex visual stimuli. Participants were tested before (T1) and after (T2) participation in an intensive one-month MT retreat, and their performance was compared with that of an age- and education-matched control group. Accuracy did not differ across groups at either time point. Response times were faster and significantly less variable in the MT versus the control group at T2. Since these results could be due to changes in mnemonic processes, speed–accuracy trade-off, or nondecisional factors (e.g., motor execution), we used a mathematical modeling approach to disentangle these factors. The EZ-diffusion model (Wagenmakers, van der Maas, & Grasman, Psychonomic Bulletin & Review 14:(1), 3–22, 2007) suggested that MT leads to improved information quality and reduced response conservativeness, with no changes in nondecisional factors. The noisy exemplar model further suggested that the increase in information quality reflected a decrease in encoding noise and not an increase in forgetting. Thus, mathematical modeling may help clarify the mechanisms by which MT produces salutary effects on performance.     

A general tableau method for propositional interval temporal logics: Theory and implementation

In this paper, we focus our attention on tableau methods for propositional interval temporal logics. These logics provide a natural framework for representing and reasoning about temporal properties in several areas of computer science. However, while various tableau methods have been developed for linear and branching time point-based temporal logics, not much work has been done on tableau methods for interval-based ones. We develop a general tableau method for Venema's CDT logic interpreted over partial orders (BCDT⁺ for short). It combines features of the classical tableau method for first-order logic with those of explicit tableau methods for modal logics with constraint label management, and it can be easily tailored to most propositional interval temporal logics proposed in the literature. We prove its soundness and completeness, and we show how it has been implemented.     

A community-reinforcement approach to alcoholism

Several theoretical approaches to alcoholism exist. An opérant reinforcement approach was used in the present study to develop a new procedure that rearranged community reinforcers such as the job, family and social relations of the alcoholic such that drinking produced a time-out from a high density of reinforcement. The results showed that the alcoholics who received this Community-Reinforcement counseling drank less, worked more, spent more time with their families and out of institutions than did a matched control group of alcoholics who did not receive these procedures. This new approach appears to be an effective method of reducing alcoholism. An analysis in reinforcement terms is presented of the etiology, epidemiology, and treatment of alcoholism.