Randomized function evaluation on a ring

LetR be a unidirectional asynchronous ring ofn identical processors each with a single input bit. Letf be any cyclic nonconstant function ofn boolean variables. Moran and Warmuth (1986) prove that anydeterministic algorithm that evaluatesf onR has communication complexity (n logn) bits. They also construct a family of cyclic nonconstant boolean functions that can be evaluated inO(n logn) bits by a deterministic algorithm.This contrasts with the following new results:

On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

Quantifier-free logic for nondeterministic theories

We develop a quantifier-free logic for deriving consequences of multialgebraic theories. Multialgebras are used as models for nondeterminism in the context of algebraic specifications. They are many sorted algebras with set-valued operations. Formulae are sequents over atoms allowing one to state set-inclusion or identity of 1-element sets (determinacy). We introduce a sound and weakly complete Rasiowa–Sikorski (R–S) logic for proving multialgebraic tautologies. We then extend this system for proving consequences of specifications based on translation of finite theories into logical formulae. Finally, we show how such a translation may be avoided—introduction of the specific cut rules leads to a sound and strongly complete Gentzen system for proving directly consequences of specifications. Besides giving examples of the general techniques of R–S and the specific cut rules, we improve the earlier logics for multialgebras by providing means to handle empty carriers (as well as empty result-sets) without the use of quantifiers, and to derive consequences of theories without translation into another format and without using general cut.     

Molecular Computing, Bounded Nondeterminism, and Efficient Recursion

The maximum number of strands used is an important measure of a molecular algorithm's complexity. This measure is also called the volume used by the algorithm. Every problem that can be solved by an NP Turing machine with b(n) binary nondeterministic choices can be solved by molecular computation in a polynomial number of steps, with four test tubes, in volume 2 ^b(n) . We identify a large class of recursive algorithms that can be implemented using bounded nondeterminism. This yields improved molecular algorithms for important problems like 3-SAT, independent set, and 3-colorability. Received May 5, 1997; revised March 24, 1998.     

Refinement-oriented probability for CSP

Jones and Plotkin give a general construction for forming a probabilistic powerdomain over any directed-complete partial order [Jon90, JoP89]. We apply their technique to the failures/divergences semantic model for Communicating Sequential Processes [Hoa85].The resulting probabilistic model supports a new binary operator, probabilistic choice, and retains all operators of CSP including its two existing forms of choice. An advantage of using the general construction is that it is easy to see which CSP identities remain true in the probabilistic model. A surprising consequence however is that probabilistic choice distributes through all other operators; such algebraic mobility means that the syntactic position of the choice operator gives little information about when the choice actually must occur. That in turn leads to some interesting interaction between probability and nondeterminism.A simple communications protocol is used to illustrate the probabilistic algebra, and several suggestions are made for accommodating and controlling nondeterminism when probability is present.All authors are members of the Programming Research Group; McIver and Seidel are supported by the EPSRC.0     

Two implementation relations and the correctness of communicating replicated processes

This paper studies the correctness of distributed systems made up of replicated processes that communicate by message passing. Processes are described within the divergence model of CSP. The notion of correctness introduced is based on a relation that formally expresses the conformance of an implementation process with the target process it is intended to implement. A weak and a strong version of the relation are introduced, aimed at treating acyclic and cyclic process networks respectively. Both allow the study of (total) correctness and may cope with non-deterministic targets and implementations.We then show how a target process may be implemented (in the formal sense introduced) by replicating it in a set of copies, a majority of which is non-faulty.     

Non-determinism and weak constraints in Datalog

This paper introduces a simple and powerful extension of stratified DATALOG which permits to express various DB-complexity classes. The new language, called DATALOG^¬s,c,p , extends DATALOG with stratified negation, a non-deterministic construct, calledchoice, and a weak form of constraints, calledpreference rules, that is, constraints that should be respected but, if they cannot be eventually enforced, they only invalidate the portions of the program which they are concerned with. Although DATALOG with stratified negation is not able to express all polynomial time queries,²⁰⁾ the introduction of the non-deterministic constructchoice permits to express, exactly, the ‘deterministic fragment’ of the class of DB-queriesP, under the non-deterministic semantics,NP, under the possible semantics, and coNP, under the certain semantics. The introduction of preference rules, further increases the expressive power of the language, and permits to express the complexity classes Σ ₂ ^p , under the possibility semantics, and Π ₂ ^p , under the certainty semantics.     

A Nondeterministic Extension over Finitely Recursive Process Model

This paper extends the Finitely Recursive Process framework introduced by Inan and Varaiya for modelling Discrete Event Systems to encompass nondeterministic processes. Nondeterminism has been captured as a set of possible deterministic futures instead of using the standard failure model of Communicating Sequential Processes. In the beginning a general structure of finitely recursive process space is provided with some important modifications. Next, the nondeterministic process space has been introduced as a special case of the general algebraic process space. A collection of operators has been defined over this nondeterministic process space that enables its characterisation in a finitely recursive manner. Finally, the advantages and disadvantages of the proposed model vis-a-vis other nondeterministic models of discrete event systems are discussed.     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007