Decomposition and Technology Mapping of Speed-Independent Circuits Using Boolean Relations
- Jordi Cortadella; Michael Kishinevsky; Alex Kondratyev; Luciano Lavagno; Enric Pastor
This paper presents a new technique for decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G available in the library and two gates H 1 and H 2 simpler than F , while preserving the original behavior and speedindependence of the circuit. To extract functions for H 1 and H 2 the method uses Boolean relations as opposed...
An Environment for the Creation of Intelligent Network Services
- Bernhard Steffen; Tiziana Margaria; Volker Braun; Andreas Claßen; Manfred Reitenspieß
This paper presents a Service Creation Environment which is unique in offering global correctness and consistency checks. These guarantee frame conditions for the design concerning implementability, country specific standards and network specific features. Frame conditions are formulated in a modal logic and verified via model checking. The described environment offers a lazy and incremental use of formal methods: if no formal constraints are defined, the system behaves like standard systems for service creation. However, the more constraints are added, the more reliable are the created services. This provides a `soft' entry into the world of formal methods.
Design, Implementation, and Evaluation of the Constraint Language cc(FD)
- Pascal Van Hentenryck; Vijay Saraswat; Yves Deville
This paper describes the design, implementation, and applications of the constraint logic language cc(FD). cc(FD) is a declarative nondeterministic constraint logic language over finite domains based on the cc framework , an extension of the CLP scheme . Its constraint solver includes (non-linear) arithmetic constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc(FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new constraint operations such as constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility...
DistAl: An Inter-pattern Distance-based Constructive Learning Algorithm
- Jihoon Yang; Rajesh Parekh; Vasant Honavar
Multi-layer networks of threshold logic units offer an attractive framework for the design of pattern classification systems. A new constructive neural network learning algorithm (DistAl) based on inter-pattern distance is introduced. DistAl constructs a single hidden layer of hyperspherical threshold neurons. Each neuron is designed to exclude a cluster of training patterns belonging to the same class. The weights and thresholds of the hidden neurons are determined directly by comparing the interpattern distances of the training patterns. This offers a significant advantage over other constructive learning algorithms that use an iterative (and often time consuming) weight modification strategy to train...
Integrating Tools for High-Level Programming of Robot Manipulation Tasks
- Giuseppe Beccari; Stefano Caselli; Francesco Zanichelli
This paper discusses the CARA programming environment for robot manipulators. The environment is realized as the integration of a full-fledged logic system with a real-time robotic machine. While the development of a general robot programming environment is an elusive goal, flexible development and incremental refinement are made possible by the open nature of the CARA environment. 1 Introduction At the University of Parma (Laboratory for Robotics and Intelligent Manufacturing) in the frame of the National Program on Robotics of the CNR, we have developed a robot programming environment based on an extended logic programming paradigm. This research has been carried...
Putting Hardware-Software Codesign into Practice
- G. Schrott; T. Tempelmeier
This contribution reports on an approach to hardware/software codesign based on a state transition system design language MAD. MAD has been used for software design for some time, but is now being extended to hardware design by adding the hardware description language VHDL as one of its target languages. The experience of adding a new dimension (i.e. hardware) to the design space and of dealing with some state-of-the-art hardware development methods and tools is presented. The approach is illustrated with an implementation of a control system for an elevator. Key words: Hardware-software codesign, Real-time languages, Real-time systems, Embedded systems, Distributed...
Inductive Assertion Method For Logic Programs
- Wlodzimierz Drabent; Jan Maluszynski
Certain properties of logic programs are inexpressible in terms of their declarative semantics. One example of such properties would be the actual form of procedure calls and successes which occur during computations of a program. They are often used by programmers in their informal reasoning. In this paper, the inductive assertion method for proving partial correctness of logic programs is introduced and proved sound. The method makes it possible to formulate and prove properties which are inexpressible in terms of the declarative semantics. An execution mechanism using the Prolog computation rule and arbitrary search strategy (eg. OR-parallelism or Prolog backtracking)...
Programming in Timed Concurrent Constraint Languages
- V. A. Saraswat; R. Jagadeesan; V. Gupta
This paper explores the expressive power of the tcc paradigm. The origin of the work in the integration of synchronous and constraint programming is described. The basic conceptual and mathematical framework --- developed in the spirit of the model-based approach characteristic of theoretical computer science --- is reviewed. We show that a range of constructs for expressing timeouts, preemption and other complicated patterns of temporal activity are expressible in the basic model and language-framework. Indeed, we present a single construct on processes, definable in the language, that can simulate the effect of other preemption constructs. We present Timed Gentzen, a...
HYWIBAS: A Hybrid Knowledge Base System for Large, Shared Knowledge Bases
- U. Reimer; P. Lippuner; R. Marti; M. Norrie; H. -j. Schek; U. Badertscher M. Rys; U. Badertscher; M. Rys
this paper has three major objectives: ffl We exploit database technology to support efficient retrieval and update of large knowledge bases. To this end we map a frame representation model to an object data model. Since the object data model is implemented as a database system we obtain a databasesupported frame system. ffl In order to provide efficient retrieval and update services the object model is mapped to a relational storage system which makes use of massive data replication (to minimise retrieval costs) and parallelisation (to minimise update costs). ffl We integrate a frame representation system for representing terminological knowledge...
An Algorithmic Approach for Checking Closure Properties of omega-Regular Languages
- Doron Peled; Thomas Wilke; Pierre Wolper
. In concurrency theory, there are several examples where the interleaved model of concurrency can distinguish between execution sequences which are not significantly different. One such example is sequences that differ from each other by stuttering, i. e., the number of times a state can adjacently repeat. Another example is executions that differ only by the ordering of independently executed events. Considering these sequences as different is semantically rather meaningless. Nevertheless, specification languages that are based on interleaving semantics, such as linear temporal logic (LTL), can distinguish between them. This situation has led to several attempts to define languages that...
Observations on Observations in Action Theories
- James M. Crawford; David W. Etherington
A number of authors have noticed that observations of specific facts about specific states of the world cause problems for existing theories of nonmonotonic reasoning about action. We argue that these problems are pervasive in action theories, and more subtle than previously noticed. Furthermore, we note that the proposed solutions are fundamentally procedural: they involve treating observations in a separate reasoning step. These insights engender a number of open questions about the precise nature of observations in reasoning about action, and how they should be treated. Introduction The development of a formal logic for reasoning about change has proven to...
The Evolution Of Carnot's Principle
- E. T. Jaynes
: We trace the development of the technical ideas showing that the Second Law of Thermodynamics became, over a Century ago, a general principle of reasoning, applicable to scientific inference in other fields than thermodynamics. Both the logic and the procedure of our present maximum entropy applications are easily recognized in the methods for predicting equilibrium conditions introduced by Gibbs in 1875. Chemical thermodynamics has been based on them ever since. What is new in this field is not the method, but the recognition of its generality. 1. INTRODUCTION 2 2. CARNOT'S PRINCIPLE 3 3. FIRST METAMORPHOSIS: KELVIN 4 4....
RISC-CLP(Tree(Delta)) - A Constraint Logic Programming System with Parametric Domain
- Hoon Hong; Stefan Ratschan
Current implementations of constraint logic programming languages (like CLP(!), CHIP or RISC-CLP(Real) support constraint solving over a certain fixed domain. In this paper a system is presented which gives the possibility to instantiate a constraint logic programming language with an arbitrary constraint domain. The interface between the system and such a constraint domain is given and the extensions to the Warren Abstract Machine (WAM) for this implementation are presented. 1 Introduction There already exist several implementations of constraint logic programming languages which are highly optimized for a certain constraint domain (for example PROLOG III , CHIP , CLP(!) , CLP(FD)...
Constraint Optimization using Preference Logics: A New Role for Modal Logic
- Allen Brown; Jr. Surya; Mantha Toshiro Wakayama
A family of modal logics of preference is presented. It is argued that modeling preference as a modal operator captures it at the correct level of granularity and extracts the logical core of the notion of preference. Next, the problem that motivated the development of preference logics is discussed in some detail. The paper ends with a list of other areas in which preference logics have shown promise. 1 Introduction The purpose of this paper is to outline the development of a logical theory of preference. While the work was motivated by an extremely concrete problem, the resulting theory turns...
Digit-Serial Reconfigurable Fpga Logic Block Architecture
- Hanho Lee; Gerald E. Sobelman
This paper presents a novel field-programmable gate array logic block architecture which incorporates support for digit-serial DSP architectures on a digit wide basis, without diminishing the support for random and control logic applications. To efficiently realize a digit-serial DSP design on FPGAs, one must create an FPGA architecture optimized for those types of systems. Key to the suitability of the FPGA for these applications is the fact that each of its basic blocks is capable of processing a digit-size of up to 4-bits. A novel digit-serial FPGA logic block architecture has been proposed to satisfy the requirement of rapid prototyping...
Needed Narrowing in Prolog
- Sergio Antoy
We describe the implementation of needed narrowing deployed in a compiler of a functional-logic language and present a few related concepts and results. Our implementation is obtained by translating rewrite rules into Prolog source code and optionally applying a set of optimizations to this code. We benchmark the effectiveness of each individual optimization. We show that our implementation is more efficient than all other previously proposed similar implementations. We measure both execution times, as is customarily done, and memory allocation that turns out to be a significant factor. We solve equations using a semi-strict equality relation that generalizes classic strict...
Pruning in Logic Programming
- Lee Naish
The logic programming community has a love--hate relationship with operators for pruning the search space of logic programs such as cut, commit, once, conditionals and variations on these. Pruning operators typically are not declarative, result in incompleteness and/or unsoundness, decrease readability and flexibility of code and make program analysis and transformation more difficult. Despite this, nearly all non-trivial Prolog programs contain cuts, nearly all more recent logic programming languages have similar pruning operators and many languages insist on pruning operators in every clause. In practice, logic programming is less logical than functional programming. Why it this so? Do we really...
Efficient Execution of HiLog in WAM-based Prolog implementations
- Konstantinos Sagonas; David S. Warren
In this paper we address the problem of efficiently implementing HiLog, a logic programming language with higher-order syntax and first-order semantics. In contrast to approaches proposed in the literature that modify, or abandon the WAM framework in order to implement HiLog, our approach to the problem stems from a belief that the WAM should be an adequate abstract machine for the execution of any logic language with first-order semantics. To show how to implement HiLog by staying within the WAM framework, we identify the reasons for poor performance characteristics of HiLog programs, present requirements for efficient HiLog execution, and propose...
Heuristic Methods for Over-Constrained Constraint Satisfaction problems
- Richard J. Wallace; Eugene C. Freuder
Introduction Constraint satisfaction problems (CSPs) involve finding an assignment of values to variables that satisfy a set of constraints between these variables. In many important applications the problems may be overconstrained, so that no complete solution is possible. In these cases, partial solutions may still be useful if a sufficient number of the most important constraints are satisfied. An example of such partial constraint satisfaction is the maximal constraint satisfaction problem (MAX-CSP), in which the goal is to find assignments of values to variables that satisfy the maximum number of constraints. An important type of CSP is the satisfiability problem...
A Meaning Representation Language for Co-operative Dialogue
- G. J. Doe; G. A. Ringland; M. D. Wilson
A meaning representation language is described which includes a typed firstorder logic with relativised quantification, using an ontology with reified events and actions. This has been developed to support the requirements of multimodal co-operative dialogue, including ambiguity, temporal and aspectual reference in natural language, reference to graphical and dialogue objects of varying complexity, explanation, and the differing approaches needed to interpret assertions, questions and commands.