International Journal of Foundations of Computer Science

We show that rigid reachability, the non-symmetric form of rigid E-unification, is already undecidable in the case of a single constraint. From this we infer the undecidability of a new and rather restricted kind of second-order unification. We also show that certain decidable subclasses of the problem which are -complete in the equational case become EXPTIME-complete when symmetry is absent. By applying automata-theoretic methods, simultaneous monadic rigid reachability with ground rules is shown to be PSPACE-complete. Moreover, we identify two decidable non-monadic fragments that are complete for EXPTIME.

We present a constraint system, OF, of feature trees that is appropriate to specify and implement type inference for first-class messages. OF extends traditional systems of feature constraints by a selection constraint x <y> z, "by first-class feature tree" y, which is in contrast to the standard selection constraint x[f]y, "by fixed feature" f. We investigate the satisfiability problem of OF and show that it can be solved in polynomial time, and even in quadratic time if the number of features is bounded. We compare OF with Treinen's system EF of feature constraints with first-class features, which has an NP-complete satisfiability problem. This comparison yields that the satisfiability problem for OF with negation is NP-hard. Further we obtain NP-completeness, for a specific subclass of OF with negation that is useful for a related type inference problem. Based on OF we give a simple account of type inference for first-class messages in the spirit of Nishimura's recent proposal, and we show that it has polynomial time complexity: We also highlight an immediate extension of this type system that appears to be desirable but makes type inference NP-complete.

This paper develops an ML-style programming language with first-class contexts i.e. expressions with holes. The crucial operation for contexts is hole-filling. Filling a hole with an expression has the effect of dynamic binding or macro expansion which provides the advanced feature of manipulating open program fragments. Such mechanisms are useful in many systems including distributed/mobile programming and program modules. If we can treat a context as a first-class citizen in a programming language, then we can manipulate open program fragments in a flexible and seamless manner. A possibility of such a programming language was shown by the theory of simply typed context calculus developed by Hashimoto and Ohori. This paper extends the simply typed system of the context calculus to an ML-style polymorphic type system, and gives an operational semantics and a sound and complete type inference algorithm.

We establish the Curry-Howard isomorphism between constructive classical logic and -calculus. -calculus exactly means the target language of Continuation Passing Style (CPS) transforms. Constructive classical logic we refer to are LKT and LKQ introduced by Danos et al.(1993).

This work is about an experimental paradigmatic functional language for programming with P-TIME functions. The language is designed from Intuitionistic Light Affine Logic. It can be typed automatically by a type inference algorithm that deduces polymorphic types à la ML.

In this paper, we explore the isomorphism between vector time and causality to characterize consistency of a set of checkpoints in a distributed computing. A necessary and sufficient condition, to determine if a set of local checkpoints can form a consistent global checkpoint, is presented and proved using the isomorphic power of vector time and causality. To the best of our knowledge, this is the first attempt to use the isomorphism for this purpose. This condition leads to a simple and straightforward algorithm for a guaranteed mutually consistent global checkpointing. In our approach, a process can take a checkpoint whenever and wherever it wants while other related process may be asked to take an additional checkpoint for ensuring the mutual consistency. We also show how this condition and the resulting algorithm can be used to obtain a maximum and minimum global checkpoints, another important paradigm for distributed applications.

Membrane Computing is a recently introduced area of Molecular Computing, where a computation takes place in a membrane structure where multisets of objects evolve according to given rules (they can also pass through membranes). The obtained computing models were called P systems. In basic variants of P systems, the use of objects evolution rules is regulated by a given priority relation; moreover, each membrane has a label and one can send objects to precise membranes, identified by their labels. We propose here a variant where we get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an "electrical charge" and the objects are passed through membranes according to their charge. We prove that such systems are able to characterize the one-letter recursively enumerable languages (equivalently, the recursively enumerable sets of natural numbers), providing that an extra feature is considered: the membranes can be made thicker or thinner (also dissolved) and the communication through a membrane is possible only when its thickness is equal to 1. Several open problems are formulated.

We derive efficient guidelines for scheduling data-parallel computations within a draconian mode of cycle-stealing in networks of workstations. In this computing regimen, (the owner of) workstation A contracts with (the owner of) workstation B to take control of B's processor for a guaranteed total of U time units, punctuated by up to some prespecified number p of interrupts which kill any work A has in progress on B. On the one hand, the high overhead — of c time units — for setting up the communications that supply workstation B with work and receive its results recommends that A communicate with B infrequently, supplying B with large amounts of work each time. On the other hand, the risk of losing work in progress when workstation B is interrupted recommends that A supply B with a long sequence of small bundles of work. In this paper, we derive two sets of scheduling guidelines that balance these conflicting pressures in a way that optimizes, up to low-order additive terms, the amount of work that A is guaranteed to accomplish during the cycle-stealing opportunity. Our non-adaptive guidelines, which employ a single fixed strategy until all p interrupts have occurred, produce schedules that achieve at least units of work. Our adaptive guidelines, which change strategy after each interrupt, produce schedules that achieve at least (low-order terms) units of work. By deriving the theoretical underpinnings of our guidelines, we show that our non-adaptive schedules are optimal in guaranteed work-output and that our adaptive schedules are within low-order additive terms of being optimal.