Defining the meaning of tabular mathematical expressions

Mathematical expressions in tabular form (also called “tabular expressions” or “tables”) have been shown to be useful for documenting and analysing software systems. They are usually easier to read than conventional mathematical expressions but are no less precise. They can be used wherever mathematical expressions are used. To avoid misunderstandings, and to support users with trustworthy tools, the meaning of these expressions must be fully defined.This paper presents a new method for defining the meaning of tabular expressions. Each definition of an expression type names the expression’s constituents, and provides a restriction schema and one or more evaluation schemas. The restriction schema defines the class of well-formed expressions of the type. An evaluation schema maps a well-formed tabular expression of the type to a mathematical expression of a previously defined type. Since the meaning of conventional mathematical expressions is well known, describing an equivalent expression fully defines the meaning of a tabular expression.In this approach, indexation is used to decouple the appearance of a tabular expression from its semantics. A tabular expression is an indexed set of grids; a grid is an indexed set of expressions. The expressions in a grid can be either conventional expressions or tabular expressions of a previously defined type.Defining the meaning of a tabular expression in this way facilitates the building of tools that faithfully implement the semantics. The decoupling of syntax and semantics by means of indices overcomes some limitations of older approaches.The method presented in the paper is illustrated by defining several previously known types of tabular expressions and some new ones. The use of the new model to build a suite of tools for the input, presentation, validation, evaluation, simplification, conversion and composition of tabular expressions is discussed.     

Algebraic Composition of Function Tables

In general, a program is composed of smaller program segments using composition, conditional constructs or loop constructs. We present a theory which enables us to algebraically define and compute the composition of conditional expressions. The conditional expressions are represented using tabular notation. The formal definition of the composition allows us to compute the close form representation of the composition of tabular expressions. The presented approach is based on a many sorted algebra containing information preserving composition. This formal definition of composition is then “lifted” to an extended algebra containing tabular expressions. The presented theory provides very compact algorithms and proofs. Received July 1998 / Accepted in revised form January 2000     

Tabular-expression-based method for constructing metamorphic relations

Metamorphic testing (MT) is proposed to overcome the oracle problem in software testing, and metamorphic relations (MRs) are the core of MT. There is a lack of guidelines for constructing effective MRs, and it is difficult to reuse MRs mainly because most MRs are closely related to the domain knowledge. In this article, we propose a method for constructing MRs from specifications in tabular expression format. Our method constructs MRs according to the characteristics of tabular expressions, especially the relationships between the header grids and the main grid, namely, our method is domain-independent and the construction process is simplified. In addition, the derived MRs can be applied to specifications with the same tabular expression structure. For specifications with different tabular expression structures, MRs can still be used after slight adjustments. To evaluate the performance of our method in practice, we apply the method to five applications. The experimental results demonstrate that our method is effective for a program with the oracle problem, and that it is applicable to tabular expressions in various formats. Compared with representative testing methods, our method identifies errors that are not detected by the compared methods. Hence, our method and existing methods can complement each other. The MR proposed in this article outperforms MRs constructed based on program properties.     

Learning constraints in spreadsheets and tabular data

Spreadsheets, comma separated value files and other tabular data representations are in wide use today. However, writing, maintaining and identifying good formulas for tabular data and spreadsheets can be time-consuming and error-prone. We investigate the automatic learning of constraints (formulas and relations) in raw tabular data in an unsupervised way. We represent common spreadsheet formulas and relations through predicates and expressions whose arguments must satisfy the inherent properties of the constraint. The challenge is to automatically infer the set of constraints present in the data, without labeled examples or user feedback. We propose a two-stage generate and test method where the first stage uses constraint solving techniques to efficiently reduce the number of candidates, based on the predicate signatures. Our approach takes inspiration from inductive logic programming, constraint learning and constraint satisfaction. We show that we are able to accurately discover constraints in spreadsheets from various sources.     

A mathematical analysis of the vibration characteristics of the human tibia

The frequencies and damping coefficients of a vibrating human tibia are studied in this paper, by modelling the tibia as a truncated conical structure. The experimentally observed principal mechanical properties of osseous tissues, viz. anisotropy, nonhomogeneity and material damping have been duly accounted for in the analysis. The applicability of the model has been illustrated through numerical computation of the derived analytical expressions. The computed values are presented in tabular form.     

