A theory of nonmonotonic rule systems II

Conclusions We have proved a number of results on nonmonotonic rule systems. This theory allows us to capture many constructions appearing in the current literature on the logical foundations of artificial intelligence.Our results provide additional tools tying these constructs with traditional methods of logic and recursion theory.In a sequel we shall deal with rule systems containing variables in the rules and with predicate logics. We shall prove results related to the properties of recursive systems that are not necessarily highly recursive. We shall also explore connections with.Work partially supported by NSF grant RII-86-10671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-89-02797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grants DMS-87-02473 and DMS-90-06413.     

An array language for data parallelism: Definition,compilation, and applications

The programming of SIMD machines that strongly support data parallelism, such as the Connection Machine, ¹ presents new challenges for language, compiler, and algorithm designers. We propose an array language that captures many of the abstractions that are necessary for the effective programming of such machines, thereby liberating the user from having to specify low-level details. Consequently, this new language, ALP, allows for efficient compilation using state-of-the-art techniques, achieving hand-code quality. We demonstrate the effectiveness of our approach by two examples which show that despite being an array language, ALP does not restrict expressiveness to rigidly regular computational structures.Work supported in part by ONR grant number N00014-89-J-1906 while on sabbatical leave at the Department of Computer Science, Yale University.Work supported in part by NSF grant number DCR-8405478 while on sabbatical leave at the Department of Computer Science, Yale University.     

Scheduling Techniques for Media-on-Demand

Broadcasting popular media to clients is the ultimate scalable solution for media-on-demand. Recently, it was shown that if clients can receive data at a rate faster than what they need for playback and if they can store later parts of the media in their buffers, then much higher scalability may be obtained. This paper addresses scheduling problems arising from these new systems for media-on-demand. For given amount of bandwidth, we reduce the maximal start-up delay time for an uninterrupted playback. We achieve our results by introducing two techniques. In the first, the media is arranged on the channels such that clients gain from buffering later parts of the transmission before the actual start of the playback. In the second, segments of different media may be mixed together on the same channel. We introduce a simple class of recursive round-robin scheduling algorithms that implement both techniques. Our results improve the best known asymptotic results. Moreover, our scheduling algorithms outperform known results for practical values for number of media and number of broadcasting channels. For some specific small values, we present solutions that are better than those achieved by our algorithms. Finally, we show that our techniques are useful for models in which clients may not receive data from all the channels, and are applicable to media with different lengths and popularities. A preliminary version appeared in the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 791–800, 2003. Work of R.E. Ladner was partially supported by NSF grant No. CCR-0098012. Work of T. Tamir done while the author was at the University of Washington.     

On the Lavrentiev phenomenon

Additional assumptions, besides convexity and coercivity, are investigated to guarantee that the Lavrentiev phenomenon does not occur in a basic problem of the calculus of variations. Dedicated to Professor S. Faedo on his 70th birthday Work partially supported by the National Science Foundation under grant MCS-82-02-033.     

Automatic symbolic compositional verification by learning assumptions

Compositional reasoning aims to improve scalability of verification tools by reducing the original verification task into subproblems. The simplification is typically based on assume-guarantee reasoning principles, and requires user guidance to identify appropriate assumptions for components. In this paper, we propose a fully automated approach to compositional reasoning that consists of automated decomposition using a hypergraph partitioning algorithm for balanced clustering of variables, and discovering assumptions using the L ^* algorithm for active learning of regular languages. We present a symbolic implementation of the learning algorithm, and incorporate it in the model checker NuSmv. In some cases, our experiments demonstrate significant savings in the computational requirements of symbolic model checking. This research was partially supported by ARO grant DAAD19-01-1-0473, and NSF grants ITR/SY 0121431 and CCR0306382.     

Autoepistemic logic of first order and its expressive power

We study the expressive power of first-order autoepistemic logic. We argue that full introspection of rational agents should be carried out by minimizing positive introspection and maximizing negative introspection. Based on full introspection, we propose the maximal well-founded semantics that characterizes autoepistemic reasoning processes of rational agents, and show that breadth of the semantics covers all theories in autoepistemic logic of first order, Moore's AE logic, and Reiter's default logic. Our study demonstrates that the autoepistemic logic of first order is a very powerful framework for nonmonotonic reasoning, logic programming, deductive databases, and knowledge representation.This research is partially supported by NSERC grant OGP42193.     

