Third-order Idealized Algol with iteration is decidable

The problems of contextual equivalence and approximation are studied for the third-order fragment of Idealized Algol with iteration (). They are approached via a combination of game semantics and language theory. It is shown that for each -term one can construct a pushdown automaton recognizing a representation of the strategy induced by the term. The automata have some additional properties ensuring that the associated equivalence and inclusion problems are solvable in Ptime. This gives an Exptime decision procedure for the problems of contextual equivalence and approximation for β-normal terms. Exptime-hardness of the problems, even for terms without iteration, is also shown.     

Backtracking games and inflationary fixed points

We define a new class of games, called backtracking games. Backtracking games are essentially parity games with an additional rule allowing players, under certain conditions, to return to an earlier position in the play and revise a choice or to force a countback of the number of moves. This new feature makes backtracking games more powerful than parity games. As a consequence, winning strategies become more complex objects and computationally harder. The corresponding increase in expressiveness allows us to use backtracking games as model-checking games for inflationary fixed-point logics such as IFP or MIC. We identify a natural subclass of backtracking games, the simple games, and show that these are the “right” model-checking games for IFP by (a) giving a translation of formulae φ and structures into simple games such that if, and only if, Player 0 wins the corresponding game and (b) showing that the winner of simple backtracking games can again be defined in IFP.     

Minimal model generation for refined answering of generalized queries in disjunctive deductive databases

Generalized queries are defined as sets of clauses in implication form. They cover several tasks of practical importance for database maintenance such as answering positive queries, computing database completions and integrity constraints checking. We address the issue of answering generalized queries under the minimal model semantics for the class of disjunctive deductive databases (DDDBs). The advanced approach is based on having the query induce an order on the models returned by a sound and complete minimal model generating procedure. We consider answers that are true in all and those that are true in some minimal models of the theory. We address the issue of answering positive queries through the construction of the minimal model state of the DDDB, using a minimal model generating procedure. The refinements allowed by the procedure include isolating a minimal component of a disjunctive answer, the specification of possible updates to the theory to enable the derivability of certain queries and deciding the monotonicity properties of answers to different classes of queries.     

Games with winning conditions of high Borel complexity

We first consider infinite two-player games on pushdown graphs. In previous work, Cachat et al. [Solving pushdown games with a Σ₃-winning condition, in: Proc. 11th Annu. Conf. of the European Association for Computer Science Logic, CSL 2002, Lecture Notes in Computer Science, Vol. 2471, Springer, Berlin, 2002, pp. 322–336] have presented a winning decidable condition that is Σ₃-complete in the Borel hierarchy. This was the first example of a decidable winning condition of such Borel complexity. We extend this result by giving a family of decidable winning conditions of arbitrary finite Borel complexity. From this family, we deduce a family of decidable winning conditions of arbitrary finite Borel complexity for games played on finite graphs. The problem of deciding the winner for these conditions is shown to be non-elementary.     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.     

What makes propositional abduction tractable

Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. This process underlies many applications, from car configuration to medical diagnosis. We study here the computational complexity of deciding whether an explanation exists in the case when the application domain is described by a propositional knowledge base. Building on previous results, we classify the complexity for local restrictions on the knowledge base and under various restrictions on hypotheses and manifestations. In comparison to the many previous studies on the complexity of abduction we are able to give a much more detailed picture for the complexity of the basic problem of deciding the existence of an explanation. It turns out that depending on the restrictions, the problem in this framework is always polynomial-time solvable, NP-complete, coNP-complete, or -complete.

Based on these results, we give an a posteriori justification of what makes propositional abduction hard even for some classes of knowledge bases which allow for efficient satisfiability testing and deduction. This justification is very simple and intuitive, but it reveals that no nontrivial class of abduction problems is tractable. Indeed, tractability essentially requires that the language for knowledge bases is unable to express both causal links and conflicts between hypotheses. This generalizes a similar observation by Bylander et al. for set-covering abduction.     

LTL over integer periodicity constraints

