On tape-bounded probabilistic Turing machine acceptors

A probabilistic Turing machine acceptor is a Turing machine acceptor that flips unbiased coins to decide what its next move will be and accepts its input if the probability of reaching a final accepting

is greater than $\text{1}\text{2}$. We show that deterministic and probabilistic tape complexities are polynomially related.     

A hierarchy of deterministic context-free ω-languages

Twenty years ago, Klaus. W. Wagner came up with a hierarchy of ω-regular sets that actually bears his name. It turned out to be exactly the Wadge hierarchy of the sets of ω-words recognized by deterministic finite automata. We describe the Wadge hierarchy of context-free ω-languages, which stands as an extension of Wagner's work from automata to pushdown automata.     

On discrete lower π-strategies

Two-person zero-sum differential games of survival are investigated. It is assumed that player I, as well as player II, can employ during the course of the game any lower π-strategy [2], π(t_i) being a finite partition of [t₀, ∞). The concept of a discrete lower π-strategy is introduced and it is shown that if player I (II) confines himself to the space of discrete lower π-strategies, being a subset of the space of lower π-strategies, then he will be able to force the same lower (upper) value as if he could employ any lower π-strategy. Since we do not use any deep facts about differential games, the results contained here might be extended to continuous games.     

The network complexity and the Turing machine complexity of finite functions

Summary Let L(f) be the network complexity of a Boolean function L(f). For any n-ary Boolean function L(f) let . Hereby p ranges over all relative Turing programs and ranges over all oracles such that given the oracle , the restriction of p to inputs of length n is a program for L(f). p is the number of instructions of p. T _p (n) is the time bound and S _p of the program p relative to the oracle on inputs of length n. Our main results are (1) L(f) O(TC(L(f))), (2) TC(f) O(L(f) ^{2 2+}) for every O.The results of this paper have been reported in a main lecture at the 1975 annual meeting of GAMM, April 2–5, Göttingen     

Recursive Data Types in Algebraically ω-Complete Categories

A category (of data types) is called algebraically ω-complete provided that for each endofunctor T the data-type equation T(X) X has a solution constructed as a colimit of the ω-chain → T() → T²()..., where is the initial data-type. Examples include the categories of (1) countable sets and (total, partial, or nondeterministic) functions, (2) countably dimensional vector spaces and linear functions, (3) countable well-ordered sets and join-preserving functions. In the case of categories enriched over CPO (the category of complete partial orders and strict, continuous functions) a stronger property holds for all locally continuous functors T: the data-type equation is both a limit and a colimit of the finite iterations of T over the initial data-type.     

Polar Type Inference with Intersection Types and ω

We present a type system featuring intersection types and ω, a type constant which is assigned to unused terms. We exploit and extend the technology of expansion variables from the recently developed System I, with which we believe our system shares many interesting properties, such as strong normalization, principal typings, and compositional analysis. Our presentation emphasizes a polarity discipline and shows its benefits. We syntactically distinguish positive and negative types, and give them different interpretations. We take the point of view that the interpretation of a type is intrinsic to it, and should not change implicitly when it appears at the opposite polarity. Our system is the result of a process which started with an extension of Trevor Jim's Polar T ype System.     

On the decidability of fragments of the asynchronous π-calculus

We study the decidability of a reachability problem for various fragments of the asynchronous π-calculus. We consider the combination of three main features: name generation, name mobility, and unbounded control. We show that the combination of name generation with either name mobility or unbounded control leads to an undecidable fragment. On the other hand, we prove that name generation without name mobility and with bounded control is decidable by reduction to the coverability problem for Petri Nets.     

On the Expressive Power of Polyadic Synchronisation in π-calculus

We extend the π-calculus with polyadic synchronisation, a generalisation of the communication mechanism which allows channel names to be composite. We show that this operator embeds nicely in the theory of π-calculus, and makes it possible to derive divergence-free encodings of distributed calculi. We give a separation result between the π-calculus with polyadic synchronisation (^eπ) and the original calculus, in the style of an analogous result given by Palamidessi for mixed choice. We encode Local Area π showing how to control the local use of resources in ^eπ.     