Spatial persistence

We examine the spatial version of the persistence problem. In temporal reasoning, this is the problem of determining whether or not the validity of a fact at some point in time persists until another point in time, given that certain events or processes may happen in between. We show that its analog does intuitively exist in spatial reasoning, and review under the aspect of transferability to space different approaches for achieving persistence in temporal reasoning. Finally, we present reasoning with generalized spatial Allen relations as an instance of reasoning under the assumption of spatial persistence.This author has partially been supported under grant numbers A18/XXXXX/62090/3414014 and A18/XXXXX/62090/F3414025 by the University of Auckland Research Fund.     

A logic for reasoning with inconsistency

Most known computational approaches to reasoning have problems when facing inconsistency, so they assume that a given logical system is consistent. Unfortunately, the latter is difficult to verify and very often is not true. It may happen that addition of data to a large system makes it inconsistent, and hence destroys the vast amount of meaningful information. We present a logic, called APC (annotated predicate calculus; cf. annotated logic programs of [4, 5]), that treats any set of clauses, either consistent or not, in a uniform way. In this logic, consequences of a contradiction are not nearly as damaging as in the standard predicate calculus, and meaningful information can still be extracted from an inconsistent set of formulae. APC has a resolution-based sound and complete proof procedure. We also introduce a novel notion of epistemic entailment and show its importance for investigating inconsistency in predicate calculus as well as its application to nonmonotonic reasoning. Most importantly, our claim that a logical theory is an adequate model of human perception of inconsistency, is actually backed by rigorous arguments.A preliminary report on this research appeared in LICS'89.Work of M. Kifer was supported in part by the NSF grants DCR-8603676, IRI-8903507.Work of E. L. Lozinskii was supported in part by Israel National Council for Research and Development under the grants 2454-3-87, 2545-2-87, 2545-3-89 and by Israel Academy of Science, grant 224-88.     

A new efficient spectral galerkin method for singular perturbation problems

A new spectral Galerkin method is proposed for the convection-dominated convection-diffusion equation. This method employs a new class of trail function spaces. The available error bounds provide a clear theoretical interpretation for the higher accuracy of the new method compared to the conventional spectral methods when applied to problems with thin boundary layers. Efficient solution techniques are developed for the convection-diffusion equations by using appropriate basis functions for the new trial function spaces. The higher accuracy and the effectiveness of the new method for problems with thin boundary layers are confirmed by our numerical experiments.The work of this author is partially supported by NSF grant DMS-9205300.     

A theory of nonmonotonic rule systems I

We introduce here the study of generalnonmonotonic rule systems. These deal with situations where a conclusion is drawn from a system of beliefsS (and seen to be inS), basedboth on some premises being inS and on some restraints not being inS. In the monotone systems of traditional logic there are no restraints, conclusions are drawn solely based on premises being inS. Nonmonotonic rule systems capture the essential syntactic, semantic, and algorithmic features of many nonmonotone systems such as default logic, negation as failure, truth maintenance, autoepistemic logic, and also important combinatorial questions from mathematics such as the marriage problem. This reveals semantics and syntax and proof procedures and algorithms for computing belief sets in many cases where none were previously available and entirely uniformly. In particular, we introduce and study deductively closed sets, extensions and weak extensions. Semantics of nonmonotonic rule systems is studied in part II of this paper and extensions to predicate classical, intuitionistic, and modal logics are left to a later paper.Work partially supported by NSF grant RII-8610671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-8902797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grant DMS-8702473.     

A data structure for arc insertion and regular path finding

