6th Gl-Conference Dortmund, January 5–7, 1983
Partial functions abound in modern computing theory, and so any system which purports to naturally formalize it must treat them. Surprisingly the most common treatments do not work well for constructive formal systems, i.e., for those with computational content. Since constructive formal systems are significant in computer science, it is important to give an account of partial functions in them. This...
We present an algorithm which will factor an integer n quite efficiently if the class number h (-n) is free of large prime divisors. The running time T(n) (number of compositions in the class group) satisfies prob [T(m)≦n1/2r]≳(r−2)−(r−2) for random mε[n/2, n] and r≧2. So far it is unpredictable which numbers will be factored fast. Running the algorithm on all integers n·s with s≦rr and $$r = \sqrt...
This paper is a review of recent theoretical work on the problems which arise when many users access the same database. For a detailed exposition of this material, the interested reader is referred to a forthcoming monograph [Pa4].
In [1] M.J.Fischer and M.S.Paterson pointed out that finding the optimal planar layout of a weighted graph with respect to the L2-metric is NP-hard. We consider this problem with respect to the L1-city-block metric in the discrete and continuous case and show that it remains NP-hard.
This paper is devoted to the study of occurrence nets as models of non-sequential processes, and of some of their properties. We characterise the properties known as discreteness, K-density and D-continuity which have been proposed in the literature as meaningful properties of processes. We show that they are closely related to each other.
This paper contributes to the theory of graph grammars, studying the generated languages of graphs from the viewpoint of complexity theory. To this respect we naturally bridge the gap between graphs and strings. A string is identified with a graph which is an oriented chain, and conversely, a representation of a graph, e.g., by its adjacency matrix, is a well-structured string. Our main result states...
In a first informal section we shall discuss some problems with definitions of list functions. In particular we motivate the restrictions of pure LISP with respect to list expressions using the full lambda definability. In sections two and three we formally define the lambda-semantics of the pure LISP language as well as the denotational description of the original semantics of pure LISP as...
We introduce a new model of parallel computation, namely the FIFO nets. First, we introduce some basic definitions. A restriction of this model has the power of the Turing machine. Monogeneous Fifo nets are then introduced. The coverability tree is a procedure to decide whether a monogeneous net is bounded or not. At last, regularity is decidable for monogeneous nets.
Here is introduced an extension for infinite words of the classical notion of rational transduction. We prove that this extension has the important property of mapping the adherence of a language of finite words into the adherence of an other language of finite words. The set of such extensions is closed by composition and is exactly the family of the compositions of an inverse faithful sequential...
The specification of abstract data types requires the possibility to treat exceptions and errors. We present an approach allowing all forms of error handling : error introduction, error propagation and error recovery. The algebraic semantics of our method and a new correctness criterion is given. We also introduce an operational semantics of a subclass of our specifications which coincides with the...
In this paper the average number of nodes (nodes of degree t) appearing at some level k in a n-node ordered tree is computed. Exact enumeration formulae for the number of all n-node trees with r nodes (r nodes of degree t) at level k are derived. Assuming all n-node trees to be equally likely, it is shown that the expected number n1(n,k) of nodes (n1 (t)(n,k) of nodes of degree t) at level...
Independent tasks are nonpreemptively scheduled on m≧2 processors which are assumed to have different speeds. By generalizing ideas of bin packing techniques scheduling algorithms are constructed which have better worst case bounds than the well-known LPT algorithm.
The generalized maximum satisfiability problem contains a large class of interesting combinatorial optimization problems. Since most of them are NP-complete we analyze fast approximation algorithms. Every generalized ψ-satisfiability problem has a polynomial ɛψ-approximate algorithm for a naturally defined constant ɛψ, 0≤ɛψ>1 which is determined here explicitly for several ψ. It is shown...
The paper proposes an axiomatic approach to semantics of specification languages. It introduces the notion of a semantical system as a framework to discuss and compare various approaches to specification of (algebraic) data types and to spell out their underlying assumptions. For various of those assumptions we present complete specification languages or show that existing specification languages...
We consider parallel computers (PC's) with fixed communication network with bounded degree. We construct a universal PC with n1+0(1/log log (n)) processors which can simulate each PC with n prodessors with a time loss of 0(log log(n)). This improves a result of [1] where a time loss of 0(log (n)) was achieved but only using 0(n) processors. Furthermore we prove a time-processor trade-off for a very...
This paper considers the semantics of coroutines and processes in block structured languages; in particular, the problem of existence of static and dynamic environments. It is shown that a definition of inaccessible module instances may result in an inconsistent meaning of some operations. Both an Algol-like language and a SIMULA-like language, (with pointers yet without coroutines), are proven to...