Decision tables for general-purpose scientific programming

Decision tables are shown, by example, to be a viable alternative to conventional algorithmic languages for general-purpose scientific programming.     

Decision tables: Formalisation,validation, and verification

The decision table is one of the simplest representations of the rules underlying a systematic decision-making process, and is especially valuable in the development of knowledge-based systems. A two dimensional table links all relevant combinations of input conditions to the desired combinations of output actions in a very intuitive way. This simplicity belies the complex considerations involved in verifying, validating, formulating or interpreting this (or any other) representation of machine-based knowledge. In this paper, the common styles of decision table representation are reviewed, a formulation of their meaning is presented, construction methods are reviewed, and an algorithm for ensuring consistency is suggested. The problems that may occur in imperfectly constructed tables are discussed, detection methods reviewed, and some implementation methods are presented.     

New techniques for COBOL programmers

Structured programming has become one of the most widely discussed topics among DP professionals. Despite this, however, COBOL programmers, responsible for the majority of ‘bread and butter jobs’, have been left mostly on their own. The article attempts to review the history of programming and list the areas essential for any future improvement and advancement of the programming profession, inclusive of systems analysis, education and training, and programming methodology. An alternative approach to structured programming in COBOL using decision tables is outlined and confronted with the concept of the so-called functional programming.     

A programming language engineered for beginners

As the complexity and size of programs increase, the programmer is challenged with the task of organizing his program in a manner which will enhance intellectual manageability. Thus, the structure and style are critical in regards to writing programs and verifying their correctness. In recent years, considerable emphasis has been placed on the correctness of programs and techniques for engineering them to be correct. However, more emphasis should be placed on designing languages which facilitate constructing correct programs. In an effort to partially address this problem, a language is described which permits users the convenient development of well-structured programs that are easy to read and understand, easy to correct (debug) and modify, and easy to verify the correctness of the program. The language presented permits the use of decision tables for expressing complex logic.     

Decision tables in Algol 68

Two methods for extending Algol 68 to handle decision tables are described. One method allows an extension to Algol 68 to handle limited entry decision tables while the other method, which involves the use of a preprocessor, extends Algol 68 to handle mixed entry decision tables. Two systems have been constructed using the ideas outlined in this paper; these are described and examples of their use are given.     

广义信息系统及其决策规则

提出一类更广泛的信息系统,称其为广义信息系统．它包含了完备信息系统、不完备信息系统和多值信息系统．给出了广义信息系统集合近似的概念、方法和相关性质．讨论了广义信息决策系统的决策描述形式．这种决策描述形式易于转化为Skolem标准型,可以直接应用于人工智能的归结推理．     

A pre-processor using rule mask techniques for extended entry decision tables

The implementation of a pre-processor for extended entry decision tables is described. If ambiguities exist in the decision tables they are detected by the pre-processor. The paper discusses what actions should be taken in this case.     

From decision tables to expert system shells

Building and maintaining high quality knowledge based systems is not a trivial task. Decision tables have sometimes been recommended in this process, mainly in verification and validation. In this paper, however, it is shown how decision tables can also be used to generate, and not just to validate, knowledge bases and how the transformation process from decision tables to knowledge bases can be organized. Several options to generate rules or other knowledge representation from decision tables are described and evauluated.

The proposed generation strategy enables the knowledge engineer to concentrate on the acquisition and modelling issues and allows him to isolate the knowledge body from its implementation. The generation process has been implemented for two commercial tools, AionDS and KBMS and has been applied to real world applications.     

Introducing functional classification theory to land use planning by means of decision tables

This paper contributes to the conceptualisation and analysis of double-sided matching problems, taking the land use planning problem as an example. It does so by introducing functional classification theory at the knowledge level, the symbol level and the system level of a DSS. This theory explicitly expresses the methodological viewpoint of relational realism. At the knowledge level this implies defining knowledge on the basis of matching the intension and extension of concepts. At the symbol level it deals with knowledge representation and here decision tables are advanced and formally introduced. At the system level the formalism used at the symbol level is implemented to develop a relational matching DSS.     

不协调决策表中基于对象的近似约简

对不协调决策表中基于对象的近似约简问题展开研究。首先,给出近似约简的判定定理;其次,通过区分矩阵与区分函数给出约简的计算方法;最后,通过实例验证,决策表中基于对象的近似约简与整体约简相比,不仅可以获得更简洁的知识,并且在实际生活中具有较好的应用价值。     

遗传算法在决策表最小约简中的应用

基于粗集理论和扩张矩阵理论,利用遗传算法,提出一种求解最小约简的优化方法,实验说明,此方法能以较大的概率全面获得决策表的最小约简,实用性较强。     

一种基于相对粒度的决策表约简算法

在知识粒度的基础上,针对决策表提出了相对粒度和属性相对重要性的概念,证明了知识的相对粒度随着知识粒度的增大而单调增加的变化规律,在此基础上提出了一种基于相对粒度的启发式约简算法,以弥补基于正区域的约简方法处理不一致决策表时存在的不足.通过理论分析和实例验证表明,该算法是有效的,且其时间复杂度相对较低.     

