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.

     

Zur semantischen Interoperabilität in der Energiebranche: CIM IEC 61970

This contribution provides an introduction to the Common Information Model CIM which is an international standard maintained by the International Electrotechnical Commission IEC. Today’s market requirements towards the model are discussed, furthermore, we give an introduction to the history of the CIM, its serializations and scope of application. The contribution concludes with an overview of future use of the CIM for both science and commerce. Briefly, we focus on:

Message-based loose coupling of information systems

Exchange of power grid topologies with minimal communication and data overhead

Data quality assurance using ontology-based meta annotations and

Integration of heterogeneous standards in the utility domain. The contribution presents solutions to the use cases providing a better information management for the utility utilizing the Common Information Model.

     

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.     

An approach to efficient distributed transactions

Most distributed systems proposed on the basis of the concept of atomic action or transaction strongly limit parallelism, thus reducing their level of efficiency. In this paper, features of efficiency in a distributed transaction system are investigated. Two mechanisms are proposed in order to enhance potential concurrency both among different transactions and within a single transaction during the commit phase:

- a synchronization mechanism has been designed which suggests an approach to concurrency control by allowing the release of acquired locks before transaction completion. The possibility of exploiting this mechanism to implement nested transactions is also discussed.

- a distributed commit protocol is developed which enhances concurrency among the participants in an atomic action, thus achieving quick execution with high modularity.

     

Some computational problems in linear algebra as hard as matrix multiplication

We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:

KER _n : Compute a basis of the kernel for a givenn×n-matrix,

OGB _n : Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form,

SPR _n : Find a sparse representation of a givenn×n-matrix.

     

High-speed tools for Global Information Management I. Information processing and retrieval

The general specifications and design for a High-Speed General Information Management System, HSGIMS, to serve as the basis for a Global Information Network are given. Some of the key specifications that have been confirmed in experiments with a prototype of the HSGIMS are:

1. Information (or data) and Question-type (or logical data) independence.
2. Very small bounded search times that are independent of the amount of information that is managed and can be computed exactly.
3. A fool-proof security system that can be used to protect databases against viruses and can also be easily invoked to deny unauthorized access by users.
4. Efficient use of all storage and communications resources.

     

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.     

Enhanced qualitative physical reasoning system: Qupras

There are many expert systems that use experimental knowledge for diagnostic analysis and design. However, there are two problems for systems using only experiential knowledge:

1. unexpected problems cannot be solved and
2. acquiring experiential knowledge from human experts is difficult.

To solve these problems, general principles or basic knowledge must be added to expert systems in addition to the experimental knowledge. In response, we previously proposed Qupras (Qualitative physical reasoning system) as a framework for basic knowledge. This system has two knowledge representations, one related to physical laws and the other to objects. By using this knowledge, Qupras reasons about the relations among physical objects, and predicts the next state of a physical phenomenon. Recently, we have improved some of Qupras’ features, and this pater desctibes the following main enhancements:

1. inheritance for representation of objects,
2. new primitive representations to describe discontinuous change, and
3. control features for effective reasoning.

     

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’.     

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.

     

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

This paper presents the following results on sets that are complete for NP.

1. If there is a problem in NP that requires $2^{n^{\Omega(1)}}$ time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
2. If there is a problem in co-NP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
3. If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP??co-NP, then there is a Turing complete language for NP that is not many-one complete.

Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.     

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     

Trial and error

A pac-learning algorithm isd-space bounded, if it stores at mostd examples from the sample at any time. We characterize thed-space learnable concept classes. For this purpose we introduce the compression parameter of a concept classb and design our Trial and Error Learning Algorithm. We show: b isd-space learnable if and only if the compression parameter ofb is at mostd. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes:

- all intersection closed concept classes with finite VC-dimension.

- convexn-gons in ?².

- halfspaces in ?ⁿ.

- unions of triangles in ?².

We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter.     

Regular prefix relations

We define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class:

1. the relations recognized by a new type of automaton, the prefix automata,
2. the relations recognized by tree automata specialized to relations on strings,
3. the relations between strings definable in the second order theory ofk successors,
4. the smallest class containing the regular sets and the prefix relation, and closed under the Boolean operations, Cartesian product, projection, explicit transformation, and concatenation with Cartesian products of regular sets.

We give concrete examples of regular prefix relations, and a pumping argument for prefix automata. An application of these results to the study of inductive inference of regular sets is described.     

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.

     

A globally convergent algorithm based on imbedding and parametric optimization

The continuation method, well-established for the solution of nonlinear equations is extended to restricted optimization problems. Only the locally active restrictions are considered along the homotopy path. It is assumed that there are only finitely many critical points, i. e. that there are only finitely many changes of the index set of active restrictions. The globally convergent algorithm which we present proceeds in three stages:

1. Within each stability region, the solution is computed by the classical continuation method.
2. On the boundary of a stability region, a critical point \(\bar t\) is determined.
3. A new active index set is determined when \(\bar t\) is passed.

For the class of convex problems, the hypotheses for the convergence of the algorithm may be secured. The algorithm is applied to several examples.     

Einsatzpotenziale von XML in Business-Intelligence-Systemen

This article describes the actual applications of XML in the context of Business- Intelligence-Systems (BI). The potentials and synergies of XML and BI will be emphasized.

1. XML applications can be found within all levels of BI-systems.
2. The application of core-standards will be introduced as well as the possibilities of BI specific-standards.
3. The discussion of the impact of XML for BI-systems follows along the dimensions: externalisation, integration, standardisation and rationalization.

     

An algorithm for solving sparse Nonlinear Least Squares problems

We introduce a new method for solving Nonlinear Least Squares problems when the Jacobian matrix of the system is large and sparse. The main features of the new method are the following:

1. The Gauss-Newton equation is “partially” solved at each iteration using a preconditioned Conjugate Gradient algorithm.
2. The new point is obtained using a two-dimensional trust region scheme, similar to the one introduced by Bulteau and Vial.

We prove global and local convergence results and we present some numerical experiments.