Computation Theory

We implemented the first version of the interface-compiler for PASCAL. The main problems we are faced with the following.a) Efficiency: The increased number of procedure calls (e.g. a number of code generation routines had to be created) demands greater efforts during the run time of the compiler.An inline code substitution for procedure calls should be applied to avoid an additional overhead.b) The complexity of PASCAL (compared with CDL 2) leads to a corresponding complexity of the interface between the code generator and the translator. To mange this, all exchanged routines have to be specified in a reasonable way.There is a very urgent need of the specification both of the code generator and the translator: In implementing a new code generator, the implementor has to know the effect of the code generation routines to be inplemented and the effect of the translator routines to be used in this implementation.The specification problem is rather complicated because we have to abstract from the details of all target codes in question.Altogether, the interface-compiler seems to be the basis of compilers for PASCAL-like languages with a higher degree of portability and with a problem-directed compiler structure.For a closer information on this project, see /Bothe 85/.

Properties of concurrent systems like deadlock-avoidance, fairness etc. can be achieved by appropriate controls of the external behaviour in many cases. The paper investigates the problem in which way such controls can be realized by restrictions of the internal state behaviour of the systems.

A new model of computation called VH-system is introduced. It is a formalization of domino tilings. We show how the semantics of nondeterminism on VH-systems, being a natural counterpart of the machinery of tilings, can be modified to cover both deterministic and alternating computations. As a by-product we present a new proof of the fact that the satisfiability problem of boolean Horn formulas is complete in PTIME.

In this paper we consider a 2-dimensional array acceptor, called Turing array machine /TAM/, which is a generalization of k-tape Turing machine for string languages. By means of this automaton the complexity classes of array languages are defined. For 2-dimension array languages a generalization of log-space reducibility relation is introduced so that every language which is NL-complete is also complete for the class of array languages accepted by TAMs in log space. It is also shown that there exists array language over 1-letter alphabet which is complete for the class of array languages accepted by nondeterministic TAMs in log space. It turned out that when proving equality or inequality of the classes NL and L we face the same difficulties when proving this property for array counterparts of the above classes. At the end we introduce an array language, called projection accessibility problem /PAP/, over 1-letter alphabet, which is log-space complete and is accepted by some nondeterministic finite automaton. It follows, that if there exists any deterministic automaton with a finite number of pebbles which accepts PAP then NL=L.

Harel proved that the dynamic logic is complete in the class of arithmetical interpretations. The set of natural numbers stands for primitive notion in arithmetical interpretations, i.e. the following condition holds: "there exists a unary relation symbol nat such that for every arithmetical interpretation I, nat_I is the set of natural numbers". It is proved that the completeness is lost when this condition is relaxed to the following one: "for every interpretationI involved, the set of natural numbers is first-order definable in I". Thus we prove that the dynamic logic is not relatively complete in the sense of Cook.

In this paper we have shown some results for decision trees with tests from the essentially wider class of functions than the polynomials of bounded degree.We introduced the notion of functions r-distant to R_d[x] and have shown how starting from decision trees we can derive lower bounds in the model of computation trees. This relation suggests an uniform approach to lower bound proving in decision and computational tree models.

The paper studies the semantic and implementation problems of programming languages which allow module concatenation. Three known languages of that class are Simula-67, Smalltalk and Loglan. The structure of program modules is treated as an algebra. A concise set of algebraic axioms defining this structure is given. The addressing problem is formulated in algebraic terms. The identifier binding rule is reduced to the evaluation of terms in the algebra of modules. The normal form theorem solves the question of this evaluation. The results allow to develop two efficient updating algorithms going beyond standard Dijkstra's algorithm and relevant for this class of languages. The paper ends with the detailed implementation techniques. The correctness of this implementation is proved. All of this allow to construct a new family of running-systems for languages with module concatenation.