Restructuring decision tables for elucidation of knowledge

Decision tables are widely used in many knowledge-based and decision support systems. They allow relatively complex logical relationships to be represented in an easily understood form and processed efficiently. This paper describes second-order decision tables (decision tables that contain rows whose components have sets of atomic values) and their role in knowledge engineering to: (1) support efficient management and enhance comprehensibility of tabular knowledge acquired by knowledge engineers, and (2) automatically generate knowledge from a tabular set of examples. We show how second-order decision tables can be used to restructure acquired tabular knowledge into a condensed but logically equivalent second-order table. We then present the results of experiments with such restructuring. Next, we describe SORCER, a learning system that induces second-order decision tables from a given database. We compare SORCER with IDTM, a system that induces standard decision tables, and a state-of-the-art decision tree learner, C4.5. Results show that in spite of its simple induction methods, on the average over the data sets studied, SORCER has the lowest error rate.     

Simplification of Switching Functions Involving a very Large Number of ‘Don't Care’ States†

A method of simplification of switching functions involving a very large number of ‘ don't care’ states is suggested in the present paper. First a tabular technique is suggested which generates all the prime implicants starting from the maxterm type expressions of switching functions, avoiding generation of the prime implicants formed of ‘don't care’ states only. The technique presented is simple and iterative. Next it is suggested how the knowledge of the sets of prime implicants thus obtained can be utilized for finding minimal or other irredundant sums of switching functions.     

Cobol generation of source programs and reports

SURGE, a COBOL pre-processor for the machine generation of source programs, is described. The article presents the coding procedure by which the user communicates with SURGE, and briefly introduces the general logic of both the pre-processor and generated programs. The main capabilities of SURGE are described as file sorting, selective retrieval and tabular report preparation, including multiple levels of totals and a capability for certain other kinds of computation. Non-proprietary and relatively machine-independent, this package appears to reduce the need for hand-crafted COBOL programs and to be remarkably easy to learn and use. It is suggested that SURGE also may offer a suitable prototype for extending the concept of source-program generation to other goals such as file updating and the production of FORTRAN programs.     

Correlation filter: an accurate approach to detect and locate low contrast character strings in complex table environment

Correlation has been used extensively in object detection field. In this paper, two kinds of correlation filters, minimum average correlation energy (MACE) and extended maximum average correlation height (EMACH), are applied as adaptive shift locators to detect and locate smudgy character strings in complex tabular color flight coupon images. These strings in irregular tabular coupon are computer-printed characters but of low contrast and could be shifted out of the table so that we cannot detect and locate them using traditional algorithms. In our experiment, strings are extracted in the preprocessing phase by removing background and then based on geometric information, two correlation filters are applied to locate expected fields. We compare results from two correlation filters and demonstrate that this algorithm is a high accurate approach.     

A new tabular form for determining root distribution of a complexpolynomial with respect to the imaginary axis

The original Routh table dealing with real polynomials is further investigated for complex polynomials. A tabular form for determining root distribution of a complex polynomial with respect to the imaginary axis is developed, and modified procedures for directly treating singularities in the array are proposed. Also, procedures are developed for determining the respective orders of simple and/or repeated roots lying on the imaginary axis. Conditional stability and instability can be distinguished from each other by the criteria developed here     

以问题结构为基础的递归程序设计

对递归程序的结构进行了较为深入的研究,提出了递归程序的更一般结构,根据此结构,给出了复杂的递归疸的程序设计方法,根据此方法,可方便地写出较为复杂的递归问题的递归程序,从而提高设计递归程序的效率。     

Make — a program for maintaining computer programs

Good programmers break their projects into a number of pieces, each to be processed or compiled by a different chain of programs. After a set of changes is made, the series of actions that must be taken can be quite complex, and costly errors are frequently made. This paper describes a program that can keep track of the relationships between parts of a program, and issue the commands needed to make the parts consistent after changes are made. Make has been in use on UNIX

1 UNIX is a trademark of Bell Laboratories.

systems since 1975. The underlying idea is quite simple and can be adapted to many other environments.     

Model comprehension for security risk assessment: an empirical comparison of tabular vs. graphical representations

