Mining information from time series in the form of sentences of natural language

The goal of this paper is to provide a more detailed explanation of the principles how special formulas that characterize properties of trend of time series can be formed and how they are interpreted. Then we show how these formulas can be used in a tectogrammatical tree that construes special sentences of natural language, using which information on behavior of time series is provided. We also outline the principles of mining this information. The last part is devoted to application of the theory of intermediate quantifiers to mining summarized information on time series also in sentences of natural language.     

Conflict-directed A and its role in model-based embedded systems

Artificial Intelligence has traditionally used constraint satisfaction and logic to frame a wide range of problems, including planning, diagnosis, cognitive robotics and embedded systems control. However, many decision making problems are now being re-framed as optimization problems, involving a search over a discrete space for the best solution that satisfies a set of constraints. The best methods for finding optimal solutions, such as A^*, explore the space of solutions one state at a time. This paper introduces conflict-directed A^*, a method for solving optimal constraint satisfaction problems. Conflict-directed A^* searches the state space in best first order, but accelerates the search process by eliminating subspaces around each state that are inconsistent. This elimination process builds upon the concepts of conflict and kernel diagnosis used in model-based diagnosis [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130; J. de Kleer, A. Mackworth, R. Reiter, Characterizing diagnoses and systems, Artif. Intell. 56 (1992) 197-222] and in dependency-directed search [R. Stallman, G.J. Sussman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artif. Intell. 9 (1977) 135-196; J. Gaschnig, Performance measurement and analysis of certain search algorithms, Technical Report CMU-CS-79-124, Carnegie-Mellon University, Pittsburgh, PA, 1979; J. de Kleer, B.C. Williams, Back to backtracking: controlling the ATMS, in: Proceedings of AAAI-86, 1986, pp. 910-917; M. Ginsberg, Dynamic backtracking, J. Artif. Intell. Res. 1 (1993) 25-46]. Conflict-directed A^* is a fundamental tool for building model-based embedded systems, and has been used to solve a range of problems, including fault isolation [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130], diagnosis [J. de Kleer, B.C. Williams, Diagnosis with behavioral modes, in: Proceedings of IJCAI-89, 1989, pp. 1324-1330], mode estimation and repair [B.C. Williams, P. Nayak, A model-based approach to reactive self-configuring systems, in: Proceedings of AAAI-96, 1996, pp. 971-978], model-compilation [B.C. Williams, P. Nayak, A reactive planner for a model-based executive, in: Proceedings of IJCAI-97, 1997] and model-based programming [M. Ingham, R. Ragno, B.C. Williams, A reactive model-based programming language for robotic space explorers, in: Proceedings of ISAIRAS-01, 2001].     

Homogeneous and strictly homogeneous criteria for partial structures

The Galois closure on the set of relations invariant to all finite partial automorphisms (automorphisms) of a countable partial structure is established via quantifier-free infinite predicate languages (infinite languages with finite string of quantifiers respectively). Based on it the homogeneous and strictly homogeneous criteria for a countable partial structure as well as an ultrahomogeneous criterion for a countable relational structure are found. Next it is shown that infinite languages with a finite string of quantifiers cannot determine the corresponding Galois closure for relations invariant to all automorphisms of an uncountable partial structure.     

Another look at graph coloring via propositional satisfiability

This paper studies the solution of graph coloring problems by encoding into propositional satisfiability problems. The study covers three kinds of satisfiability solvers, based on postorder reasoning (e.g., grasp, chaff), preorder reasoning (e.g., 2cl, 2clsEq), and back-chaining (modoc). The study evaluates three encodings, one of them believed to be new. Some new symmetry-breaking methods, specific to coloring, are used to reduce the redundancy of solutions. A by-product of this research is an implemented lower-bound technique that has shown improved lower bounds for the chromatic numbers of the long-standing unsolved random graphs known as DSJC125.5 and DSJC125.9. Independent-set analysis shows that the chromatic numbers of DSJC125.5 and DSJC125.9 are at least 18 and 40, respectively, but satisfiability encoding was able to demonstrate only that the chromatic numbers are at least 13 and 38, respectively, within available time and space.     

Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers

We prove convergence laws for logics of the form , where is a properly chosen collection of generalized quantifiers, on very sparse finite random structures. We also study probabilistic collapsing of the logics , where is a collection of generalized quantifiers and k ∈ ℕ₊, under arbitrary probability measures of finite structures.     

二值逻辑中命题的条件真度理论

基于条件概率的思想,在二值经典命题逻辑中引入条件真度的概念。在二值逻辑系统中初步给出了在信息Σ下的近似推理理论。     

中介逻辑演算系统MPN及MFN

为满足不完全信息系统应用的需要,本文构造了基于命题联结词∧、∨、→、ヲ、～和～的中介逻辑命题演算系统ＭＰＮ和中介逻辑谓词演算系统ＭＦＮ,并证明了ＭＰＮ与ＭＰ＊、ＭＦＮ与ＭＦ＊的表达能力等价。ＭＦＮ将为进一步讨论不完全信息数据库作准备     

On transformations of constant depth propositional proofs

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.     

Generalized domination in closure systems

In the context of extracting maximal item sets and association rules from a binary data base, the graph-theoretic notion of domination was recently used to characterize the neighborhood of a concept in the corresponding lattice.In this paper, we show that the notion of domination can in fact be extended to any closure operator on a finite universe and be efficiently encoded into propositional Horn functions. This generalization enables us to endow notions and algorithms related to Formal Concept Analysis with Horn minimization and minimal covers of functional dependencies in Relational Databases.