Genetic Algorithms in Engineering and Computer Science
- Edited D. Quagliarella,C. Poloni,G. Winter,John Wiley Sons
This paper deals with evolutionary processes, simulated on computers, i.e., Artificial
Evolution or Evolutionary Computation (EC) [BFM97]. At least since 1994, when the
first World Congress of Computational Intelligence (WCCI) [ZMR94] took place at
Orlando, Florida, EC has become one out of three major domains of Computational
Intelligence (CI), the other two being Neural and Fuzzy Computation. Their common
peculiarity, distinguishing the CI approach toward "computer intelligence" from the
classical AI approach, is the subsymbolic information processing, typical for Neural
Networks (NN), Fuzzy Logic (FL), and Evolutionary Algorithms (EA).
We concentrate here on just one branch of the EA, i.e., Evolution Strategies (ES)
[Rec71, Sch75], born at Berlin in...
A Rewrite Approach for Constraint Logic Programming
- Gilles Richard
. Constraint Logic Programming (CLP ) is an extension of
Logic Programming aimed at replacing the unification mechanism used
in Prolog, by a more general operation called constraint satisfaction. This
yields a more efficient evaluation process due to the use of appropriate
algorithms designed specifically for a given constraint domain. On the
other hand, it is known that pure logic programs can be represented as
rewrite rules, and executed using a version of Knuth-Bendix completion
procedure, called linear completion. Taking advantage of the simplification
techniques available with rewriting, linear completion acts as a loopavoiding
mechanism, pruning unnecessary computations when possible.
A very powerful feature must also be emphasized : for...
On the Compositionality and Analysis of Algebraic High-Level Nets
- Johan Lilius
: This work discusses three aspects of net theory: compositionality of nets,
analysis of nets and high-level nets.
Net theory has often been criticised for the difficulty of giving a compositional semantics
to a net. In this work we discuss this problem form a category theoretic point of view.
In category theory compositionality is represented by colimits. We show how a high-level
net can be mapped into a low-level net that represents its behaviour. This construction
is functorial and preserves colimits, giving a compositional semantics for these high-level
nets. Using this semantics we propose some proof rules for compositional reasoning with
Linear logic is a recently discovered...
Safety Property Verification of
- Lalita Jategaonkar Jagadeesan,Carlos Puchol,James E. Von Olnhausen
. We present a technique for automatically verifying linear-time temporal
logic safety properties of programs written in ESTEREL, a formally-defined
language for programming reactive systems. In our approach, linear-time temporal
logic safety properties are first translated into ESTEREL programs that model
these properties. Using the ESTEREL compiler, the translations are compiled in
parallel with the ESTEREL program to be verified. A trivial reachability analysis
of the output of the compiler then indicates whether or not the safety property is
satisfied by the program. We describe two real-world software problems --- ES-
TEREL versions of two features of the AT&T5ESS
switching system --- and one
well-known benchmark problem --- the...
Reconfigurable Processor Architectures
- On Hardware/software Codesign
No particular application is well-supported by a conventional microprocessor which has a predetermined
set of functional units. This is particularly true in highly dynamic areas, such as multimedia,
communications and other embedded systems. We suggest that additional silicon is used to
provide hardware which can be dynamically configured to support any application. By combining a
conventional microprocessor and FPGA reconfigurable logic on one chip, commodity pricing is maintained
and yet the same part can effectively support a wide range of applications. A novel FPGA
architecture is outlined which is particularly suitable for this style of implementation.
Keywords : FPGA, computer architecture, parallel processing, embedded systems.
Computer architecture has...
Completion of Rewrite Systems with Membership Constraints Part II: Constraint Solving
- Hubert Comon
this paper is to show how to solve the constraints that are involved in
the deduction mechanism of the first part. This may be interesting in its own since this
provides with a unification algorithm for an order-sorted logic with context variables and
can be read independently of the first part.
This can also be compared with unification of term schemes of various kind (Chen &
Hsiang, 1991; Salzer, 1992; Comon, 1995; R. Galbav'y and M. Hermann, 1992). Indeed,
Wave Pipelining YADDs - A Feasibility Study
- A. Mukherjee,M. Marek-sadowska,S. I. Long
In this paper we study circuit structures obtained from direct
mapping to pass transistor logic (PTL) of Yet Another Decision
Diagrams (YADDs). These structures have almost equal
delays along all the paths which makes wave pipelining possible.
We discuss the details of a complete design, clocking and
layout. In 0.5µm CMOS technology, YADDs can be clocked
at a fixed rate of 715MHz for any function. Our experimental
results suggest that 4 times increase of speed over standard
cell design is on the average possible for the price of similar
We analyze circuits obtained from mapping to PTL logic of
linearized, binary decision diagram (BDD) based structures
which we call...
Modelling and Analysis of a Steam Generator using UPPAAL
- Kare J. Kristoffersen,Paul Petterson
We present the modelling and analysis of a steam generator using the automatic
verification tool uppaal. The physical parts of the steam generator as
well as the control software are modelled in the language of timed automata.
Requirements to the system are stated in a real--time logic allowing for expessing
safety properties such as 'the waterlevel in the drum must never go
below nor above certain critical values'. Also the logic allows for expressing
bounded liveness properties, e.g. 'steam must be produced within a certain
timelimit'. The automatic modelchecker in uppaal is used to investigate
system behaviour with respect to logical properties.
In a steam generator water is let...
Learning stage transition rules with Indlog
- Rui Camacho
This paper describes the application of an Inductive Logic Programming system to Computer
Assisted Aircraft Pilot Training. The usefulness of Machine Learning techniques for
Computer Assisted Aircraft Pilot Training is assessed.
An Inductive Logic Programming system called Indlog is presented and some preliminary
results on applying it to the Computer Assisted Aircraft Pilot Training domain are reported.
The problem divides into a) learning operators (previously done by Sammut and Michie)
b) learning pre and post-conditions. Comprehensible pre and post-conditions were learned
using a regime in which training were augmented until predictive accuracy reached 100%.
Previous hand-coded pre and post-conditions were both incomplete and incorrect.
Inductive Logic Programming (ILP)[Mug91]...
- Ullrich Hustadt
The most natural means for specifying a non-classical logic is by means of a Hilbert
calculus. Usually, the semantics of a non-classical logic is given in terms of possible
worlds. Given an axiomatization of a non-classical logics, the correspondence problem
in these logics is to find for every given Hilbert axiom an equivalent property of
the accessibility relation (van Benthem (1984)). For mechanizing deduction in nonclassical
logics it is very important to find these correspondences Ohlbach (1991).
So far the method for finding the correspondences was mostly by intuition and the
verification required complex proofs van Benthem (1984).
SCAN is an algorithm which offers a method for computing...
Strong Modes can Change the World!
- Fergus Henderson
We investigate compile-time garbage collection, structure reuse, and destructive assignment
for logic programming languages, using an expressive strong mode system. By
attaching groundness and uniqueness information to each node of a variable's type tree,
the mode system forms the basis for carrying out these optimizations. Our system allows
polymorphic mode definitions to achieve a high level of expressiveness. We implement a
simple preprocessor that does structure re-use optimization for Prolog programs annotated
with mode declarations. Finally, we show how our mode system can be used to
provide declarative I/O for logical programming languages.
I'd like to thank Lee Naish (my supervisor), Harald Søndergaard, Jeff Schultz, Alistair
Moffat, Will Winsborough,...
A Logical View of Composition
- Gordon D. Plotkin
We define two logics of safety specifications for reactive systems. The logics
provide a setting for the study of composition rules. The two logics arise
naturally from extant specification approaches; one of the logics is intuitionistic,
while the other one is linear.
1 Introduction 1
2 Overview 3
2.1 A calculus of sets of behaviors : : : : : : : : : : : : : : : : : : 3
2.2 A calculus of sets of processes : : : : : : : : : : : : : : : : : : 5
2.3 Testing : : : : : :...
Coalgebras and Approximation
- Bart Jacobs
. Motivated by a new approach in the categorical semantics of
linear logic, we investigate some specific categories of coalgebras. They all
arise from the canonical comonad that one has on a category of algebras.
We obtain a very simple model of linear logic where linear formulas are
complete lattices and intuitionistic formulas are just sets. Also, in another,
domain theoretic example, we give a new characterization of continuous
posets (where every elemtent is join of elements way below) as coalgebras.
And finally we describe a related example where categories in which every
object is coproduct of indecomposables, are coalgebras. Approximation is
the key ingredient of all these coalgebras.
MORPH: A System Architecture for Robust High Performance Using Customization
- Andrew A. Chien,Rajesh K. Gupta
Achieving 100 TeraOps performance within a tenyear
horizon will require massively-parallel architectures
that exploit both commodity software and hardware
technology for cost efficiency. Increasing clock
rates and system diameter in clock periods will make
efficient management of communication and coordination
increasingly critical. Configurable logic presents a
unique opportunity to customize bindings, mechanisms,
and policies which comprise the interaction of processing,
memory, I/O and communication resources. This
programming flexibility, or customizability, can provide
the key to achieving robust high performance.
The MultiprocessOr with Reconfigurable Parallel
Hardware (MORPH) uses reconfigurable logic blocks
integrated with the system core to control policies, interactions,
and interconnections. This integrated configurability
can improve the performance of local memory
hierarchy, increase the efficiency of interprocessor
A Tableau System for Full Linear Temporal Logic
- Peter H. Schmitt,Jean Goubault-larrecq
We present a sound, complete and terminating tableau system for the propositional
logic of linear time with 2, 3, fl, W and U and the past operators
2 - , 3 - , flGamma , e flGamma , B and S.
Studied in [SC85]. We adopt the notations of [MP91].
2 Linear Temporal Logic
Formulas F , G, H, : : : , of linear temporal logic are built from variables A, B, C,
: : : by the following grammar:
F ::= A j :F j F F j F F
j 2F j 3F j flF j F W F j...
Improving Temporal Logic Tableaux using Integer Constraints
- Reiner Hahnle,Ortrun Ibens
In this position paper we present some ideas that aim to improve analytic tableau
for temporal logics with the ultimate goal of reviving the interest in using
them for temporal logic satisfiability checking. Although tableau formulations
for several propositional temporal logics exist , these are not used much in
practice, because the tableau size becomes intractable already for quite small
formulas. Moreover, checking tableau closure is complicated and expensive to
implement. For practical purposes, usually automata theoretic approaches are
preferred . It might, however, still be interesting to have competitive tableau
formulations as will be pointed out in Section 4.
The ideas for the research reported here were stimulated...
Recurrent Neural Networks to Approximate the Semantics of Acceptable Logic Programs
- Yvonne Kalinke,Hans-peter Stoerr
In this paper weshow that a feedforward neural network with at least one hiddenlayer canapproximate the meaning
function TP for an acceptable logic program P . This is found by using the property of acceptable logic programs
that for this class of programs the meaning function TP is a contraction mapping on the complete metric space of the
interpretations for P as shown by Fitting in .
Using this result it can be shown that for an acceptable program such a network can be extended to a recurrent neural
networks that is able to approximate the iteration of the meaning function TP , that is...
An Embedding of Timed Transition Systems in HOL
- Rachel Cardell-oliver,Roger Hale,John Herbert
The theory of Timed Transition Systems (TTSs) developed by Henzinger, Manna
and Pnueli provides a formal framework for specifying and reasoning about realtime
systems. In this theory a system is described by a set of state transitions
with associated time constraints. We report on work in progress to mechanize the
published theory of timed transition systems using the HOL theorem prover.
Different specification languages may be defined in terms of the TTS model. In
particular, a real-time temporal logic (RTTL) has been used for specifying requirements
and a graphical notation for specifying system designs. A semantics for each
of these languages can be given in terms of TTSs,...
A Tile-Based Coordination View of
activity tiles coordination tiles
Metodi e Strumenti per la
Progettazione e la Verifica di Sistemi Eterogenei Connessi mediante Reti di Comunicazione
Dipartimento di Informatica, Universit`a di Pisa,
Computer Science Laboratory, SRI International, Menlo Park,
Tiles are rewrite rules with side effects, reminiscent of both
Plotkin SOS and Meseguer rewriting logic rules. They are well suited for
modeling coordination languages, since they can be composed both statically
and dynamically via possibly complex synchronization and workflow
mechanisms. In this paper, we give a tile-based bisimilarity semantics
for the asynchronous-calculus of Honda and Tokoro and prove it
equivalent to the ordinary semantics. Two kinds of tiles are...
An Algebra-Based Method to Associate Rewards with EMPA Terms
- Marco Bernardo
. We present a simple method to associate rewards with terms
of the stochastic process algebra EMPA in order to make the specification
and the computation of performance measures easier. The basic idea
behind this method is to specify rewards within actions of EMPA terms,
so it substantially differs from methods based on modal logic. The main
motivations of this method are its ease of use as well as the possibility
of defining a notion of equivalence which relates terms having the same
reward, thus allowing for simplification without altering the performance
index. We prove that such an equivalence is a congruence finer than the
strong extended Markovian bisimulation...