Banská Bystrica, Czechoslovakia August 27–31, 1990 Proceedings
Y. Gurevich recently proposed a framework for semantics of programming concepts which directly reflects the dynamic and resource-bounded aspects of computation. This approach is based on (essentially first-order) structures that evolve over time and are finite in the same way as real computers are (so-called “dynamic algebras”). See Gurevich 1988 for the idea of dynamic algebras and its application...
Solving equations, also called unification, has made impressive progress during the past decade. Described as existentially quantified formulae over =, unification problems are usually transformed step by step until a solved form is reached from which a most general unifier can be obtained. Kirchner showed how to compute transformation rules for theories having a syntactic presentation, for which...
Kleene algebras are an important class of algebraic structures that arise in diverse areas of computer science: program logic and semantics, relational algebra, automata theory, and the design and analysis of algorithms. The literature contains at several inequivalent definitions of Kleene algebras and related algebraic structures [2,13,14,5,6,1,9,7]. In this paper we establish some...
In order to acquire insight about arbitrary branching programs, a number of restricted branching program models have been considered. Among these are decision trees, read-once-only branching programs length-restricted oblivious branching programs and width-restricted branching programs. In the following we survey some results which characterize the computational power of such restricted models. Interestingly,...
This survey paper describes new types of dynamic hashing strategies for implementing dictionaries on sequential, parallel and distributed computation models. In particular, it surveys the progress in constructing and analyzing new classes of universal hash functions.
In complexity theory a one-way function is defined to be a one-one, honest, function that is computable in polynomial time whose inverse is not computable in polynomial time. We will examine relationships between the complexity of functional computational problems and ordinary set recognition problems. The complexity of inverting one-way functions will follow from these relationships. Then, we will...
Initially functional languages were implemented using tree reduction or term rewriting. It was realized in 1971 by Wadsworth that more efficient execution would result if shared subexpressions were reduced only once, leading to the mechanism of graph reduction. Graph reduction is considered an attractive possibility to achieve parallel execution on distributed memory architectures. However, serious...
We prove that every set in uniform-AC0 can be recognized by a uniform family of depth-three threshold circuits of size $$n^{log^{O(1)} n}$$ .
We consider the problem of separating a given set of d-dimensional non-overlapping isothetic hyperrectangles by means of one cutting isothetic hyperplane. If the cutting hyperplane crosses one hyperrectangle this is split into two non-overlapping hyperrectangles. We show that there always exists a cutting hyperplane which separates n given hyperrectangles into two sets each containing no more than...
We investigate the preemptive scheduling of periodic, real-time task systems on one processor. We present three major results. First, we show that the Simultaneous Congruences Problem is NP-complete in the strong sense. Although this result is included primarily as a lemma for showing our next major theorem, it is important in its own right, answering a question that has been open for ten years. Our...
We present an operational model O and a continuation based denotational model D for a uniform variant of Prolog, including the cut operator. The two semantical definitions make use of higher order transformations Φ and Ψ, respectively. We prove O and D equivalent in a novel way by comparing yet another pair of higher order transformations Φ and Ψ, that yield Φ and Ψ, respectively, by application of...
Immerman and Szelepcsényi's inductive counting technique demonstrated that, for space classes, the nondeterministic acceptance mechanism can simulate with no space penalty any reasonable acceptance mechanism based on censuses of configurations. However, the efficiency with which other acceptance mechanisms can simulate nondeterminism remains an open question. This paper uses inductive counting to...
Deterministic and nondeterministic one-way multicounter machines with bounds on the number of zerotests are studied. First, we establish a fine hierarchy of zerotesting bounded deterministic counter machine languages. Second, we show that a nondeterministic two-counter machine with 2 zerotests is able to recognize a language which cannot be accepted by any deterministic sublinear zerotesting bounded...
We consider 2-server algorithms with time complexity O(1) per each request. We show that the previously known algorithm BALANCE2 has competitiveness constant not better than 6, and present another algorithm whose competitiveness constant is 4.
We define atomic semi commutations as being associated to independance relations the form of which is A × B, in which A and B are two disjoint subsets of the alphabet. We prove that semi commutations can be decomposed in weaker semi commutations if and only if they are not atomic. We then deduce that every semi commutation can be obtained by a composition of atomic semi commutations and we suggest...