For Rabin pair automata [R1] a standard form is defined /def. 2/ i.e. such that an ordered subset {s₁,...,s_2I-1} of states is distinguished in such a way that a path of a run is accepting /rejecting if for some i even/ odd, 1≤i≤2I-1, the s_i appears infinitely often, and all s_j, j<i only finitely many times. The class of standard automata is big enough to represent all f.a. representable sets /th.1/ but has many properties similar to special automata defined in [R1]. A standard regular expression is defined /def. 6/ describing a process of forming of an infinite tree, as well as a process of building of an automaton /analysis and synthesis theorems 3,4/. The standard regular expressions are a generalisation of McNaughtons formula v d . [N] /.

We propose a programming methodology for improving the efficiency of applicative parallel programs.The basic idea comes from the program transformation approach à la Burstall-Darlington, in which "new and more efficient" versions of the programs are derived from "old" ones.We extend that approach in the following two respects:we consider parallel concurrent programs, andwe provide a calculus for ensuring that the derived versions are more efficient.We consider that the programmer provides a first version of his/her program and then he/she discovers, maybe in an incremental way, some "facts" about it. Facts are then tested by the calculus and, if they are "accepted", they will be incorporated into the given version of the program via a translation algorithm, and a new version is thereby derived.

Most of the deduction algorithms are of the form of regular expressions. To investigate some properties of these deductions we introduce an extension of PDL with propositional constants and infinite conjunctions and disjunctions. We treat the formulas of the object logical language for which the deductions are as propositional variables, the sets of formulas — as propositional constants and the deductions — as regular programs. A Hilbert's style axiomatization of this logic is shown to be complete for countable Kripke structures of sets of formulas.Examples include a logic for the PDL logical consequences, a kind of a nonmonotonic deduction algorithm and some properties of logical consequences.

Let us now make the final conclusions concerning the learning processes in static and expanding systems. In a static system we are able to approximate a new concept and teach the system only that approximation. The relation between the concept and its approximation is stored as a system rule. In an expanding system we can teach the system the exact concept. Concepts learned by the system are used to approximate concepts which have to be learned. In static systems these approximations are replaced by larger approximations by applying system rules. For this reason the number of examples used by the teacher to teach a concept in static systems is greater than the number of examples needed to teach the same concept in expanding systems.

In this paper we present two results concerning the time and space complexity of context-free recognition. The first result states that cfl's can be recognized on a cube-connected computer (CCC) or on a perfect-shuffle computer (PSC) in log2n time using n6 processors. There are known algorithms with the same parallel time complexity but they use more powerful models of computation. The second result states that deterministic cfl's can be recognized in polynomial time using one log2n bounded pushdown store and log n tape. Known algorithms use log2n tape. Since algorithm is a simulation of a deterministic pda it may be looked upon as an efficient reduction of the height of the pushdown store. The second result is obtained by applying a transformation of a fast parallel recognition of deterministic cfl's and it can be viewed as an application of parallel algorithms to the design of efficient sequential algorithms.Both results are aimed not at improving the known complexity bounds, but rather at showing that the same complexity can be obtained on less powerful models of computation.

The paper is aimed at a comparision of the MAZURKIEWICZ-calculus of traces and trace languages with the calculus of semiwords and semilanguages. The method to do this is to translate the notions from these languages into the language of irreflexive partial orderings to detect parallelities and differences.

The computational complexity of the deadlock prediction problem in linear systems is investigated. An algorithm which solves this problem for linear systems is given. Its complexity is polynomial. The paper contains also an algorithm which solves the deadlock avoidance problem in the systems defined here. The computational complexity of that algorithm is also polynomial.

This paper is organised in two parts. In the first part, transition graphs, labelled at nodes, are considered as a general and nevertheless operational semantical setting for analysing some program properties that do not require the definition of the program constructs. Bisimulation, the known behaviour equivalence, is formulated for such transition graphs.In the second part, a family of formalized languages is considered and its expressiveness with respect to transition graphs is analysed. It is shown that Milner's semantical characterization of logical equivalence can be stated.

The implementation of CSP mechanisms in the Algol-like language with modern facilities is presented. Especially, the realization of communication between disjoint processes by a single data transfer and the realization of nondeterministic guarded commands is described. The semantics of implemented CSP mechanisms and their constraints in comparison to the standard CSP are investigated.