Periodicity constraints are used in many logical formalisms, in fragments of Presburger LTL, in calendar logics, and in logics for access control, to quote a few examples. In the paper, we introduce the logic PLTL^mod, an extension of Linear-Time Temporal Logic LTL with past-time operators whose atomic formulae are defined from a first-order constraint language dealing with periodicity. Although the underlying constraint language is a fragment of Presburger arithmetic shown to admit a PSPACE-complete satisfiability problem, we establish that PLTL^mod model-checking and satisfiability problems remain in PSPACE as plain LTL (full Presburger LTL is known to be highly undecidable). This is particularly interesting for dealing with periodicity constraints since the language of PLTL^mod has a language more concise than existing languages and the temporalization of our first-order language of periodicity constraints has the same worst case complexity as the underlying constraint language. Finally, we show examples of introduction the quantification in the logical language that provide to PLTL^mod, EXPSPACE-complete problems. As another application, we establish that the equivalence problem for extended single-string automata, known to express the equality of time granularities, is PSPACE-complete by designing a reduction from QBF and by using our results for PLTL^mod.     

Causal reasoning by evaluating the complexity of conditional densities with kernel methods

We propose a method to quantify the complexity of conditional probability measures by a Hilbert space seminorm of the logarithm of its density. The concept of reproducing kernel Hilbert spaces (RKHSs) is a flexible tool to define such a seminorm by choosing an appropriate kernel. We present several examples with artificial data sets where our kernel-based complexity measure is consistent with our intuitive understanding of complexity of densities.

The intention behind the complexity measure is to provide a new approach to inferring causal directions. The idea is that the factorization of the joint probability measure P(effect,cause) into P(effect|cause)P(cause) leads typically to “simpler” and “smoother” terms than the factorization into P(cause|effect)P(effect). Since the conventional constraint-based approach of causal discovery is not able to determine the causal direction between only two variables, our inference principle can in particular be useful when combined with other existing methods.

We provide several simple examples with real-world data where the true causal directions indeed lead to simpler (conditional) densities.     

Probabilistic rebound Turing machines

This paper introduces a probabilistic rebound Turing machine (PRTM), and investigates the fundamental property of the machine. We first prove a sublogarithmic lower space bound on the space complexity of this model with bounded errors for recognizing specific languages. This lower bound strengthens a previous lower bound for conventional probabilistic Turing machines with bounded errors. We then show, by using our lower space bound and an idea in the proof of it, that

Full-size image

where £[PRTM(o(logn))] denotes the class of languages recognized by o(logn) space-bounded PRTMs with error probability less than . Furthermore, we show that there is an infinite space hierarchy for £[PRTM(o(logn))]. We finally show that £[PRTM(o(logn))] is not closed under concatenation, Kleene +, and length-preserving homomorphism. This paper answers two open problems in a previous paper.     

An improved lower bound on approximation algorithms for the Closest Substring problem

The Closest Substring problem (the CSP problem) is a basic NP-hard problem in the study of computational biology. It is known that the problem has polynomial time approximation schemes. In this paper, we prove that unless the Exponential Time Hypothesis fails, the CSP problem has no polynomial time approximation schemes of running time f(1/ε)n^o(1/ε) for any function f. This essentially excludes the possibility that the CSP problem has a practical polynomial time approximation scheme even for moderate values of the error bound ε. As a consequence, it is unlikely that the study of approximation schemes for the CSP problem in the literature would lead to practical approximation algorithms for the problem for small error bound ε.     

An approximate algorithm for top-k closest pairs join query in large high dimensional data

In this paper we present a novel approximate algorithm to calculate the top-k closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity and space complexity and guarantees a solution within a factor of the exact one, where t  {1, 2, … , ∞} denotes the Minkowski metrics L_t of interest and d the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most d + 1 sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm behaves as an exact algorithm in low dimensional spaces; it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; in any case it returns a solution within a small error to the exact one.     

Mean behaviour and distribution properties of multiplicative functions

Mean-value theorems with sharp quantitative remainder term estimates and theorems on the distribution of values are proved for a large class of multiplicative functions. This class is characterized by the existence of an abscissa of absolute convergence ≤ 1 for the Dirichlet series of the quotient , where is the Dirichlet series associated with ƒ and ζ(s) denotes the Riemann zeta function. In particular, the mean behaviour of ƒ on certain sequences a, namely, that of Mersenne numbers 2ⁿ −1 and that of shifted primes p−1 with natural n and prime p, respectively, is studied and cluster points of the image sequence f(a) of a are determined. The strength of the results is demonstrated by new results for some specific functions.     