σ-Automata and Chebyshev-polynomials

A σ-automaton is an additive, binary cellular automaton on a graph. For product graphs such as a grids and cylinders, reversibility and periodicity properties of the corresponding σ-automaton can be expressed in terms of a binary version of Chebyshev polynomials. We will give a detailed analysis of the divisibility properties of these polynomials and apply our results to the study of σ-automata.     

On the ω-language Expressive Power of Extended Petri Nets

In this paper, we study the expressive power of several monotonic extensions of Petri nets. We compare the expressive power of Petri nets, Petri nets extended with non-blocking arcs and Petri nets extended with transfer arcs, in terms of ω-languages. We show that the hierarchy of expressive powers of those models is strict. To prove these results, we propose original techniques that rely on well-quasi orderings and monotonicity properties.     

Objects in the π-Calculus

Two semantics for a parallel object-oriented programming language are presented. One is a two-level transitional semantics in which the global behaviour of a system is derived directly from the possible actions of its constituent objects. The other is by translation into the π-calculus. A close correspondence between the semantics is established.     

Strong normalisation in the π-calculus

We introduce a typed π-calculus where strong normalisation is ensured by typability. Strong normalisation is a useful property in many computational contexts, including distributed systems. In spite of its simplicity, our type discipline captures a wide class of converging name-passing interactive behaviour. The proof of strong normalisability combines methods from typed λ-calculi and linear logic with process-theoretic reasoning. It is adaptable to systems involving state, non-determinism, polymorphism, control and other extensions. Strong normalisation is shown to have significant consequences, including finite axiomatisation of weak bisimilarity, a fully abstract embedding of the simply typed λ-calculus with products and sums and basic liveness in interaction. Strong normalisability has been extensively studied as a fundamental property in functional calculi, term rewriting and logical systems. This work is one of the first steps to extend theories and proof methods for strong normalisability to the context of name-passing processes.     

The complexity of small universal Turing machines: A survey

We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example, it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. As a related result, we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also review a large number of old and new universal program size results, including new small universal Turing machines and new weakly, and semi-weakly, universal Turing machines. We then discuss some ideas for future work arising out of these, and other, results.     

Turing complexity of Behncke-LeptinC *-algebras with a two-point dual

We prove that the combinatorial complexity of theC ^*-algebras mentioned in the title is polynomial. We use our interpretation of AFC ^*-algebras as theories in the infinite-valued calculus of Lukasiewicz.     

Complete solution of the 4‐block H∞ control problem with infinite and finite jω‐axis zeros

This paper discusses the 4‐block H^∞ control problem with infinite and finite jω‐axis invariant zeros in the state‐space realizations of the transfer functions from the control input to the controlled output and from the disturbance input to the measurement output, where these realizations are induced from a stabilizable and detectable realization of the generalized plant. This paper extends the DGKF approach to the H^∞ control problem but permitting infinite and finite jω‐axis invariant zeros by using the eigenstructures related to these zeros. Necessary and sufficient conditions are presented for checking solvability through checking the stabilizing solutions of two reduced‐order Riccati equations and examining matrix norm conditions related to the jω‐axis zeros. The parameterization of all suitable controllers is given in terms of a linear fractional transformation involving a certain fixed transfer function matrix and together with a stable transfer function matrix with gain less than 1 which is free apart from satisfying certain interpolation conditions. Copyright © 2000 John Wiley & Sons, Ltd.     

Improving the robustness of Nussbaum-type regulators by the use of σ-modification — local results

The bursting phenomenon in a Nussbaum-type regulator is discussed. Its cause is associated with some properties of the equilibrium manifold. A σ-modification factor is introduced, and the resulting equilibrium set is completely characterized using linearization techniques. Local robustness against bounded disturbances is proved by Malkin's Theorem, and verified by simulation.