An operational semantics for Paragon: A design notation for parallel architectures

The need to design and verify architectures to support parallel implementations of declarative languages has led to the development of a novel language, called Paragon, which bridges the gap between the top-level specification of the abstract machine, and its detailed implementation in terms of parallel processes and message passing. The central technical contributions in this paper are:

? The introduction and specification of Paragon, a parallel object-oriented language based on graph rewriting and message passing principles.

? An illustration of the approach at work in the design of a parallel supercombinator graph reduction machine.

? A sketch proof that this design meets the requirements statement.

     

Specification and refinement of networks of asynchronously communicating agents using the assumption/commitment paradigm

This paper presents an assumption/commitment specification technique and a refinement calculus for networks of agents communicating asynchronously via unbounded FIFO channels in the tradition of Kahn.

We define two types of assumption/commitment specifications, namely simple and general specifications.

It is shown that semantically, any deterministic agent can be uniquely characterized by a simple specification, and any nondeterministic agent can be uniquely characterized by a general specification.

We define two sets of refinement rules, one for simple specifications and one for general specifications. The rules are Hoare-logic inspired. In particular the feedback rules employ invariants in the style of a traditional while-rule.

Both sets of rules have been proved to be sound and also (semantic) relative complete.

Conversion rules allow the two logics to be combined. This means that general specifications and the rules for general specifications have to be introduced only at the point in a system development where they are really needed.

     

Thinking in parallel: four steps to Parlog

If you are familiar with Prolog but not with Parlog then this tutorial is aimed at you. In what follows I attempt to:

? explain the basics of Parlog

? demonstrate that Parlog programs can be powerful and elegant

? discuss the relationship of Parlog to Prolog, and

? identify some resources which will take you further.

These are what I call ‘four steps to Parlog’.     

Stable semantics for disjunctive programs

We introduce the stable model semantics fordisjunctive logic programs and deductive databases, which generalizes the stable model semantics, defined earlier for normal (i.e., non-disjunctive) programs. Depending on whether only total (2-valued) or all partial (3-valued) models are used we obtain thedisjunctive stable semantics or thepartial disjunctive stable semantics, respectively. The proposed semantics are shown to have the following properties:

? For normal programs, the disjunctive (respectively, partial disjunctive) stable semantics coincides with thestable (respectively,partial stable) semantics.

? For normal programs, the partial disjunctive stable semantics also coincides with thewell-founded semantics.

? For locally stratified disjunctive programs both (total and partial) disjunctive stable semantics coincide with theperfect model semantics.

? The partial disjunctive stable semantics can be generalized to the class ofall disjunctive logic programs.

? Both (total and partial) disjunctive stable semantics can be naturally extended to a broader class of disjunctive programs that permit the use ofclassical negation.

? After translation of the programP into a suitable autoepistemic theory \( \hat P \) the disjunctive (respectively, partial disjunctive) stable semantics ofP coincides with the autoepistemic (respectively, 3-valued autoepistemic) semantics of \( \hat P \) .

     

Inventive machine: Second generation

Inventive Machine project is the matter of discussion. The project aims to develop a family of AI systems for intelligent support of all stages of engineering design. Peculiarities of the IM project:

1. deep and comprehensive knowledge base — the theory of inventive problem solving (TIPS)
2. solving complex problems at the level of inventions
3. application in any area of engineering
4. structural prediction of engineering system development

The systems of the second generation are described in detail     

Software system for automatic interpretation of ionosphere sounding data

The present paper is concerned with methods and algorithms of the software system for the automatic interpretation of radio physics information, as acquired by an FMCW ionosonde (at the Institute of Solar-Terrestrial Physics, Siberian Branch, Russian Academy of Sciences), which provides for vertical sounding (VS) and oblique sounding (OS) of the ionosphere. The following problems were considered within this problem:

1. preprocessing to suppress noise from images and improve amplitude characteristics
2. data compression using a cellular automaton
3. interpretation of VS and OS ionograms.

The method of interpreting ionograms is based on using simulation data for the frequency dependences of the long-term prediction propagation characteristics and the results of processing experimental data.     

On Bounded Rational Trace Languages

In this paper, for a finitely generated monoid M, we tackle the following three questions:

1. Is it possible to give a characterization of rational subsets of M which have polynomial growth?
2. What is the structure of the counting function of rational sets which have polynomial growth?
3. Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds?

We give a positive answer to all the previous questions in the case that M is a direct product of free monoids. Some of the proved results also extend to trace monoid.     

Entwicklungstendenzen im Bereich der Fahrzeugelektronik

Applications in the automobile sector, wired or unwired, are today often integrated into a network of sensors and actors as well as in service functions, visualization, and entertainment. The paper presents an innovative platform, which is applicable for automotive and automation applications. & IT systems for automobiles and for business applications took a very different development direction.

? In the automotive sector a lot of proprietary IT systems have been developed.

? The increasing requirements of automotive applications require platform concepts, which are based on open standards.

     

Separability and one-way functions

We settle all relativized questions of the relationships between the following five propositions:

• P = NP.
• P = UP.
• P = NP $\cap$ coNP.
• All disjoint pairs of NP sets are P-separable.
• All disjoint pairs of coNP sets are P-separable.

We make the first widespread use of variations of generic oracles to achieve the necessary relativized worlds.     

Kernel language KLND