Triple positive solutions for some second-order boundary value problem on a measure chain

In this paper, we study the existence of three positive solutions for the second-order two-point boundary value problem on a measure chain,

where f:[t₁,σ(t₂)]×[0,∞)×R→[0,∞) is continuous and p:[t₁,σ(t₂)]→[0,∞) a nonnegative function that is allowed to vanish on some subintervals of [t₁,σ(t₂)] of the measure chain. The method involves applications of a new fixed-point theorem due to Bai and Ge [Z.B. Bai, W.G. Ge, Existence of three positive solutions for some second order boundary-value problems, Comput. Math. Appl. 48 (2004) 699–707]. The emphasis is put on the nonlinear term f involved with the first order delta derivative x^Δ(t).     

基于空值修复的数据库一致性查询方法*

完整性约束常用来定义数据库的数据语义,违反约束的数据库实例为不一致数据库,返回含有不一致结果的查询称为不一致查询。一致性查询目的在于不修改数据库实例而从不一致数据库获取满足约束的查询结果,已有方法因其支持的约束类型有限或计算复杂度高而影响其应用范围。提出了一种基于空值修复的数据库一致性查询方法,首先将原始完整性约束转换为与查询相关的统一约束,然后根据统一约束对原SQL查询进行查询重写,重写后的查询将不一致属性值当做空值来处理以获得满足完整性约束的结果。系统实现与实验证明,该方法在多种完整性约束类型与SQL     

A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs

Many robust control problems can be formulated in abstract form as convex feasibility programs, where one seeks a solution x that satisfies a set of inequalities of the form . This set typically contains an infinite and uncountable number of inequalities, and it has been proved that the related robust feasibility problem is numerically hard to solve in general.

In this paper, we discuss a family of cutting plane methods that solve efficiently a probabilistically relaxed version of the problem. Specifically, under suitable hypotheses, we show that an Analytic Center Cutting Plane scheme based on a probabilistic oracle returns in a finite and pre-specified number of iterations a solution x which is feasible for most of the members of , except possibly for a subset having arbitrarily small probability measure.     

Improved construction for universality of determinant and permanent

Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249–261] proved that every polynomial of formula size e is a projection of the (e+2)×(e+2) determinant polynomial. We improve “e+2” to “e+1”, also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the “2e+2” proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137–172], but uses different invariants and a tighter set of base cases.     

A characterization theorem for injective model classes axiomatized by general rules

We continue the work in Zhu et al. [Normal conditions for inference relations and injective models, Theoret. Comput. Sci. 309 (2003) 287–311]. A class Ω of strict partial order structures (posets, for short) is said to be axiomatizable if the class of all injective preferential models from Ω may be characterized in terms of general rules. This paper aims to obtain some characteristics of axiomatizable classes. To do this, a monadic second-order frame language is presented. The relationship between ₀-axiomatizability and second-order definability is explored. Then a notion of an admissible set is introduced. Based on this notion, we show that any preferential model, which does not contain any four-node substructure, must be a reduct of some injective model. Furthermore, we furnish a necessary and sufficient condition for the axiomatizability of classes of injective preferential models using general rules. Finally, we show that, in some sense, the class of all posets without any four-node substructure is the largest among axiomatizable classes.     

Eigenvalue of fourth-order -point boundary value problem with derivatives

This paper deals with the existence of positive solutions for the fourth-order nonlinear ordinary differential equation

subject to the boundary conditions:

where ,β,γ,δ≥0 are constants such that ρ=δ+γ+βδ>0, and . By means of a fixed-point theorem due to Krasnaselskii, some new existence results of positive solutions for the above multi-point boundary value problem are obtained, which improve the main results of Graef et al. [J.R. Graef, C. Qian, B. Yang, A three-point boundary value problem for nonlinear fourth-order differential equations, J. Math. Anal. Appl. 287 (2003) 217–233]. An example is given to demonstrate the main results of this paper.     

Stability for first order delay dynamic equations on time scales

In this paper, we establish some sufficient conditions for the uniform stability and the uniformly asymptotical stability of the first order delay dynamic equation

where is a time scale, p(.) is rd-continuous and positive, the delay function . Our results unify the corresponding ones for differential and difference equations. To the best of our knowledge, this is the first time to discuss the asymptotical behavior of delay dynamic equations on time scales.