Let be the language defined by some deterministick-state automaton with accepting statesF, and letG be a directed graph withn nodes andm labeled arcs. Thedynamic -path problem is to process efficiently and on-line two kinds of operations: (1) inserting arcs intoG, and (2) given two nodesu andv inG, finding a path fromu tov that is labeled by some word of , or reporting that none exists. We present a data structure that supports insertion and regular path existence queries inO(nk ²) amortized time andO(|F|) worst-case time, respectively. Deletions only (no insertions) can also be accommodated in directed acyclic graphs. Finding an -path between two nodes can be done inO(l+|F|) worst-case time, wherel is the length of the path returned. This is an improvement over theO(m) time required to answer queries in the static version of this problem, for each fixed infinite . We show how this data structure and the techniques used for building it are applicable to the area of knowledge base querying. In an amortized setting, we provide relative improvements ofO(m/n) to the time bounds for answering many one-sided recursive queries and even some two-sided recursive queries, such as the same generation query on acyclic graphs.An extended abstract of this paper was presented at the first annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1990.Work partially completed while at Brown University. Work at Princeton partially supported by the NSF Center in Discrete Mathematics and Theoretical Computer Science (DIMACS).Work supported in part by NSF grant IRI-8617344, by an Alfred P. Sloan Foundation Fellowship, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.Work supported in part by an NSF Presidential Young Investigator Award with matching funds from IBM, by NSF research grant DCR-8403613, and by ONR grant N00014-83-K-0146, ARPA Order No. 4786.     

Middle-out reasoning for synthesis and induction

We develop two applications of middle-out reasoning in inductive proofs: logic program synthesis and the selection of induction schemes. Middle-out reasoning as part of proof planning was first suggested by Bundy et al. Middle-out reasoning uses variables to represent unknown terms and formulae. Unification instantiates the variables in the subsequent planning, while proof planning provides the necessary search control. Middle-out reasoning is used for synthesis by planning the verification of an unknown logic program: The program body is represented with a meta-variable. The planning results both in an instantiation of the program body and a plan for the verification of that program. If the plan executes successfully, the synthesized program is partially correct and complete. Middle-out reasoning is also used to select induction schemes. Finding an appropriate induction scheme during synthesis is difficult because the recursion of the program, which is unknown at the outset, determines the induction in the proof. In middle-out induction, we set up a schematic step case by representing the constructors that are applied to induction variables with meta-variables. Once the step case is complete, the instantiated variables correspond to an induction appropriate to the recursion of the program. We have implemented these techniques as an extension of the proof planning system CL ^A M, called Periwinkle, and synthesized a variaety of programs fully automatically. Supported by the Swiss National Science Foundation and ARC Project BC/DAAD Grant 438. The work described in this paper was carried out while the first author was at the Department of Artificial Intelligence of the University of Edinburgh. Supported by the German Ministry for Research and Technology (BMFT) under grant ITS 9102 and ARC Project BC/DAAD Grant 438. Responsibility for the contents of this publication lies with the authors. Supported by SERC grant GR/J/80702, ESPRIT BRP grant 6810, ESPRIT BRP grant EC-US 019-76094, and ARC Project BC/DAAD Grant 438.     

Algorithms for bichromatic line-segment problems and polyhedral terrains

We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.Work on this paper by the first author has been supported in part by the National Science Foundation under Grant CCR-9002352. Work by the second author was supported in part by the National Science Foundation under Grant CCR-8714565. The fourth author has been supported in part by the Office of Naval Research under Grant N0014-87-K-0129, by the National Science Foundation under Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a grant from the US-Israeli Binational Science Foundation.     

Adaptive decentralized control under non-uniqueness of the optimal control

We study the problem of decentralization of flow control in packet-switching networks under the isarithmic scheme. An incoming packet enters the network only if there are permits available at the entry port when it arrives. The actions of the controllers refer to the routing of permits in the network and the control variables are the corresponding probabilities. We study the behavior of adaptive algorithms implemented at the controllers to update these probabilities and seek optimal performance. This problem can be stated as a routing problem in a closed queueing network. The centralized version of a learning automation is a general framework presented along with the proof of asymptotic optimality. Decentralization of the controller gives rise to non-uniqueness of the optimal control parameters. Non-uniqueness can be exploited to construct asymptotically optimal learning algorithms that exhibit different behavior. We implement two different algorithms for the parallel operation and discuss their differences. Convergence is established using the weak convergence methodology. In addition to our theoretical results, we illustrate the main results using the flow control problem as a model example and verify the predicted behavior of the two proposed algorithms through computer simulations, including an example of tracking.The work of this author was partially supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Government of Canada, and partially supported by NSERC grant WFA 0139015 and FCAR-Québec grant 95-NC-1375.The work of this author was supported by a grant from the CITR under the NCE program of the Government of Canada.     

