
Rob Gerth; Doron Peled; Moshe Y. Vardi; R. Gerth; Den Dolech Eindhoven; D. Peled; M. Y. Vardi; Pierre Wolper
We present a tableaubased algorithm for obtaining an automaton from a temporal logic formula. The algorithm is geared towards being used in model checking in an "onthefly" fashion, that is the automaton can be constructed simultaneously with, and guided by, the generation of the model. In particular, it is possible to detect that a property does not hold by only constructing part of the model and of the automaton. The algorithm can also be used to check the validity of a temporal logic assertion. Although the general problem is PSPACEcomplete, experiments show that our algorithm performs quite well on the...

S.O. Orero; M.R. Irving; Mr. S. O. Orero; Dr. M. R. Irving
. This paper presents a genetic algorithm based approach to the scheduling of generators in a Power System. All the usual unit commitment constraints including ramp rates are considered. An enhanced genetic algorithm incorporating a sequential decomposition logic is used to provide a faster search mechanism. The main advantage of the genetic algorithm formulation is that fairly accurate results can be obtained with a very simple algorithm. The algorithm has been tested on a power system with 26 generators. 1 INTRODUCTION The principal objective of the unit commitment of thermal generators in a power system is to schedule the generating...

Kelly Austin; I. Kelly; J. Austin
This paper describes a hardware to support distributed associative memories, in particular the ADAM neural network architecture. The system is designed to support a large number of moderately sized ADAM memories on a distributed memory MIMD architecture. The system addresses the issues of weight paging to allow neural networks of very large size to be executed using only a relatively small physical memory. The hardware also supports dedicated peripheral logic to accelerate the most compute intensive aspects of the ADAM memory. The paper describes the benefits gained by implementing the ADAM in hardware and presents a discussion of its design...

Norman Y. Foo
Gardenfors [3] proposed convexity as a nonlogical criterion for predicates that are amenable to induction. Some wellknown paradoxes appear to be resolvable using this criterion. In this paper we show that the convexity criterion subsumes classical mathematical induction if a transitivity assumption is made. This provides independent evidence for the viability of the criterion since classical induction is clearly successful in formal domains. 1. Introduction In artificial intelligence (AI) the problem of induction is a central one. Machine learning (e.g. [10]), logic programming (e.g. [1]), and a host of similar activities (e.g. [6]) in AI rely on notions of induction...

P.D. Bruza; T.P. van der Weide
: In this paper we introduce Index Expressions as a means for modelling document content. From an index expression the the Power Index Expression can be derived, which is a powerful instrument for information retrieval. We describe the characterization of documents in the style of formal logic. The content of a document is then modelled by a set of axioms, of which the document is a model. Relating a document to a query is done by proving the query from the axioms of that document. We introduce three rules of inference. If such a proof is not possible, the relevance...

Peter J. Mccann; Peter J. Mccann; Gruiacatalin Roman; Gruiacatalin Roman
With recent advances in wireless communication technology, mobile computing is an increasingly important area of research. A mobile system is one where independently executing components may migrate through some space during the course of the computation, and where the pattern of connectivity among the components changes as they move in and out of proximity. Mobile UNITY is a language and logic for specifying and reasoning about mobile systems, the components of which must operate in a highly decoupled way. In this paper it is argued that Mobile UNITY contributes to the modular development of system specifications precisely because of the...

Gert Smolka
We present a calculus providing an abstract operational semantics for higherorder concurrent constraint programming. The calculus is parameterized with a firstorder constraint system and provides firstclass abstraction, guarded disjunction, committedchoice, deep guards, dynamic creation of unique names, and constraint communication. The calculus comes with a declarative sublanguage for which computation amounts to equivalence transformation of formulas. The declarative sublanguage can express negation. Abstractions are referred to by names, which are firstclass values. This way we obtain a smooth and straightforward combination of firstorder constraints with higherorder programming. Constraint communication is asynchronous and exploits the presence of logic variables. It provides...

Xianchang Wang; Jiahuai You; Li Yan Yuan
This paper studies the semantics for the class of all defeasible (inheritance) networks, including cyclic and inconsistent networks using a transformation approach. First we show that defeasible networks can be translated, tractably, to default theories while preserving Horty's pathoff credulous semantics for all consistent networks. Using the existing methods in dealing with the semantics of default logic, we are able to provide a tractable skeptical semantics, the wellfounded semantics, and a new credulous semantics, the regular semantics, both of which are defined for any defeasible network. Furthermore, we show that these semantics are based on the same principle of specificity...

Yeung Yam; Masao Mukaidono; Vladik Kreinovich
In many practical applications of fuzzy methodology, it is desirable to go beyond the interval [0; 1] and to consider more general fuzzy values: e.g., intervals, or real numbers outside the interval [0; 1]. When we increase the set of possible fuzzy values, we thus increase the number of bits necessary to store each degree, and therefore, increase the computation time which is needed to process these degrees. Since in many applications, it is crucial to get the result on time, it is therefore desirable to make the smallest possible increase. In this paper, we describe such smallest possible increases....

Allen Van Gelder; Kenneth A. Ross; John S. Schlipf
A general logic program (abbreviated to "program" hereafter) is a set of rules that have both positive and negative subgoals. It is common to view a deductive database as a general logic program consisting of rules (IDB) sitting above elementary relations (EDB, facts). It is desirable to associate one Herbrand model with a program and think of that model as the "meaning of the program," or its "declarative semantics." Ideally, queries directed to the program would be answered in accordance with this model. Recent research indicates that some programs do not have a "satisfactory" total model; for such programs, the...

