Correction to: Connecting Knowledge Compilation Classes and Width Parameters

Theory of Computing Systems - The article title in the original publication contains an error. The correct title is presented in this Erratum. The online version of the original article can be...     

Theory Revision with Queries: DNF Formulas

The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.     

A Unifying Approach to Edge-valued and Arithmetic Transform Decision Diagrams

This paper shows that binary decision diagrams (BDDs) and their generalizations are not only representations of switching and integer-valued functions, but also Fourier-like series expansions of them. Furthermore, it shows that edge-valued binary decision diagrams (EVBDDs) are related to arithmetic transform decision diagrams (ACDDs), which are the integer counterparts of the functional decision diagrams (FDDs). Finally, it shows that the complexity of multi-terminal binary decision diagrams (MTBDDs), EVBDDs and ACDDs of a function f depends on the structure of the truth-vector of f, partial arithmetic transform spectra of f and the arithmetic transform spectrum of f, respectively.     

Special Feature Program Testing: Art Meets Theory*

The problems of providing quality assurance for computer software have received a good deal of attention from the computing community. Such areas as program proving, automatic programming, structured programming, and hierarchical design/development methodologies have all experienced significant growth–largely as a result of the increased attention focussed on them. Program testing, on the other hand, has not enjoyed the same level of intensive investigation, even though it has a number of technical and intuitive appeals:     

不一致决策表下基于D-S证据理论的知识约简

对于一致决策表,基于D-S证据理论的知识约简与代数约简所得的结果是一致的,对于不一致决策表,它们并不完全一致.本文通过具体算例说明了基于D-S证据理论的广义决策约简与代数约简的在不一致决策表下的差异性.理论上证明了广义决策约简仅与分配约简是等价的,提出一种基于D-S证据理论求代数约简的方法.理论分析和算例都证明了本文方法的正确性.     

Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation

In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n×n Walsh matrix, for example, the BDD representation is of size O(log n). No other special-case representation in common use represents this matrix in space less than O(n²). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.     

不一致决策表的知识约简方法研究

日前计算不一致决策表的分布约筒、最大分布约筒和分配约筒的方法均基于可辨识属性矩阵,在大数据集下耗时较多.为此,提出转化算法,将计算原不一致决策表的上述3种约简转化为计算3种一致决策表的Pawlak约筒,通过应用针对后者的高效启发式算法,有效地减少了计算时间．此外,引入λ-约筒的概念,通过调节A的值,能得到一族反映决策矢量不同水平相似程度的知识约筒．该方法降低了分布约筒对决策表区分能力的过高要求,较上述3种约筒更为灵活。     

Information Theory Approach to Statistical Decision Problems

The use of information theory concepts in statistical decision problems is examined. It is shown that the average risk of decision-making is related to the amount of information contained in observations. This is used as a basis for estimating the minimum average risk of decision-making. A number of examples are considered     

Decision Planning Knowledge Representation Framework: A Case-Study

This paper discusses experiences and perspectives of utilisation of declarative knowledge structures as a convenient knowledge base medium in configuration expert systems. Although many successful systems have been developed, these are often difficult to maintain and to generalize in rapidly changing domains. In this paper we address the problem of building intelligent knowledge based systems with emphasis on their maintainability. Firstly, several industrial applications of proof planning, a theorem proving technique, will be described and their advantages and flaws will be discussed. This discussion is followed by the theoretical foundation of decision planning knowledge representation framework that, based on proof planning, facilitates separate administration of inference problem solving knowledge and the domain theory axioms. Machine learning methods for maintaining the inference knowledge to be up-to-date with permanently changing domain theory are commented and evaluated.     

在专家系统中利用关系数据库来表达知识

在专家系统中,传统的知识表达方式具有很大的局限性,知识的重复利用率不高,并且无法给出知识的关系。为了解决这个问题,文章利用关系数据库的特点,将知识存贮在数据库中,并结合推理机的工作原理,阐明了如何利用标准数据查询语言(SQL)来对知识库进行正向推理及反向推理。从而提高了推理机的效率,减少知识获取的开销,增强知识库的可维护性和扩展性。     

