## SEARCH

#### Institution

##### ( see all 1670)

- Universität des Saarlandes 29 (%)
- University of California 24 (%)
- Stanford University 22 (%)
- University of Waterloo 22 (%)
- IBM Thomas J. Watson Research Center 18 (%)

#### Author

##### ( see all 3331)

- Rozenberg, G. 18 (%)
- Engelfriet, Joost 16 (%)
- Hesselink, Wim H. 11 (%)
- Vogler, Walter 11 (%)
- Meduna, Alexander 9 (%)

## CURRENTLY DISPLAYING:

Most articles

Fewest articles

Showing 1 to 10 of 1551 matching Articles
Results per page:

## Developmental systems with locally catenative formulas

### Acta Informatica (1973-09-01) 2: 214-248 , September 01, 1973

### Summary

A locally catenative sequence of strings of letters is such that each string in the sequence, after an initial stretch, is formed by concatenating strings which occurred at some specified distances previously in the sequence. These kinds of structures are frequently encountered in biological development, particularly in the case of compound branching structures or compound leaves. Developmental systems have been formally defined in previous publications. One of the present results is that dependent PDOL systems can produce sequences for every locally catenative formula (PDOL systems are propagating, deterministic developmental systems without interactions). Every dependent PDOL system produces a sequence which satisfies an infinite class of locally catenative formulas. Some of these formulas can be derived from a minimum formula, but a sequence may satisfy more than one minimum formulas.

## Affine relationships among variables of a program

### Acta Informatica (1976-06-01) 6: 133-151 , June 01, 1976

### Summary

Several optimizations of programs can be performed when in certain regions of a program equality relationships hold between a linear combination of the variables of the program and a constant. This paper presents a practical approach to detecting these relationships by considering the problem from the viewpoint of linear algebra. Key to the practicality of this approach is an algorithm for the calculation of the “sum” of linear subspaces.

## Step failures semantics and a complete proof system

### Acta Informatica (1989-11-01) 27: 125-156 , November 01, 1989

### Summary

The (linear) failures semantics is a well-known model for the theoretical version of Hoare's CSP. We generalize this semantics by taking steps (i.e. multisets of simultaneously occurring actions) instead of single actions as the basic execution unit. Hence opposed to the linear semantics — where parallelism is modelled as arbitrary interleaving in order to avoid technical complication — the step failures semantics models parallelism explicitly and is equally easy to manage. In particular a sound and complete proof system is given. Opposed to the linear model divergence is treated uniformly here. The relation to the linear semantics can be established using our newly introduced deparallelize operator.

## A balanced search tree with O(1) worst-case update time

### Acta Informatica (1988-11-01) 26: 269-277 , November 01, 1988

### Summary

In this paper a new data structure is described for performing member and neighbor queries in *O*(log*n*) time that allows for *O*(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only *O*(1) amortized time or *O*(log^{*}*n*) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.

## The time complexity of typechecking tree-walking tree transducers

### Acta Informatica (2009-04-01) 46: 139-154 , April 01, 2009

Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of *k* tree-walking tree transducers can be typechecked in (*k* + 1)-fold exponential time. Consequently *k*-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (*k* + 2)-fold exponential time. The results hold for both ranked and unranked trees.

## First-order identities as a defining language

### Acta Informatica (1980-10-01) 14: 337-357 , October 01, 1980

### Summary

Inverting the adage that a data type is just a simple programming language, we take the position that a programming language is, semantically, just a complex data type; evaluation of a program is just another operation in the data type. The algebraic approach to data types may then be applied. We make a distinction between specification and modelling, and we emphasize the use of first-order identities as a specification language rather than as a tool for model-building. Denotational and operational semantics are discussed. Techniques are introduced for proving the equivalence of specifications. Reynolds' lambda-calculus interpreter is analyzed as an example.

## Information theoretic approximations for M/G/1 and G/G/1 queuing systems

### Acta Informatica (1982-04-01) 17: 43-61 , April 01, 1982

### Summary

This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an *M/G*/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact *M/M*/1 results when *G = M*. For the case when a *G/G*/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known *M/M*/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the *M/M*/1 formulas.

## Languages accepted by systolic Y-tree automata: structural characterizations

### Acta Informatica (1992-08-01) 29: 761-778 , August 01, 1992

In this paper closure properties and decision problems for families of languages accepted by deterministic and nondeterministic systolic binary Y-tree automata are studied. Non closure results under basic language operations are stated by means of new nonacceptability criteria for these classes of automata. Necessary and sufficient conditions are given in terms of the shape of the underlying Y-tree, for the closure under λ-free regular substitution, concatenation, inverse homomorfism and for the closure under right concatenation with and quotient by finite sets. Moreover in the nondeterministic case necessary and sufficient conditions are given again in terms of the shape of the underlying Y-tree for the closure under right concatenation with regular sets and for the decidability of the problems of emptiness, finiteness, equivalence and co-emptiness. A sufficient condition is given for the decidability of the stability problem, in the deterministic case, while some undecidability results are proved in the nondeterministic case.

## Abstractions of data types

### Acta Informatica (2006-04-01) 42: 639-671 , April 01, 2006

The use of abstraction in the context of abstract data types, is investigated. Properties to be checked are formulas in a first order logic under Kleene's 3-valued interpretation. Abstractions are defined as pairs consisting of a congruence and a predicate interpretation. Three types of abstractions are considered,∀∀, ∀∃ and ∃^{0,1}∀, and for each of them corresponding property preservation results are established. An abstraction refinement property is also obtained. It shows how one can pass from an existing abstraction to a (less) finer one. Finally, equationally specified abstractions in the context of equationally specified abstract data types are discussed and exemplified.

## A specification technique based on predicate transformers

### Acta Informatica (1981-08-01) 15: 425-445 , August 01, 1981

### Summary

This paper proposes a formal specification technique based on the notion of predicate transformers. Several approaches to showing the completeness are investigated. A method for proving the correctness of an implementation with respect to a formal specification is described.