青少年机器人足球比赛系统决策编程的可视化

分析了机器人足球比赛系统中决策子系统的一般结构，建立了产生式推理模型和决策的表达模型，构造了机器人足球比赛系统的决策程序的结构；定义了决策存储的结构体变量类型，设计了菜单，并以此形式实现了决策编程的可视化。     

一种基于关系矩阵的决策表正域约简算法

研究了粗糙集属性约简问题,引入等价关系矩阵的诱导矩阵和矩阵的λ-截矩阵等概念来计算决策表的上、下近似集,进而给出基于关系矩阵的决策表正域求解方法,并从理论上证明了该方法的正确性。提出了粗糙集属性核的启发式约简,并用该方法计算最小约简,在属性动态增加时,用矩阵快速更新的方法来改变属性等价关系矩阵,可以快速地计算属性变化后的正域。最后,通过实例分析说明了属性约简的具体操作方法和算法的有效可行性。     

Compact coding of syntax tables

A method for constructing compact syntax tables in three steps is presented. First, the rules of a grammar are mapped into a syntax graph, from which five syntactic forms are defined. Secondly, the grammar expressed in these syntactic forms is mapped into data structures. Finally, from the data structures, the compact syntax table of the grammar is constructed.     

Yet another storage technique for lr parsing tables

A submatrix storage scheme for sparse matrices is presented which has been found useful for storing LR parsing tables. It is not the most compact representation but it is easy to use and of order (1) in speed of access. The method is compared with the two most popular methods of storing LR parsing tables which use ‘linear lists’ and ‘row displacement’. Results of using the submatrix method to store the parsing tables for the Pascal language are included.     

Task-dependent processing of tables and graphs

In two experiments participants had to detect changes in periodic sinusoidal functions, displayed in either graphic or tabular displays. Graphs had a major advantage over tables when the task required considering configurations of data. Both displays led to similar results when task performance could rely on inspecting individual data points. With graphs almost all participants reported using the optimal method for detecting changes in the function, i.e., they used the method requiring the least effort to perform the task. With tables only about half used the optimal detection method, and these participants showed transfer of learning of detection methods between tasks. Experience in using a detection method led to improved performance if the new task relied on the same method of detection. These findings demonstrate the need to consider task performance methods when determining the relative value of different displays. The set of tasks for which a display is used is likely to affect performance and needs to be analysed as a whole, since methods employed for one task can affect task performance in other tasks.     

Lock-free dynamic hash tables with open addressing

We present an efficient lock-free algorithm for parallel accessible hash tables with open addressing, which promises more robust performance and reliability than conventional lock-based implementations. "Lock-free" means that it is guaranteed that always at least one process completes its operation within a bounded number of steps. For a single processor architecture our solution is as efficient as sequential hash tables. On a multiprocessor architecture this is also the case when all processors have comparable speeds. The algorithm allows processors that have widely different speeds or come to a halt. It can easily be implemented using C-like languages and requires on average only constant time for insertion, deletion or accessing of elements. The algorithm allows the hash tables to grow and shrink when needed. Lock-free algorithms are hard to design correctly, even when apparently straightforward. Ensuring the correctness of the design at the earliest possible stage is a major challenge in any responsible system development. In view of the complexity of the algorithm, we turned to the interactive theorem prover PVS for mechanical support. We employ standard deductive verification techniques to prove around 200 invariance properties of our algorithm, and describe how this is achieved with the theorem prover PVS. CR Subject Classification (1991): D.1 Programming techniques AMS Subject Classification (1991): 68Q22 Distributed algorithms, 68P20 Information storage and retrieval Received: 13 April 2004, Accepted: 27 October 2004, Published online: 25 November 2004     

基于决策背景的决策蕴涵规范基

主要给出决策背景下的决策蕴涵基,通过不确定的分组阈值对决策背景进行分组,找到每个分块的决策背景下的决策蕴涵规范基,并证明了每个分块上的决策蕴涵集是完备、无冗余和最优的;也证明了每个决策背景分块上的决策蕴涵基的集合在整个决策背景上也是完备、无冗余和最优的。在生成决策背景的决策蕴涵规范基的过程中,优化了最小生成子算法;同时也给出了基于决策背景的决策蕴涵规范基的生成算法。实验表明,通过分组策略和算法的优化改进,可以很好地抑制冗余决策蕴涵规范基的生成,使决策蕴涵规范基更为有效和紧凑。     

Hashing as a compaction technique for parser tables

Authors of papers on LR parser table compaction and authors of books on compiler construction appear to have either overlooked or discounted the possibility of using hashing. In fact, hashing is easy to implement as a compaction technique and gives reasonable performance. It produces tables that are as compact as some of the other techniques reported in the literature while permitting efficient table lookups.