Suspension Terms as a Means for Meta-coordination in the μLog Coordination Framework

In this paper we introduce the concept of suspension terms as a reification of the suspension of coordination operations in the Log framework. Each time a coordination operation suspends, a corresponding suspension term is created. By creating primitives that can manipulate the suspension terms, we are able to introduce coordination primitives at the meta-level (e.g., dealing with success, failure, suspension). This is called meta-coordination. In this paper, we introduce the new primitives, give a formal definition of their basic semantics, and argue their expressiveness. The paper is concluded with an argumentation why first order suspension terms suffice and how higher order suspension terms can be replaced by lower order suspension terms.     

A computer checked algebraic verification of a distributed summation algorithm

We present an algebraic verification of Segalls propagation of information with feedback algorithm and we report on the verification of the proof using the PVS system. This algorithm serves as a nice benchmark for verification exercises (see [2, 8, 17]). The verification is based on the methodology presented in [7] and demonstrates its suitability to deliver mechanically verifiable correctness proofs of highly nondeterministic distributed algorithms.The research of the second author was supported by Human Capital Mobility (HCM). The research of the third author was supported by the Netherlands Organization for Scientific Research (NWO) under contract SION 612-33-006.Received October 1988 by J. RushbyRevised July 2004Accepted September 2004 by C. B. Jones     

Compositional checking of satisfaction

We present a compositional method for deciding whether a process satisfies an assertion. Assertions are formulas in a modal -calculus, and processes are drawn from a very general process algebra inspired by CCS and CSP. Well-known operators from CCS, CSP, and other process algebras appear as derived operators. The method iscompositional in the structure of processes and works purely on the syntax of processes. It consists of applying a sequence ofreductions, each of which only takes into account the top-level operator of the process. A reduction transforms a satisfaction problem for a composite process into equivalent satisfaction problems for the immediate subcomponents. Using process variables, systems with underfined subcomponents can be defined, and given an overall requirement to the system,necessary and sufficient conditions on these subcomponents can be found. Hence the process variables make it possible to specify and reason about what are often referred to ascontexts, environments, andpartial implementations. Since reductions are algorithms that work on syntax, they can be considered as forming a bridge between traditional noncompositional model checking and compositional proof systems.     

Verifying programs in the calculus of inductive constructions

This paper deals with a particular approach to the verification of functional programs. A specification of a program can be represented by a logical formula [Con86, NPS90]. In a constructive framework, developing a program then corresponds to proving this formula. Given a specification and a program, we focus on reconstructing a proof of the specification whose algorithmic contents corresponds to the given program. The best we can hope is to generate proof obligations on atomic parts of the program corresponding to logical properties to be verified. First, this paper studies a weak extraction of a program from a proof that keeps track of intermediate specifications. From such a program, we prove the determinism of retrieving proof obligations. Then, heuristic methods are proposed for retrieving the proof from a natural program containing only partial annotations. Finally, the implementation of this method as a tactic of theCoq proof assistant is presented.This research was partly supported by ESPRIT Basic Research Action Types for Proofs and Programs and by Programme de Recherche Coordonnes and CNRS Groupement de Recherche Programmation.     

AI & Society and society

This article looks at the broadest implications of public acceptance of AI. A distinction is drawn between conscious belief in a technology, and organic belief where the technology is incorporated into an unconscious world model. The extent to which we feel threatened by AI's apparent denial of spirit is considered, along with a discussion of how people react to this threat. It is proposed that organic acceptance of AI models would lead to a rebirth of popular spiritual concepts as paradoxical as the New Age ideas that have their roots in the theories of physics. Finally the relevance of this speculation is discussed in terms of how it could impinge upon public acceptability of AI technology.     

Electro-osmotically controllable multi-flow microreactor

An adjustable diffusion-based microfluidic reactor is presented here, which is based on electro-osmotic guiding of reagent samples. The device consists of a laminar flow chamber with two separate reagent inlets. The position and the width of the two sample streams in the flow chamber can be controlled individually by changing the flow ratio of three parallel guiding buffer streams. Since electro-osmotic flow (EOF) is used for pumping, no external pumps or other moving parts are needed. The region where the diffusive profiles of the two sample streams overlap is used for the reactions. This overlapping region can be manipulated in a predictable way by adjusting the voltages required to generate the respective electro-osmotic flow. Reaction dynamics inside the microreactor is illustrated with a reactant pair of a fluorescent calcium tracer and a calcium chloride solution. An analytical model, which is an analogue of electrical circuits to EOF, was developed and embedded into the LabView control software, allowing real-time control of the microreactor. This paper describes the simulation, fabrication and experimental characterisation of the device.     

A Probabilistic Framework for SVM Regression and Error Bar Estimation

In this paper, we elaborate on the well-known relationship between Gaussian Processes (GP) and Support Vector Machines (SVM) under some convex assumptions for the loss functions. This paper concentrates on the derivation of the evidence and error bar approximation for regression problems. An error bar formula is derived based on the -insensitive loss function.     

