Theorem proving for intensional logic

For a number of tasks in knowledge representation, and particularly in natural language semantics, it is useful to be able to treat propositions and properties as objects — as items that can appear as arguments of predicates, as things one can quantify over, and so on. Logics that support such intensional operations are notoriously hard to work with. The current paper presents a theorem prover for one such logic, namely, Turner's property theory.     

新一代人工智能十问十答

新一代人工智能是我国在全球第一个面向2030年提出的国家重大发展战略。如何认识新一代人工智能和传统人工智能的不同,了解其内涵、外延、技术特征以及发展目标,从而更好地凝聚研发队伍,是实现这一战略的重要保证。本文围绕新一代人工智能的技术内核,提出十个主要问题,自问自答,大问小答,指出新一代人工智能将从传统的计算机智能跃升为无意识的类脑智能,是人类智能的体外延伸,不涉及生命和意识,由人赋予意图,通过有指导的传承学习和自主学习,能够与时俱进地解释、解决新的智力问题,形成有感知、有认知、有行为、可交互、会学习、自成长的新一代人工智能—智能机器。     

Efficient execution of composite Web services exchanging intensional data

Web service technologies provide a standard means of integrating heterogeneous applications distributed over the Internet. Successive compositions of new Web services using pre-existing ones usually create a hierarchical structure of invocations among a large number of Web services. For the efficient execution of these composite Web services, we propose an approach which exploits intensional XML data, i.e. an XML document that contains special elements representing the calls to Web services, in order to delegate the invocations of the external Web services to some relevant nodes. We formalize an invocation plan for composite Web services in which intensional data is used as their parameters and results, and define a cost-based optimization problem to obtain an efficient invocation plan for them. We provide an A∗ heuristic search algorithm to find an optimal invocation plan for a given set of Web services and also present a greedy method of generating an efficient solution in a short time. The experimental results show that the proposed greedy method can find a close-to-optimal solution efficiently and has good scalability for a complex call hierarchy of Web services.     

A 3D spreadsheet based on intensional logic

A three-dimensional spreadsheet design based on intensional logic is proposed. Intensional logic is concerned with assertions and other expressions whose meaning depends on an implicit context. The intensional spreadsheet is a declarative spreadsheet with a simple formal semantics called intensional semantics. It is expected to be suitable for a wide range of applications and for various users, including those who have had conventional programming experience. As an example of using the intensional 3-D spreadsheet, the formalization of a systolic algorithm for matrix multiplication is considered     

An intensional approach for periodic data in relational databases

Periodic data play a major role in many application domains, spanning from manufacturing to office automation, from scheduling to data broadcasting. In many of such domains, the huge number of repetitions make the goal of extesionally storing and accessing such data very challenging. In this paper, we propose a new methodology, based on an intensional representation of periodic data. The representation model we propose captures the notion of periodic granularity provided by the temporal database glossary, and is an extension of the TSQL2 temporal relational data model. We define the algebraic operators, and introduce access algorithms to cope with them, proving that they are correct with respect to the traditional extesional approach. We also provide an experimental evaluation of our approach.     

Scalable computation of the extensional and intensional stability of formal concepts

The effective use of the concept lattice in large datasets has been always limited by the large volume of extracted knowledge. The stability measure has been shown to be of valuable help for knowledge selection. In this paper, we introduce the SC-MG algorithm to efficiently compute both types of stability, i.e. extensional and intensional. The guiding idea is to exploit the relationship between stability and minimal generators in order to compute both measures. The performed experiments show the efficiency of the SC-MG algorithm. In addition, it sharply outperforms the pioneering approaches of the literature.     

Making computational sense of Montague's intensional logic

Montague's difficult notation and complex model theory have tended to obscure potential insights for the computer scientist studying Natural Language. Despite his strict insistence on an abstract model-theoretic interpretation for his formalism, we feel that Montague's work can be related to procedural semantics in a fairly direct way. A simplified version of Montague's formalism is presented, and its key concepts are explicated in terms of computational analogues. Several examples are presented within Montague's formalism but with a view toward developing a procedural interpretation. We provide a natural translation from intensional logic into lisp. This allows one to express the composition of meaning in much the way Montague does, using subtle patterns of functional application to distribute the meanings of individual words throughout a sentence. The paper discusses some of the insights this research has yielded on knowledge representation and suggests some new ways of looking at intensionality, context, and expectation.     

Combining intensional with extensional query evaluation in tuple independent probabilistic databases

In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm [24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well.     

An intensional approach to qualitative and quantitative periodicity‐dependent temporal constraints

In this paper, we propose a framework for representing and reasoning about qualitative and quantitative temporal constraints between periodic events. In particular, our contribution is twofold: (i) we provide a formalism to deal with both qualitative and quantitative “periodicity‐dependent” constraints between repeated events, considering user‐defined periodicities as well; and (ii) we propose an intensional approach to temporal reasoning, which is based on the operations of intersection and composition. Such a comprehensive approach, to the best of our knowledge, represents an innovative contribution that integrates and extends results from both the artificial intelligence and the temporal databases literature. © 2009 Wiley Periodicals, Inc.     

Declarative diagnosis of missing answers

This paper investigates algorithms for declarative diagnosis of missing answers in Prolog programs, especially programs which use coroutines. The logic of the problem is first presented, in the form of the simplest possible debugger. Next, we compare several previously published declarative debuggers based on Shapiro’s work. Examples showing incompleteness, incorrectness and equivalence of debuggers are given. Several enhancements to these debuggers are presented which can reduce the number and complexity of questions asked of the oracle, while still supporting coroutines. Although no debugger considered is best in all cases, the new algorithms are a practical contribution. Finally, we discuss diagnosis algorithms based more on Pereira’s work. These algorithms ask easier questions than Shapiro’s algorithms but rely on the standard left to right computation rule. We discuss possible ways to adapt these algorithms to handle coroutining. Completeness of debuggers is also discussed.     

Intensional answers to database queries

In addition to data, database systems store various kinds of information about their data. Examples are: class hierarchies, to define the various data classes and their relationships; integrity constraints, to state required relationships among the data; and inference rules, to define new classes in terms of known classes. This information is often referred to as intensional information (the data are referred to as extensional information). There have been several independent research works that suggested ways by which intensional information may be used to improve the conventional (extensional) database answers. Although each of these efforts developed its own specific methods, they all share a common belief: database answers would be improved if accompanied by intensional statements that describe them more abstractly. We study and compare the various approaches to intensional answers by using various classifications; we examine their relative merits with regard to key aspects; we discuss remaining issues; and we offer new research directions     

Computing answers with model elimination

We demonstrate that theorem provers using model elimination (ME) can be used as answer-complete interpreters for disjunctive logic programming. More specifically, we introduce a family of restart variants of model elimination and we introduce a mechanism for computing answers. Building on this, we develop a new calculus called ancestry restart ME. This variant admits a more restrictive regularity restriction than restart ME and, as a side-effect, it is in particular attractive for computing definite answers. The presented calculi can also be used successfully in the context of automated theorem proving. We demonstrate experimentally that it is more difficult to compute nontrivial answers to goals than to prove the existence of answers.