For programs whose data variables range over Boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this article, we consider algorithmic verification of programs that use Boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over an unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) Pspace-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly nested loops. The second result establishes connections to automata and logics defining languages over data words.

Path constraints are capable of expressing inclusion and inverse relationships and have proved useful in modeling and querying semistructured data [Abiteboul and Vianu 1999; Buneman et al. 2000]. Types also constrain the structure of data and are commonly found in traditional databases. There has also been work on imposing structure or a type system on semistructured data for storing and querying semistructured data in a traditional database system [Alon et al. 2001; Deutsch et al. 1999a; Florescu and Kossmann 1999; Shanmugasundaram et al. 1999]. One wants to know whether complexity results for reasoning about path constraints established in the untyped (semistructured) context could carry over to traditional databases, and vice versa. It is therefore appropriate to understand the interaction between types and path constraints. In addition, XML [Bray et al. 1998], which may involve both an optional schema (e.g., DTDs or XML Schema [Thompson et al. 2001]) and integrity constraints, highlights the importance of the study of the interaction.This article investigates that interaction. In particular it studies constraint implication problems, which are important both in understanding the semantics of type/constraint systems and in query optimization. It shows that path constraints interact with types in a highly intricate way. For that purpose a number of results on path constraint implication are established in the presence and absence of type systems. These results demonstrate that adding a type system may in some cases simplify reasoning about path constraints and in other cases make it harder. For example, it is shown that there is a path constraint implication problem that is decidable in PTIME in the untyped context, but that becomes undecidable when a type system is added. On the other hand, there is an implication problem that is undecidable in the untyped context, but becomes not only decidable in cubic time but also finitely axiomatizable when a type system is imposed.

We establish that the decidability of the first order theory of a class of finite structures C is a simple and useful condition for guaranteeing that the expressive power of FO+LFP properly extends that of FO on C, unifying separation results for various classes of structures that have been studied. We then apply this result to show that it encompasses certain constructive pebble game techniques which are widely used to establish separations between FO and FO+LFP, and demonstrate that these same techniques cannot succeed in performing separations from any complexity class that contains DLOGTIME.

XML [7], which is emerging as an important standard for data exchange on the World-Wide Web, highlights the importance of semistructured data. Although the XML standard itself does not require any schema or type system, a number of proposals [6, 17, 19] have been developed that roughly correspond to data definition languages. These allow one to constrain the structure of XML data by imposing a schema on it. These and other proposals also advocate the need for integrity constraints, another form of constraints that should, for example, be capable of expressing inclusion constraints and inverse relationships. The latter have recently been studied as path constraints in the context of semistructured data [4, 9]. It is likely that future XML proposals will involve both forms of constraints, and it is therefore appropriate to understand the interaction between them. This paper investigates that interaction. In particular it studies constraint implication problems, which are important both in understanding the semantics of type/constraint systems and in query optimization. A number of results on path constraint implication are established in the presence and absence of type systems. These results demonstrate that adding a type system may in some cases simplify reasoning about path constraints and in other cases make it harder. For example, it is shown that there is a path constraint implication problem that is decidable in PTIME in the untyped context, but that becomes undecidable when a type system is added. On the other hand, there is an implication problem that is undecidable in the untyped context, but becomes not only decidable in cubic time but also finitely axiomatizable when a type system is imposed.

We present a class of path constraints of interest in connection with both structured and semi-structured databases, and investigate their associated implication problems. These path constraints are capable of expressing natural integrity constraints that are not only a fundamental part of the semantics of the data, but are also important in query optimization. We show that in semistructured databases, despite the simple syntax of the constraints, their associated implication problem is r.e. complete and finite implication problem is co-r.e. complete. However, we establish the decidability of the implication problems for several fragments of the path constraint language, and demonstrate that these fragments suffice to express important semantic information such as inverse relationships and local database constraints commonly found in object-oriented databases. We also show that in the presence of types, the analysis of path constraint implication becomes more delicate. We demonstrate so...

The extensions of first-order logic with a least fixed point operator (FO + LFP) and with a partial fixed point operator (FO + PFP) are known to capture the complexity classes P and PSPACE respectively in the presence of an ordering relation over finite structures. Recently, Abiteboul and Vianu (in "Proceedings of the 23rd ACM Symposium on the Theory of Computing," 1991) investigated the relationship of these two logics in the absence of an ordering, using a machine model of generic computation. In particular, they showed that the two languages have equivalent expressive power if and only if P = PSPACE. These languages can also be seen as fragments of an infinitary logic where each formula has a bounded number of variables, Lω∞ω, (see, for instance, Kolaitis and Vardi, in "Proceedings of the 5th IEEE Symposium on Logic in Computer Science," pp. 156-167, 1990). We investigate this logic on finite structures and provide a normal form for it. We also present a treatment of Abiteboul and Vianu′s results from this point of view. In particular, we show that we can write a formula of FO + LFP that defines an ordering of the Lk∞ω, types uniformly over all finite structures. One consequence of this is a generalization of the equivalence of FO + LFP and P from ordered structures to classes of structures where every element is definable. We also settle a conjecture mentioned by Abiteboul and Vianu by showing that FO + LFP is properly contained in the polynomial time computable fragment of Lω∞ω, raising the question of whether the latter fragment is a recursively enumerable class.

Abstract A paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.

The price is failure on a class of inductive inference problems that are easily solved, in contrast, by nonBayesian mechanical learners. By “mechanical” is meant “simulable by Turing machine”. One of the central tenets of Bayesianism, which is common to the heterogeneous collection of views which fall under this rubric, is that hypothesis change proceeds via conditionalization on accumulated evidence, the posterior probability of a given hypothesis on the evidence being computed using Bayes's theorem. We show that this strategy for hypothesis change precludes the solution of certain problems of inductive inference by mechanical means—problems which are solvable by mechanical means when the restriction to this Bayesian strategy is lifted. Our discussion proceeds as follows. After some technical preliminaries, the concept of (formal) learner is introduced along with a criterion of inferential success. Next we specify a class of inductive inference problems, and then define the notion of “Bayesian behavior” on those problems. Finally, we exhibit an inductive inference problem from the specified class such that (a) some nonmechanical Bayesian learner solves the problem, (b) some nonBayesian mechanical learner solves the problem, (c) some mechanical learner manifests Bayesian behavior on the problem, but (d) no mechanical Bayesian learner solves the problem. Insofar as possible terminology and notation are drawn from Osherson, Stob, and Weinstein [1986].

Linguistic theories typically assign various linguistic phenomena to one of the categories, syntactic, semantic, or pragmatic, as if the phenomena in each category were relatively independent of those in the others. However, various phenomena in discourse do not seem to yield comfortably to any account that is strictly a syntactic or semantic or pragmatic one. This paper focuses on particular phenomena of this sort-the use of various referring expressions such as definite noun phrases and pronouns-and examines their interaction with mechanisms used to maintain discourse coherence.