95/1
FINITE ALGORITHMS
FOR DECODING RECURRENT ITERATED FUNCTION
A. Edalat, 21pp
We present two finite algorithms, the recurrent probabilistic domain algorithm for decoding a recurrent iterated function system (IFS) and the vector recurrent probabilistic domain algorithm for decoding a vector recurrent IFS on the digitised screen. Recurrent IFSs and vector recurrent IFSs are used for fractal image compression and our algorithms are the first finite algorithms in the state of art. They have the following advantages compared to the previous two known algorithms in the field:
- Our algorithms terminate in finite time on any digitised screen withoutneeding to fix a number of iterations in advance.
- There is a simple complexity analysis for the algorithms.
- The algorithms produce a good quality image up to several times faster than the other algorithms.
95/2
TRANSACTIONS
AND UPDATES IN DEDUCTIVE DATABASES
D. Montesi, E. Bertino and M. Martelli, 56pp
In this paper we develop a new approach providing a smooth integration of extensional updates and declarative query language for deductive databases. The approach is based on a declarative specification of updates in rule bodies. Updates are not executed as soon as they are evaluated. Instead, they are collected and then applied to the database when the query evaluation is completed. We call this approach non-immediate update semantics. We provide a top-down and equivalent bottom-up semantics which reflect the corresponding computation models. We also package set of updates into transactions and we provide a formal semantics for transaction language with control constructors still preserving formal semantics and semantics equivalence.
95/3
A BOUNDING
CIRCLE FOR THE ATTRACTOR OF AN IFS
A. Edalat, 2pp
Given an iterated function system consisting of a finite number of contracting affine maps on the plane and given any point of the plane, we obtain a circle centred at that point which contains the attractor of the IFS. We find the point on the plane such that the bounding circle centred at that point has minimum radius.
95/4
COMPUTER-AIDED
INCONSISTENCY MANAGEMENT IN SOFTWARE DEVELOPMENT
B. Nuseibeh, 15pp
The incremental development of software systems involves the detection and handling of inconsistencies. These inconsistencies arise in system requirements, design specifications and, quite often, in the final implemented software product. In this paper we explore different kinds of inconsistency that arise during different stages of software development, and examine the scope and role of computer-based tool support for managing inconsistency in this setting. In addition to detecting and removing inconsistencies, managing inconsistency also includes a wide range of activities that facilitate continued development in the presence of inconsistency. These include procedures for controlled amelioration and avoidance of incosistencies. The paper uses the ViewPoints framework for multi-perspective software development as a vehicle for the discussion, and as a test bed for tool support. The framework facilitates the development and composition of multiple partial specifications (ViewPoints), and is itself supported by automated tools that check and handle inconsistencies (The Viewer).
The paper makes a contribution towards a better understanding of the way in which complex software systems are developed, and consequently, the kind of automated tool support that needs to be provided in this setting.
95/5
DECENTRALISED
PROCESS ENACTMENT
U. Leonhardt, A. Finkelstein, J. Kramer and B. Nuseibeh,
26pp
The Viewpoints framework for distributed and concurrent software engineering provides an alternative approach to traditional centralised software development environments. We investigate the use of decentralised process models to drive consistency checking and conflict resolution in this framework. Our process models use pattern matching on local development histories to determine the particular situation (state) of the development process, and employ rules to trigger situation-dependent assistance to the user. We describe how communication between such process models facilitates the decentralised management of explicitly defined consistency constraints in the Viewpoints framework.
95/6
PROCEEDINGS
OF THE FIFTH CONFER WORKSHOP
R. Nagarajan, ed., 294pp
This is a collection of papers and copies of tranparencies representing the talks presented at the Fifth CONFER (CONcurrency and Functions: Evaluation and Reduction) Workshop, held at Imperial College, London, from 4th to 7th October, 1994.
Areas covered in the workshop included:
- Foundational Models and Abstract Machines
- Calculi
- Logics for Concurrency and the lambda-calculus
- Programming languages
95/7
MODAL LABELLED
DEDUCTIVE SYSTEMS
A. Russo, 81pp
We present a formalization of propositional modal logic in the framework of Labelled Deductive Systems (LDS) in which modal theory is presented as a "configuration" of several "local actual worlds". We define a natural deduction style proof system for a propositional modal labelled deductive system (MLDS). We describe a model-theoretical semantics (based on first-order logic) and we show that the natural deduction proof system is sound and complete with respect to this semantics. We also show that the semantics given here is equivalent to Kripke semantics for a normal modal logic whenever the initial configuration is a single point. Finally we discuss how this logic can be extended to the predicate case, we sketch some natural deduction rules for quantifiers and we discuss how such rules solve certain problems associated with the nesting of quantifiers within the scope of modal operators.
95/8
GEM - A GENERALISED
EVENT MONITORING LANGUAGE FOR DISTRIBUTED SYSTEMS
M. Mansouri-Samani and M. Sloman, 26pp
Event based monitoring is critical for managing and debugging networks and distributed systems. This paper presents GEM - an interpreted Generalised Event Monitoring language. It allows high level, abstract events to be specified in terms of combinations of lower level events from different nodes in a loosely coupled distributed system. Event monitoring components can thus be distributed within the system to perform filtering, correlation and notification of events close to where they occur and thus reduce network traffic. GEM is a declarative rule based language in which the notion of real time has been closely integrated and various temporal constraints can be specified for event composition. The paper discusses the effect of communication delays on composite event detection and presents a tree based solution for dealing with out-of-order event arrivals at event monitors.
95/9
AN APPROACH
TO ROLE BASED MANAGEMENT FOR DISTRIBUTED SYSTEMS
E. Lupu and M. Sloman, 23pp
Roles have been widely used for modelling the authority, responsibility, functions and interactions associated with manager positions within organisations. In this paper we discuss the issues related to specifying roles for both human and automated managers of distributed computer systems. The starting point is that a role can be defined in terms of the authorisation and obligation policies for a particular manager position which specify what actions the manager is permitted or is obliged to do on a set of target objects. This permits inidviduals to be assigned or removed from postions without respecifying the policies for the role. However these policies are insufficient for specifying the interaction protocols between managers and the targets they manage or between different manager roles. There is a need to specify the coordination and synchronisation relating to manager interactions.
This report describes notations and techniques applicable to specifying the interactions and activities related to manager roles in a distributed system and indicates which are the most suitable for implementation within a role based management framework. Structuring a management framework in terms of roles enables a more flexible and dynamic approach to the management of a complex system.
This study assumes the existence of an underlying monitoring service and of a specification language for management policies. The role based framework is composed of a set of tools enabling the creation of roles from policies, the specification of the relationships between roles and of protocols for role interaction. In addition, the issues related to conflicts which can occur between policies within a role or between interacting roles are briefly discussed.
95/10
MANAGEMENT
POLICY SERVICE FOR DISTRIBUTED SYSTEMS
D. Marriott, M. Sloman and N. Yialelis, 24pp
Interpreting policy in automated managers facilitates the dynamic change of behaviour of a distributed management system by simply changing policies. This paper describes a management policy notation which can be used to define both authorisation policies (what activities a manager is permitted to do) and obligation policies (the activities a manager must perform). Some example policy specifications are given to demonstrate the notation and the concepts involved. A graphical policy editor is described which permits high level abstract policies to be refined into lower level, implementable policies and maintains derivation and dependency relationships between the different policies. A policy service which stores policies is outlined and its integration within a domain service for grouping policies is explained. Outlines are given of implementations of automated managers for interpreting obligation policies and of an access control mechanism for enforcing authorisation policies.
95/11
TOWARDS INTEROPERABILITY
IN HETEROGENEOUS DATABASE SYSTEMS
A. Zisman and J. Kramer, 100pp
Distributed heterogeneous databases consist of systems which differ physically and logically, containing different data models and data manipulation languages. Although these databases are independently created and administered they must cooperate and interoperate. Users need to access and manipulate data from several databases, and applications may require data from a wide variety of independent databases. Therefore, a new system architecture is required to manipulate and manage distinct and multiple databases, in a transparent way, while preserving their autonomy.
This report contains an extensive survey on heterogeneous databases, analysing and comparing the different aspects, concepts and approaches related to the topic. It introduces an architecture to support interoperability among heterogeneous database systems. The architecture avoids the use of a centralised structure to assist in the different phases of the interoperability process. It aims to support scalability, and to assure privacy and confidentiality of the data. The proposed architecture allows the databases to decide when to participate in the system, what type of data to share and with which other databases, thereby preserving their autonomy. The report also describes an approach to information discovery in the proposed architecture, without using any centralised structure as repositories and dictionaries, and broadcasting to all databases. It attempts to reduce the number of databases searched and to preserve the privacy of the shared data. The main idea is to visit a database that either contains the requested data or knows about another database that possible contains this data.
95/12
A SIMPLE DECLARATIVE
LANGUAGE FOR DESCRIBING NARRATIVES WITH ACTIONS
A. Kakas, R. Miller, 52pp
We describe a simple declarative language E for describing the effects of a series of action occurrences within a narrative. E is analogous to Gelfond and Lifschitz's Language A and its extensions, but is based on a different ontology. The semantics of E is based on a simple characterisation of persistence which facilitates a modular approach to extending the expressivity of the language. Domain descriptions in A can be translated to equivalent theories in E . We show how, in the context of reasoning about actions, E 's narrative-based ontology may be exploited in order to characterise and synthesise two complementary notions of explanation. According to the first notion, explanation may be partly modelled as the process of suitably extending an apparently inconsistent theory written in E so as to establish consistency, thus providing a natural method, in many cases, to account for conflicting sets of information about the domain. According to the second notion, observations made at later times can sometimes be explained in terms of what is true at earlier times. This enables domains to be given an alternative characterization in which knowledge arising from observations is appropriately separated from other aspects of the domain. We also describe how E domains may be implemented as Event Calculus style logic programs, which facilitate automated reasoning both backwards and forwards in time, and which behave correctly even when the knowledge entailed by the domain description is incomplete.
95/13
AN AUTHENTICATION
SERVICE SUPPORTING DOMAIN BASED ACCESS CONTROL POLICIES
N. Yialelis and M. Sloman, 12pp
This paper describes the basic architecture of an authentication service for distributed systems in which domains are used to group objects in order to specify policy. This is necessary for very large scale systems where it is impractical to specify policies for individual objects. The enforcement of a policy that is specified in terms of domains requires authentication of object membership of domains.
As the use of asymmetric cryptography would result in unacceptable performance, the proposed system is based on the use of symmetric cryptography for intra-realm authentication of identities or domain membership, while asymmetric cryptography can still be used for inter-realm authentication. It utilises replicated trusted authentication servers with minimal state in order to avoid problems in terms of the security and state consistency of the replicas. This is achieved by using private-key certificates which provide a similar functionality to the public key certificates in asymmetric cryptosystems, but have better performance. Authentication servers are also used as translators, i.e. they translate messages that were encrypted with the secret key of the sender by re-encrypting them with the secret key of the receiver. The paper also describes the establishment of secure channels between remote objects as well as the authentication of object membership of domains.
95/14
A SECURITY
FRAMEWORK SUPPORTING DOMAIN BASED ACCESS CONTROL IN DISTRIBUTED SYSTEMS
N. Yialelis and M. Sloman, 17pp
This paper describes a security framework for object-based distributed systems which is being developed in the CORBA-compliant OrbixTM environment. This framework allows the development of secure distributed applications on existing operating systems that do not support distributed security. The design aims at making the authentication and access control mechanisms transparent to the application level and supporting access control policies specified using the concept of the management domain. This concept has been developed as a means of specifying policies in terms of groups of objects. The description focuses on how the Access Control List paradigm is combined with pseudo capabilities which are used as hints to improve the time-efficiency of the access control decision mechanism. The protocols to support the (cascaded) delegation of access rights to agents acting on behalf of a grantor are explained. A brief description of the authentication mechanism is also given.
95/15
MANAGING INCONSISTENT
SPECIFICATIONS: REASONING, ANALYSIS AND ACTION
A. Hunter and B. Nuseibeh, 32pp
In previous work, we have advocated continued development of specifications in the presence of inconsistency. To support this, we have used classical logic to represent partial specifications and to identify inconsistencies between them. We now present an adaptation of classical logic, which we term quasi-classical (QC) logic, that allows continued reasoning in the presence of inconsistency. The adaptation is a weakening of classical logic that prohibits all trivial derivations, but still allows all resolvants of the assumptions to be derived. Furthermore, the connectives behave in a classical manner. We then present a development called labelled QC logic that records and tracks assumptions used in reasoning. This facilitates a logical analysis of inconsistent information. We discuss the application of labelled QC logic in the analysis of multi-perspective specifications. Such specifications are developed by multiple participants who hold overlapping, often inconsistent, views of the systems they are developing. Finally, we discuss further the notion of acting in the presence of inconsistency, and examine the use of meta-level inconsistency handling rules to support such action. The feasibility of automated support for this kind of inconsistency handling is also discussed, and related work in the area is critically reviewed.
95/16
THE TRACTA
APROACH FOR BEHAVIOUR ANALYSIS OF CONCURRENT SYSTEMS
D. Giannakopoulou, 27pp
The need for modularity in the behaviour analysis of concurrent systems has been answered successfully by making reachability analysis compositional. Compositional reachability analysis (CRA) on the other hand, often exacerbates the state explosion problem; subsystem analysis leaves out information from the subsystem environment (context), which could considerably reduce the number of states allowed into its behaviour state-graph. To deal with that, we have chosen to incorporate context constraints in CRA . In the Tracta approach developed in our section, context constraints are expressed as processes in our model (we call them interface processes), that are composed with the subsystem, without affecting the global system behaviour. Tracta supports both automatically generated and user-specified interfaces. It also provides an elegant way of checking violation of safety properties by the system under analysis. This work, besides introducing the main open problems in this area of research, is a detailed presentation of Tracta and its underlying theory, in their current form.
95/17
RESULTS FROM
IMPLEMENTING THE EVENT CALCULUS IN CLP(R)
K.J. Dryllerakis, 16pp
This report presents an implementation of the Event Calculus under the constraint logic programming language CLP(R). Constraint logic programming is then put into context; its advantages and limitations are judged and proposals for solutions are made. The description of the implementation is given in phases corresponding to levels of increasing difficulty. All phases are meant to follow a general scheme so that the examples under consideration should be solved under all phases.
95/18
RESIDUAL SLDNF
IN CLP LANGUAGES
K.J. Dryllerakis, 11pp
This report gives an outline of the theoretical and practical framework for the implementation of a restricted form of residual SLDNF in languages falling under the general CLP scheme. The work is related to partial evaluation of goals in logic programs and to constructive negation. In particular, we implement constructive negation for artithmetic relations in the domain of real numbers under CLP(R).
95/19
HETEROGENEOUS
KNOWLEDGE REPRESENTATION: INTEGRATING CONNECTIONIST AND SYMBOLIC COMPUTATIONS
D. Montesi, 15pp
Heterogeneous knowledge representation allows us to combine several knowledge representation techniques. For instance connectionist and symbolic systems are two different computational paradigms and knowledge representation tools. Unfortunately, the integration of different paradigms and knowledge representations is not easy and very often is informal. In this paper, we propose a formal approach to integrate these two paradigms where as symbolic system we consider a (logic) rule-based system. The integration is operated at language level between neural networks and rule languages. The formal model that allows the integration is based on constraint logic programming and provides an integrated framework to represent and process heterogeneous knowledge. In order to achieve this we define a new language that allow us to express and model in a natural and intuitive way the above issues together with the operational semantics.
95/20
A CASE STUDY
IN REASONING ABOUT ACTIONS AND CONTINUOUS CHANGE (EXTENDED VERSION)
R. Miller, 19pp
This paper shows how the Situation Calculus can be extended to deal both with 'narratives' and with domains containing real-valued parameters, whose actual values may vary continuously between the occurrences of actions. In particular, a domain is represented where action occurrences may be 'triggered' at instants in time when certain parameters reach particular values. Its formalisation requires the integration of several types of default reasoning. Hence Baker's circumscriptive solution to the frame problem is extended to reflect the assumptions that by default a given action does not occur at a given time point, that by default a given set of parameter values does not trigger a given action, and that by default a given action occurrence does not result in a discontinuity for a given parameter. Regarding the minimisation of discontinuities, the example illustrates how circumstances can arise where, at a particular time point, discontinuities in some parameters can be 'traded' for discontinuities in others. It is argued that, in general, in such cases extra domain-specific information will be necessary in order to eliminate anomalous models of the domain.