This paper presents a kernel language KLND on the basis of analysing the kernel languagerequirements of new generation computer systems. These requirements are: the ability ofknow-ledge processing, the parallelism, the elegant mathematical properties of the comput-ation model which is appropriate for working as the basis of the novel architecture design, andthe suitability for writing large scale softwares. The main features of KLND are as follows: 1. several new language concepts. 2. the modularity, 3. the unification of logical and functional programming styles, 4. the exploitation of the parallelism. 5. the introduction of the type concept, 6. the introduction of the storage concept.     

An approach to the DIN Kernel Lisp definition

A DIN Kernel LISP Draft (DKLisp) has been developed by DIN as Reaction to Action D1 (N79), short term goal, of ISO WG16. It defines a subset language, as compatible as possible with the ANSICommon-Lisp draft, but also with theEuLisp draft. It combines the most important LISP main stream features in a single, compact, but nevertheless complete language definition, which thereby could be well suited as basis for a short term InternationalLisp Standard. Besides the functional and knowledge processing features, the expressive power of the language is well comparable with contemporary procedural languages, as e.g. C++ (of course without libraries). Important features ofDKLisp are:

to be a “Lisp-1,” but allowing an easy “Lisp-2” transformation;

to be a simple, powerful and standardized educationalLisp;

to omit all features, which are unclean or in heavy discussion;

DKLisp programs run nearly unchanged inCommon-Lisp;

DKLisp contains a simple object and package system;

DKLisp contains those data classes and control structures also common to most modernLisp and non-Lisp languages;

DKLisp offers a simple stream I/O;

DKLisp contains a clean unified hierarchical class/type system;

DKLisp contains the typical “Lisp-features” in an orthogonal way;

DKLisp allows and encourages really small but powerful implementations;

DKLisp comes in levels, so allowing ANSICommon-Lisp to be an extension ofDKLisp level-1.

The present is the second version of the proposal, namely version 1.2, with slight differences with respect to the one sent to ISO. Sources of such changes were the remarks generously sent by many readers of the previous attempt.     

RaumComputer

The RoomComputer is an embedded system and as such offers unprecedented chances to manage buildings. Several RoomComputers can be networked via the Intra-/Internet, which makes it possible to monitor, control, and manage rooms and buildings on a unified worldwide accessible platform, irrespective of any particular local technology. It can be easily installed in any building and gives access to a full set of services. It implements a distributed system, which provides secure and controlled access to services like

1. control of light, heating, ventilation, air and climate
2. communication facilities like unified messaging, telephone, fax, etc.
3. reservation of rooms and required resources
4. localization of persons and equipment within rooms and buildings
5. entrance control (i.e. locking/unlocking doors)
6. organization of maintenance and house keeping, and
7. charging and billing.

     

Word-Mappings of Level 2

A sequence of natural numbers is said to have level k, for some natural integer k, if it can be computed by a deterministic pushdown automaton of level k (Fratani and Sénizergues in Ann Pure Appl. Log. 141:363–411, 2006). We show here that the sequences of level 2 are exactly the rational formal power series over one undeterminate. More generally, we study mappings from words to words and show that the following classes coincide:

the mappings which are computable by deterministic pushdown automata of level 2

the mappings which are solution of a system of catenative recurrence equations

the mappings which are definable as a Lindenmayer system of type HDT0L.

We illustrate the usefulness of this characterization by proving three statements about formal power series, rational sets of homomorphisms and equations in words.     

Powerful Parallel and Symmetric 3D Thinning Schemes Based on Critical Kernels

The main contribution of the present article consists of new 3D parallel and symmetric thinning schemes which have the following qualities:

They are effective and sound, in the sense that they are guaranteed to preserve topology. This guarantee is obtained thanks to a theorem on critical kernels;

They are powerful, in the sense that they remove more points, in one iteration, than any other symmetric parallel thinning scheme;

They are versatile, as conditions for the preservation of geometrical features (e.g., curve extremities or surface borders) are independent of those accounting for topology preservation;

They are efficient: we provide in this article a small set of masks, acting in the grid ?³, that is sufficient, in addition to the classical simple point test, to straightforwardly implement them.

     

The Alexander Method — A technique for the processing of recursive axioms in deductive databases

We propose a technique for handling recursive axioms in deductive databases. More precisely, we solve the following problem: Given a relational query including virtual relations defined from axioms (Horn clauses, with variables in the conclusion predefined in the hypotheses), which can be recursive, how to translate this query into arelational program, i. e. a set of relational operations concerning only real relations (not virtual). Our solution has the following properties:

? the program to evaluate the query always terminates,

? the relational program is produced by a pure compilation of a source query and of the axioms, and is independent of the data values (there is no run-time),

? the relational operations are optimized: theyfocus towards the computation of the query, without needless computations.

As far as we know, the Alexander Method is the first solution exhibiting all these properties. This work is partly funded by Esprit Project 112 (KIMS).     

Sweep methods for parallel computational geometry

In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include:

General hidden-surface elimination (even if the overlap relation contains cycles).

CSG boundary evaluation.

Computing the contour of a collection of rectangles.

Hidden-surface elimination for rectangles.

There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted.     

Unternehmensweites Berechtigungsmanagement

The central coordination of access control management is crucial especially for companies that are engaged in cooperative processes with other companies. Most critical is to respect the security needs that arise with the “opening“ towards other partners.

• The central coordination of access control is indispensable in order to protect the company’s resources.
• If access control management is to be oriented directly towards the corporate goals in contrast to a merely technical view there is a need for extended concepts — like role based access control (RBAC).
• The first software products that make use of the RBAC-concept for a centrally coordinated access control management are available and can be used in practice.