利用SQL Server和VB实现分布式历史数据的存储与查询

本文针对石化企业技术改造任务中历史数据库部分,介绍了ＳＱＬ Ｓｅｒｖｅｒ下分布式历史数据库的设计、存储、查询的实现以及数据压缩的应用。     

基于知识粗糙度的决策树生成方法

决策树是一种重要的数据分类方法,测试属性的选择直接影响到决策树中结点的个数和深度,本文提出了一种基于知识粗糙度的方法。通过比较我们发现：在决策树的构造上,粗集理论中知识粗糙度的方法计算量较小,构造的决策树比经典ID3算法简洁,并且具有较高的分类精度。     

基于知识粗糙度的决策树生成方法

决策树是一种重要的数据分类方法,测试属性的选择直接影响到决策树中结点的个数和深度,本文提出了一种基于知识粗糙度的方法.通过比较我们发现:在决策树的构造上,粗集理论中知识粗糙度的方法计算量较小,构造的决策树比经典ID3算法简洁,并且具有较高的分类精度.     

“数据库与程序设计”教学研究与实践

VFP是一种用来进行管理信息系统开发的常用工具,是高等学校计算机专业以及非计算机专业的一门主干课。本文结合VFP课程的主要教学内容,分析了该课程的主要特点以及传统教学中存在的主要问题,提出任务驱动教学法是适合VFP课程教学、避免现有教学方式中多种弊端的教学方法,通过探索实践取得了较好的教学效果。     

Answers to Queries to Internet: An Optimal Generation Strategy

Representation of the answers to a query to Internet as a list of hypertext references to found objects is studied. Optimization of the strategy for choosing between static and dynamic references by criteria of server performance and reliability of information on an object is investigated. A probabilistic model is developed. Two strategies providing 100% reliability and admitting obsolete information with some probability are designed. Formulas for choosing a strategy are derived. Examples are given to illustrate their application to exponential distributions admitting an analytical solution. More complex distributions require the application of numerical methods of inverse Laplace transformation, integration, and optimization.     

Integration of Temporal Reasoning and Temporal-Data Maintenance into a Reusable Database Mediator to Answer Abstract, Time-Oriented Queries: The Tzolkin System

The ability to reason with time-oriented data is central to the practice of medicine. Monitoring clinical variables over time often provides information that drives medical decision making (e.g., clinical diagnosis and therapy planning). Because the time-oriented patient data are often stored in electronic databases, it is important to ensure that clinicians and medical decision-support applications can conveniently find answers to their clinical queries using these databases. To help clinicians and decision-support applications make medical decisions using time-oriented data, a database-management system should (1) permit the expression of abstract, time-oriented queries, (2) permit the retrieval of data that satisfy a given set of time-oriented data-selection criteria, and (3) present the retrieved data at the appropriate level of abstraction. We impose these criteria to facilitate the expression of clinical queries and to reduce the manual data processing that users must undertake to decipher the answers to their queries. We describe a system, Tzolkin, that integrates a general method for temporal-data maintenance with a general method for temporal reasoning to meet these criteria. Tzolkin allows clinicians to use SQL-like temporal queries to retrieve both raw, time-oriented data and dynamically generated summaries of those data. Tzolkin can be used as a standalone system or as a module that serves other software systems. We implement Tzolkin with a temporal-database mediator approach. This approach is general, facilitates software reuse, and thus decreases the cost of building new software systems that require this functionality.     

面向语言信息处理的朝鲜语知识库研究

在自然语言处理系统(包括机器翻译系统) 中,语法、语义信息词典是必不可少的构件。本文以国内外语义工程研究成果为基础,通过对朝鲜语谓词进行句法语义一体化描述,建立面向信息处理的朝鲜语知识库。该研究的语言学理论根据是论元结构理论和语义场理论。我们首先对谓词进行语义分类,然后再对谓词义项作详细的属性描述。在知识库构建上,采用结构体方式将谓词的句法、语义等属性整合在一起。