Abstracts of invited talks

• Matthew Hennessy

  Axiomatising Asynchronous Process Languages

  Most semantic theories for process languages developed in recent years presuppose that communication is synchronous; the sending and receiving processes must rendezvous for the communication to occur. Asynchronous communication is when the sender is not blocked but may transmit a message even in the absence of a waiting receiver. This communication paradigm is much easier to implement and consequently has been adopted by numerous recently developed process languages.

  

  Top

• Marek Karpinski

  Randomized Complexity of Linear Arrangements

  We present some recent results on the complexity of computing linear arrangements and convex polyhedra by randomized algebraic decision trees. Among other things, these results give the first randomized lower bounds on the problems like Knapsack, Element Distinctness, and bounded Integer Programming.

  

  Top

• Ugo Montanari

  Tile Transition Systems as Coalgebras
  (joint paper with Andrea Corradini and Reiko Heckel)

  Tile systems have been studied by the last coauthor and several collaborators as general, compositional models of computation for concurrent, distributed, and reactive systems. Tiles are much like SOS inference rules, but they can be composed horizontally and vertically to build larger proof steps. They generalize Kim Larsen and Liu Xinxin context systems, since they allow for more general rule formats. The tile model also extends rewriting logic by Jose' Meseguer (in the nonconditional case), since it takes into account rewritings with side effects and rewriting synchronization, and it can be naturally equipped with congruences and observational equivalences based on bisimilarity.

  Coalgebras are a natural setting where to study transition systems with bisimilarity, especially when a minimal realization does exist. In the paper we show that, by actually forgetting part of the structure, it is possible to associate a coalgebra to every tile system such that both bisimilarities coincide. If we want to preserve the tile structure completely, we can consider a particular class of tile systems enjoying the so-called decomposition property: any transition of a system having a subsystem, can be decomposed into a transition of the subsystem and a transition of the rest of the system. We show that these tile systems can be mapped into coalgebras defined on a category of algebras (rather than on Set), or alternatively to the bialgebra setting of Turi and Plotkin. This understanding of decomposable tile systems is conceptually satisfactory, since the coexistence of the algebraic and the coalgebraic structure guarantees interesting properties, like for instance that bisimilarity is a congruence.

  

  Top

• Arto Salomaa

  Caesar and DNA. Views on cryptology

  The paper discusses some recent aspects of cryptology. Attention is focused on public-key cryptography, in particular, on certain zero-knowledge proofs and the general question of whether and how cryptographic ideas can be realized without computers. Possible impacts of DNA computing on cryptology, as well as recent legislative measures to restrict the marketing of cryptographic products, will also be briefly considered.

  

  Top

• Boris Trakhtenbrot

  Dynamic systems and their interaction: Definitional Suggestions

  Recent research in reactive and hybrid systems is dominated by a plethora of Concepts/Terminology/Notation. Unfortunately, this background is not free of ad-hoc and ambiguous decisions which are liable to misjudgements and to the infliction of myths into the area. Some authors seek a remedy in very abstract theories, especially in category theory. However, for most members of the community this seems too much of a burden when compared to the expected payoff. Hence, the need to have a coherent conceptual/notational setting for many of the facts already known, at a more intuitive and intelligible level. We take the risk of facing this challenge, deliberately omitting some subtleties which are not critical to the enterprise as a whole. Such omissions are partially compensated for by examples, and historical/methodological digressions. Here are four specific principles which characterize our approach:

  • Continuous Time.
    The shift to continuous time brings to light circumstances that are not visible at discrete time. We pursue them in a `digital-logical" framework, postponing (or completely ignoring) incursions into classical calculus.
  • Paradigms of Interaction.
    Interaction in hybrids is embodied essentially in the synchronous composition of components which do not share variables.
  • Nondeterminism.
    Nondeterminism is a useful mathematical abstraction but still beyond the basic paradigm.
  • Input/Output.
    Functions are more basic than sets. Correspondingly, input/output devices (transducers) are more fundamental than acceptors. Transducers interact in the framework of circuits, i.e. networks subjected to input/output discipline.

  According to these principles we expound our definitional suggestions. We illustrate them with respect to the current literature on the subject, where they are sometimes obscured by a premature mixture of semantics, syntax and pragmatics. One may argue that something essential is still missing, and the right time did not yet come for ultimate CTN-decisions. This argument doesn't seem to revoke the challenge to release the existing CTN, from the shortcomings mentioned above.

  

  Top