Computable processes and bisimulation equivalence

A process is calledcomputable if it can be modelled by a transition system that has a recursive structure—implying finite branching. The equivalence relation between transition systems considered is strong bisimulation equivalence. The transition systems studied in this paper can be associated to processes specified in common specification languages such as CCS, LOTOS, ACP and PSF. As a means for defining transition systems up to bisimulation equivalence, the specification languageCRL is used. Two simple fragments of,CRL are singled out, yielding universal expressivity with respect to recursive and primitive recursive transition systems. For both these domains the following properties are classified in the arithmetical hierarchy:bisimilarity, perpetuity (both ₁ ⁰ ),regularity (having a bisimilar, finite representation, ₂ ⁰ ),acyclic regularity ( ₁ ⁰ ), anddeadlock freedom (distinguishing deadlock from successful termination, ₁ ⁰ ). Finally, it is shown that in the domain of primitive recursive transition systems over a fixed, finite label set, a genuine hierarchy in bisimilarity can be defined by the complexity of the witnessing relations, which extends r.e. bisimilarity. Hence, primitive recursive transition systems already form an interesting class.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

Reasoning about programs in continuation-passing style

Plotkin's _v -calculus for call-by-value programs is weaker than the -calculus for the same programs in continuation-passing style (CPS). To identify the call-by-value axioms that correspond to on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformation, we determine the precise language of CPS terms closed under -transformations, as well as the call-by-value axioms that correspond to the so-called administrative -reductions on CPS terms. Using the inverse mapping, we map the remaining and equalities on CPS terms to axioms on call-by-value terms. On the pure (constant free) set of -terms, the resulting set of axioms is equivalent to Moggi's computational -calculus. If the call-by-value language includes the control operatorsabort andcall-with-current-continuation, the axioms are equivalent to an extension of Felleisenet al.'s _v -C-calculus and to the equational subtheory of Talcott's logic IOCC.This article is a revised and extended version of the conference paper with the same title [42]. The technical report of the same title contains additional material.The authors were supported in part by NSF grant CCR 89-17022 and by Texas ATP grant 91-003604014.     

On the Relationship Between BDI Logics and Standard Logics of Concurrency

The behavior of an agent is mainly governed by the specific way in which it handles the rational balance between information and deliberation. Rao and Georgeff's BDI theory is most popular among the formalisms capturing this very balance. This formalism has been proposed as a language for specifying agents in an abstract manner or, alternatively, for verifying various properties of agents implemented in some other programming language. In mainstream computer science, there are formalisms designed for a purpose similar to the BDI theory; not specifically aiming at agents, but at concurrency in general. These formalisms are known as logics of concurrent programs. In this paper these two frameworks are compared with each other for the first time. The result shows that the basic BDI theory, BDI_CTL*, can be captured within a standard logic of concurrency. The logic which is relevant here is Kozen's propositional -calculus. -calculus turns out to be even strictly stronger in expressive power than BDI_CTL* while enjoying a computational complexity which is not higher than that of BD_CTL*'s small fragment CTL. This correspondence puts us in a position to provide the first axiomatization of Rao and Georgeff's full theory. Immediate consequences for the computational complexity of BDI theory are also explored, both for theorem proving and model checking.     

Multimedia teleorchestra with independent sources: Part 1 — temporal modeling of collaborative multimedia scenarios

Multimedia synchronization involving independent sources is a challenging issue imposed by the distributed multimedia applications. In our work, this issue is studied by investigating the teleorchestra application (remote multimedia presentation). In teleorchestration, among the data objects to be presented, relative and uncertain temporal requirements may be involved. Fuzzy presentation scenarios are thus generated. In this paper, we describe a temporal model that can handle these fuzzy scenarios that contain imprecise synchronization constraints, such as unknown object presentation durations and relative event occurring times. The model supports a distributed synchronization algorithm that can schedule the independent sources for the multimedia teleorchestration.     

Continuous-time time-varying entropy

In this paper we present a definition for the entropy for time-varying continuous-time systems. This entropy differs significantly from the entropy for discrete-time systems, which is defined as the memoryless component of the spectral factor of an operator related to the system. Properties of this entropy are discussed, the relationships with ₂ and , as well as the relationship with the discrete-time entropy.The work of P. A. Iglesias was supported in part by the National Science Foundation, under Contract ECS-9309387.     

A Typology of Translation Problems for Eurotra Translation Machines

This paper presents a detailed study of Eurotra Machine Translation engines, namely the mainstream Eurotra software known as the E-Framework, and two unofficial spin-offs – the C,A,T and Relaxed Compositionality translator notations – with regard to how these systems handle hard cases, and in particular their ability to handle combinations of such problems. In the C,A,T translator notation, some cases of complex transfer are wild, meaning roughly that they interact badly when presented with other complex cases in the same sentence. The effect of this is that each combination of a wild case and another complex case needs ad hoc treatment. The E-Framework is the same as the C,A,T notation in this respect. In general, the E-Framework is equivalent to the C,A,T notation for the task of transfer. The Relaxed Compositionality translator notation is able to handle each wild case (bar one exception) with a single rule even where it appears in the same sentence as other complex cases.     