Tabular and graphical representations are used to communicate security risk assessments for IT systems. However, there is no consensus on which type of representation better supports the comprehension of risks (such as the relationships between threats, vulnerabilities and security controls). Cognitive fit theory predicts that spatial relationships should be better captured by graphs. In this paper we report the results of two studies performed in two countries with 69 and 83 participants respectively, in which we assessed the effectiveness of tabular and graphical representations with respect to extraction correct information about security risks. The experimental results show that tabular risk models are more effective than the graphical ones with respect to simple comprehension tasks and in some cases are more effective for complex comprehension tasks. We explain our findings by proposing a simple extension of Vessey’s cognitive fit theory as some linear spatial relationships could be also captured by tabular models.     

Strategy Construction in the Higher-Order Framework of TL

When viewed from a strategic perspective, a labeled rule base in a rewriting system can be seen as a restricted form of strategic expression (e.g., a collection of rules strictly composed using the left-biased choice combinator). This paper describes higher-order mechanisms capable of dynamically constructing strategic expressions that are similar to rule bases. One notable difference between these strategic expressions and rule bases is that strategic expressions can be constructed using arbitrary binary combinators (e.g., left-biased choice, right-biased choice, sequential composition, or user defined). Furthermore, the data used in these strategic expressions can be obtained through term traversals.A higher-order strategic programming framework called TL is described. In TL it is possible to dynamically construct strategic expression of the kind mentioned in the previous paragraph. A demonstration follows showing how the higher-order constructs available in TL can be used to solve several problems common to the area of program transformation.     

编译原理中文法的教学探讨

在分析正规式、正规文法和上下文无关文法的基础上,着重讨论上下文无关文法中涉及到的一些重要的文法,例如二义文法、递归文法、LL（1）文法、LR（0）文法和SLR（1）文法,并以二义文法为主线,分析二义文法和递归文法、LL（1）文法、LR（0）文法和SLR（1）文法的关系,找出一些判定文法有无二义性的充分条件。     

Requirements Analysis for Engineering Computation: A Systematic Approach for Improving Reliability

This paper argues that the reliability of engineering computation can be significantly improved by adopting software engineering methodologies for requirements analysis and specification. The argument centers around the fact that the only way to judge the reliability of a system is by comparison to a specification of the requirements. This paper also points to methods for documenting the requirements. In particular, a requirements template is proposed for specifying engineering computation software. To make the mathematical specification easily understandable by all stakeholders, the requirements documentation employs the technique of using tabular expressions. To clarify the presentation, this paper includes a case study of the documentation for a system for analyzing statically determinant beams.     

Partiality and Nondeterminacy in Program Proofs

Specifications and programs make much use of nondeterministic and/or partial expressions, i.e. expressions which may yield several or no outcomes for some values of their free variables. Traditional 2-valued logics do not comfortably accommodate reasoning about undefined expressions, and do not cater at all for nondeterministic expressions. We seek to rectify this with a 4-valued typed logic E4 which classifies formulae as either “true”, “false”, “neither true nor false”, or “possibly true, possibly false”. The logic is derived in part from the 2-valued logic E and the 3-valued LPF, and preserves most of the theorems of E. Indeed, the main result is that nondeterminacy can be added to a logic covering partiality at little cost. Received July 1996 / Accepted in revised form April 1998     

基于PowerBuilder的动态报表设计

在开发MIS系统时需要创建大量报表,这些报表具有不确定性,其格式、内容和数量经常根据需求发生变化。文章提出了一种新的动态报表生成技术,即采用空模版与报表描述文件组合和动态合成方法,根据用户的需求,快速方便地增加、修改报表。该技术为MIS的开发和应用提供了有效的解决工具。该文详细介绍了基于PowerBuilder动态报表设计的方法和编程要点等。     

Computing polynomial program invariants

We present two automatic program analyses. The first analysis checks if a given polynomial relation holds among the program variables whenever control reaches a given program point. It fully interprets assignment statements with polynomial expressions on the right-hand side and polynomial disequality guards. Other assignments are treated as non-deterministically assigning any value and guards that are not polynomial disequalities are ignored. The second analysis extends this checking procedure. It computes the set of all polynomial relations of an arbitrary given form that are valid at a given target program point. It is also complete up to the abstraction described above.