Hassan AïtKaci; Hassan Aitkaci; Andreas Podelski
LIFE uses matching on ordersorted feature structures for passing arguments to functions. As opposed to unification which amounts to normalizing a conjunction of constraints, solving a matching problem consists of deciding whether a constraint (guard) or its negation are entailed by the context. We give a complete and consistent set of rules for entailment and disentailment of ordersorted feature constraints. These rules are directly usable for relative simplification, a general prooftheoretic method for proving guards in concurrent constraint logic languages using guarded rules. 1 Introduction LIFE [5, 4] extends the computational paradigm of Logic Programming in two essential ways: ffl...

Zhanping Chen; Student Member; Kaushik Roy; Senior Member; TanLi Chou
Power dissipation in CMOS circuits is heavily dependent on the signal properties of the primary inputs. Due to uncertainties in specification of such properties, the average power should be specified between a maximum and a minimum possible value. Due to the complex nature of the problem, it is practically impossible to use traditional power estimation techniques to determine such bounds. In this paper, we present a novel approach to accurately estimate the maximum and minimum bounds for average power using a technique which calculates the sensitivities of average power dissipation to uncertainties in specification of primary input signal properties. The...

Paola Bruscoli; Francesca Levi; Giorgio Levi; Maria Chiara Meo
In this paper we define a new compilative version of constructive negation (intensional negation) in CLP and we prove its (nonground) correctness and completeness wrt the 3valued completion. We show that intensional negation is essentially equivalent to constructive negation and that it is indeed more efficient, as one would expect from the fact that it is a compilative technique, with the transformation and the associated normalization process being performed once and for all on the source program. We define several formal nonground semantics, based either on the derivation rule or on the least fixpoint of an immediate consequence operator. All...

Christopher T. Haynes; Richard M. Salter
In the presence of firstclass continuations, shallow maintenance of dynamic bindings requires more than the traditional stackbased techniques. This paper provides correctness criteria for such dynamic environments, along with contrasting implementations. A store semantics provides the framework for our correctness criteria and presentation of deep and shallowbinding implementations. The latter implementation is a new statespace algorithm, which is proved correct. A variation of the algorithm implements Scheme's dynamicwind operation. Finally, a technique for maintaining dynamic state called semishallow binding is presented. This compromise between deep and shallowbinding appears suitable for parallel systems. Applications include fluid binding of lexical variables and...

Scott Richard Oksanen; David Chenho Kung; Jyhjong Lin
: A technique is presented for verifying realtime system specifications. A visual conceptual modeling language called ECM is used as a realtime specification language. Specifications are translated into augmented Petri nets with timing and temporal logic constraints. A reachability tree of legal system states is generated from the timing constraints in the Petri net. Past temporal logic constraints are verified using the reachability tree as a record of past states. Future temporal logic constraints are verified dynamically during construction of the reachability tree. 1 Introduction As the size and complexity of software systems grows, so does the potential for errors....

Steve Reeves; Steve Reeves; Steve Reeves
In this paper we propose the design of a tool that will allow the construction of a formal, textual description of a software system even if it has a graphical userinterface as a component. An important aspect of this design is that it can be used for two purposesthe teaching of predicate calculus and the formal specification of graphical userinterfaces. The design has been suggested by considering a system that has already been very successful for teaching predicate logic, namely Tarski's World. 1. Introduction There are now many, welldocumented uses of formal specification in the program development processDiller, 1994; Dromey,...

Giorgio Levi; Davide Ramundo
The paper formally shows that the Ssemantics is adequate for reasoning about the soundness and completeness of real Prolog metainterpreters, based on the nonground representation of objectlevel variables. The paper extends some recent results by De Schreye and Martens, by proving the "equivalence" between the object program and its version metainterpreted by vanilla for any positive logic program. The same construction is applied to obtain a soundness and completeness result for an enhanced metainterpreter defining various inheritance mechanisms on structured logic programs. We then consider the specialization of metainterpreters by means of partial deduction techniques, both in the case of...

Dmitry Y. Zinoviev; Yury A. Polyakov
An integrated multipurpose setup for the automated testing of superconductor devices and circuits has been designed, implemented, and installed in the RSFQ Laboratory of the State University of New York at Stony Brook. The extendable and modular design of the setup allows a wide variety of lowfrequency superconductor experiments to be carried out including those that require immediate interaction between the setup and the researcher. I. Motivation The recent rapid progress in the field of superconductor electronics, particularly of Rapid Single Flux Quantum (RSFQ) logic and memory devices [1], has required adequate testing equipment that would flexibly accommodate the needs...

Peter Buneman; Leonid Libkin; Dan Suciu; Val Tannen; Limsoon Wong
. The syntax of comprehensions is very close to the syntax of a number of practical database query languages and is, we believe, a better starting point than firstorder logic for the development of database languages. We give an informal account of a language based on comprehension syntax that deals uniformly with a variety of collection types; it also includes pattern matching, variant types and function definition. We show, again informally, how comprehension syntax is a natural fragment of structural recursion, a much more powerful programming paradigm for collection types. We also show that a very small "abstract syntax language"...

B. M. Lawal; D. R. Gilbert; A. A. Letichevsky
This paper describes the design of a web based scheduler program and its implementation in the constraint logic programming language clp(FD). We give a formal description of this implementation using the interaction semantics of action languages recently developed by the authors. The clp code employs a port of the PiLLoW library and was compiled via C to executable code (using technology based on wamcc for Prolog) to be run as a CGI script. The implementation is based on the course modules description currently being used in the School of Informatics at City University. It integrates constraints concerning module pre and...