Understanding Computer-based “Informated” Environments

The paper introduces the concept of Computer-based Informated Environments (CBIEs) to indicate an emergent form of work organisation facilitated by information technology. It first addresses the problem of inconsistent meanings of the informate concept in the literature, and it then focuses on those cases which, it is believed, show conditions of plausible informated environments. Finally, the paper looks at those factors that when found together contribute to building a CBIE. It makes reference to CBIEs as workplaces that comprise a non-technocentric perspective and questions whether CBIEs truly represent an anthropocentric route of information technology.     

From Pre-Historic to Post-Modern Symbolic Model Checking

Symbolic model checking, which enables the automatic verification of large systems, proceeds by calculating expressions that represent state sets. Traditionally, symbolic model-checking tools are based on backward state traversal; their basic operation is the function pre, which, given a set of states, returns the set of all predecessor states. This is because specifiers usually employ formalisms with future-time modalities, which are naturally evaluated by iterating applications of pre. It has been shown experimentally that symbolic model checking can perform significantly better if it is based, instead, on forward state traversal; in this case, the basic operation is the function post, which, given a set of states, returns the set of all successor states. This is because forward state traversal can ensure that only parts of the state space that are reachable from an initial state and relevant for the satisfaction or violation of the specification are explored; that is, errors can be detected as soon as possible.In this paper, we investigate which specifications can be checked by symbolic forward state traversal. We formulate the problems of symbolic backward and forward model checking by means of two -calculi. The pre- calculus is based on the pre operation, and the post- calculus is based on the post operation. These two -calculi induce query logics, which augment fixpoint expressions with a boolean emptiness query. Using query logics, we are able to relate and compare the symbolic backward and forward approaches. In particular, we prove that all -regular (linear-time) specifications can be expressed as post- queries, and therefore checked using symbolic forward state traversal. On the other hand, we show that there are simple branching-time specifications that cannot be checked in this way.     

Knowledge discovery and system-user partnership: On a production “adversarial partnership” approach

We examine the relationship between systems and their users from the knowledge discovery perspective. Recently knowledge discovery in databases has made important progress, but it may also bring some potential problems to database design, such as issues related to database security, because an unauthorised user may derive highly sensitive knowledge from unclassified data. In this paper we point out that there is a need for a comprehensive study on knowledge discovery in human-computer symbiosis. Borrowing terms from algorithm design and artificial intelligence literature, we propose a notion called database-user adversarial partnership. We point out that this notion is general enough to cover various knowledge discovery and security of issues related to databases and their users. Furthermore, we point out the notion of database-user adversarial partnership can be further generalised into system-user adversarial partnership. Opportunities provided by knowledge discovery techniques and potential social implications are also discussed.     

The Claremont Shakespeare Authorship Clinic: How Severe Are the Problems?

Ward Elliott (from 1987) and Robert Valenza (from 1989) set out to the find the true Shakespeare from among 37 anti-Stratfordian Claimants. As directors of the Claremont Shakespeare Authorship Clinic, Elliott and Valenza developed novel attributional tests, from which they concluded that most Claimants are not-Shakespeare. From 1990-4, Elliott and Valenza developed tests purporting further to reject much of the Shakespeare canon as not-Shakespeare (1996a). Foster (1996b) details extensive and persistent flaws in the Clinic's work: data were collected haphazardly; canonical and comparative text-samples were chronologically mismatched; procedural controls for genre, stanzaic structure, and date were lacking. Elliott and Valenza counter by estimating maximum erosion of the Clinic's findings to include five of our 54 tests, which can amount, at most, to half of one percent (1998). This essay provides a brief history, showing why the Clinic foundered. Examining several of the Clinic's representative tests, I evaluate claims that Elliott and Valenza continue to make for their methodology. A final section addresses doubts about accuracy, validity and replicability that have dogged the Clinic's work from the outset.     

A Mathematical Analysis of Pānini’s <Emphasis Type="Italic">Śivasūtras</Emphasis>

In Pninis grammar of Sanskrit one finds the ivastras, a table which defines the natural classes of phonological segments in Sanskrit by intervals. We present a formal argument which shows that, using his representation method, Pninis way of ordering the phonological segments to represent the natural classes is optimal. The argument is based on a strictly set-theoretical point of view depending only on the set of natural classes and does not explicitly take into account the phonological features of the segments, which are, however, implicitly given in the way a language clusters its phonological inventory. The key idea is to link the graph of the Hasse-diagram of the set of natural classes closed under intersection to ivastra-style representations of the classes. Moreover, the argument is so general that it allows one to decide for each set of sets whether it can be represented with Pninis method. Actually, Pnini had to modify the set of natural classes to define it by the ivastras (the segment h plays a special role). We show that this modification was necessary and, in fact, the best possible modification. We discuss how every set of classes can be modified in such a way that it can be defined in a ivastra-style representation.¹