Using counterfactuals in knowledge-based programming

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi [3,4]. The use of counterfactuals is illustrated by designing a protocol in which an agent stops sending messages once it knows that it is safe to do so. Such behavior is difficult to capture in the original framework because it involves reasoning about counterfactual executions, including ones that are not consistent with the protocol. Attempts to formalize these notions without counterfactuals are shown to lead to rather counterintuitive behavior.Received: 15 November 2001, Accepted: 15 April 2004, Published online: 13 July 2004Joseph Y. Halpern: Work supported in part by NSF under grant IRI-96-25901, IIS-0090145, and CTC-0208535, by the Air Force Office of Scientific Research under grant F49620-96-1-0323 and F48620-02-1-0101, and by ONR under grants N00014-00-1-03-41, N00014-01-1-0795, and by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grant N00014-01-1-0795.)A preliminary version of this paper appeared in the Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1998.     

Tight bounds for shared memory systems accessed by Byzantine processes

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al. [21]. We show that sticky bits are universal in the Byzantine failure model for n ≥ 3t + 1, an improvement over the previous result requiring n ≥ (2t + 1)(t + 1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ≥ 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects. Research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This work was partially completed while at AT&T Labs and while visiting the Institute for Advanced Study, Princeton, NJ. Research supported in part by US-Israel Binational Science Foundation Grant 2002246. This work was partially completed while visiting AT&T Labs. This work was partially completed while at AT&T Labs. Research supported in part by the National Science Foundation under Grant No. CCR-0331584. A preliminary version of the results presented in this paper appeared in [23].     

Automatic Construction and Verification of Isotopy Invariants

We extend our previous study of the automatic construction of isomorphic classification theorems for algebraic domains by considering the isotopy equivalence relation. Isotopism is an important generalisation of isomorphism, and is studied by mathematicians in domains such as loop theory. This extension was not straightforward, and we had to solve two major technical problems, namely, generating and verifying isotopy invariants. Concentrating on the domain of loop theory, we have developed three novel techniques for generating isotopic invariants, by using the notion of universal identities and by using constructions based on subblocks. In addition, given the complexity of the theorems that verify that a conjunction of the invariants form an isotopy class, we have developed ways of simplifying the problem of proving these theorems. Our techniques employ an interplay of computer algebra, model generation, theorem proving, and satisfiability-solving methods. To demonstrate the power of the approach, we generate isotopic classification theorems for loops of size 6 and 7, which extend the previously known enumeration results. This work was previously beyond the capabilities of automated reasoning techniques. The author’s work was supported by EPSRC MathFIT grant GR/S31099.     

A New Quantum Lower Bound Method,with Applications to Direct Product Theorems and Time-Space Tradeoffs

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal. A. Ambainis supported by University of Latvia research project Y2-ZP01-100. This work conducted while at University of Waterloo, supported by NSERC, ARO, MITACS, CIFAR, CFI and IQC University Professorship. R. Špalek supported by NSF Grant CCF-0524837 and ARO Grant DAAD 19-03-1-0082. Work conducted while at CWI and the University of Amsterdam, supported by the European Commission under projects RESQ (IST-2001-37559) and QAP (IST-015848). R. de Wolf supported by a Veni grant from the Netherlands Organization for Scientific Research (NWO) and partially supported by the EU projects RESQ and QAP.     

A Logical Characterization of Forward and Backward Chaining in the Inverse Method

The inverse method is a generalization of resolution that can be applied to non-classical logics. We have recently shown how Andreoli’s focusing strategy can be adapted for the inverse method in linear logic. In this paper we introduce the notion of focusing bias for atoms and show that it gives rise to forward and backward chaining, generalizing both hyperresolution (forward) and SLD resolution (backward) on the Horn fragment. A key feature of our characterization is the structural, rather than purely operational, explanation for forward and backward chaining. A search procedure like the inverse method is thus able to perform both operations as appropriate, even simultaneously. We also present experimental results and an evaluation of the practical benefits of biased atoms for a number of examples from different problem domains. This work has been partially supported by the Office of Naval Research (ONR) under grant MURI N00014-04-1-0724 and by the National Science Foundation (NSF) under grant CCR-0306313. The first author was partially supported by a post-doctoral fellowship from INRIA-Futurs/école Polytechnique.