Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Journals
  3. Mathematical Structures in Computer Science
  4. Volume 19
Journal Home
Refine listing

Refine listing

Access:
Publication date:

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×
< Back to all issues

Volume 19 - June 2009

Contents

Page 3 of 3

Front Cover (OFC, IFC) and matter

  • MSC volume 19 issue 2 Cover and Front matter

  • Published online by Cambridge University Press:
    01 April 2009, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Back Cover (IBC, OBC) and matter

  • MSC volume 19 issue 4 Cover and Back matter

  • Published online by Cambridge University Press:
    01 August 2009, pp. b1-b5
    • Article
      • You have access
    • PDF
    • Export citation

Paper

  • On computably locally compact Hausdorff spaces

  • YATAO XU, TANJA GRUBBA
  • Published online by Cambridge University Press:
    01 February 2009, pp. 101-117

  • Locally compact Hausdorff spaces generalise Euclidean spaces and metric spaces from ‘metric’ to ‘topology’. But does the effectivity on the latter (Brattka and Weihrauch 1999; Weihrauch 2000) still hold for the former? In fact, some results will be totally changed. This paper provides a complete investigation of a specific kind of space – computably locally compact Hausdorff spaces. First we characterise this type of effective space, and then study computability on closed and compact subsets of them. We use the framework of the representation approach, TTE, where continuity and computability on finite and infinite sequences of symbols are defined canonically and transferred to abstract sets by means of notations and representations.

Back Cover (IBC, OBC) and matter

  • MSC volume 19 issue 2 Cover and Back matter

  • Published online by Cambridge University Press:
    01 April 2009, pp. b1-b8
    • Article
      • You have access
    • PDF
    • Export citation

Paper

  • Deciding reachability problems in Turing-complete fragments of Mobile Ambients

  • NADIA BUSI, GIANLUIGI ZAVATTARO
  • Published online by Cambridge University Press:
    04 December 2009, pp. 1223-1263

  • The calculus of Mobile Ambients was proposed by Cardelli and Gordon as a foundational calculus for mobile computing. Since its introduction, the computational strength and the decidability of properties have been investigated for several fragments and variants of the standard calculus. We consider the problem of reachability and characterise a public (that is, restriction-free) fragment for which it is decidable. This fragment is obtained by removing the open capability and restricting the application of the replication operator to guarded processes only. This decidability result may appear surprising in combination with the fact that the same fragment was shown to be Turing complete by Maffeis and Phillips. Finally, we extend our decidability result in two ways: we first prove the decidability of a more general property called target reachability (according to which the target of interest for the reachability analysis consists of a possibly infinite set of processes) and then show that our decidability results also hold for a more general calculus, which includes the sophisticated communication mechanisms of Boxed Ambients, which is the most relevant variant of Mobile Ambients without the open capability.

  • Quantum multiparty communication complexity and circuit lower bounds

  • IORDANIS KERENIDIS
  • Published online by Cambridge University Press:
    01 February 2009, pp. 119-132

  • We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Ω(n/2k), its classical k-party communication is Ω(n/2k/2). Finding such an f would allow us to prove strong classical lower bounds for k ≥ log n players and make progress towards solving a major open question about symmetric circuits.

  • Mobile Petri nets

  • A. ASPERTI, N. BUSI
  • Published online by Cambridge University Press:
    04 December 2009, pp. 1265-1278

  • We add mobility to Place-Transition Petri nets: tokens are names for places, and an input token of a transition can be used in its postset to specify a destination. Mobile Petri nets are then further extended to dynamic nets by adding the possibility of creating new nets during the firing of a transition. In this way, starting from Petri nets, we define a simple hierarchy of nets with increasing degrees of dynamicity. For each class in this hierarchy, we provide its encoding in the former class.

    Our work was largely inspired by the join-calculus of Fournet and Gonthier, which turns out to be a (well-motivated) particular case of dynamic Petri nets. The main difference is that, in the preset of a transition, we allow both non-linear patterns (name unification) and (locally) free names for input places (that is, we remove the locality constraint, and preserve reflexion).

  • Unary automatic graphs: an algorithmic perspective

  • BAKHADYR KHOUSSAINOV, JIAMOU LIU, MIA MINNES
  • Published online by Cambridge University Press:
    01 February 2009, pp. 133-152

  • This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.

Author Index

Paper

Front Cover (OFC, IFC) and matter

  • MSC volume 19 issue 6 Cover and Front matter

  • Published online by Cambridge University Press:
    04 December 2009, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Paper

  • A note on the feasibility of generalised universal composability†

  • ANDREW C. C. YAO, FRANCES F. YAO, YUNLEI ZHAO
  • Published online by Cambridge University Press:
    01 February 2009, pp. 193-205

  • In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.

Back Cover (IBC, OBC) and matter

  • MSC volume 19 issue 6 Cover and Back matter

  • Published online by Cambridge University Press:
    04 December 2009, pp. b1-b7
    • Article
      • You have access
    • PDF
    • Export citation

Paper

Front Cover (OFC, IFC) and matter

  • MSC volume 19 issue 1 Cover and Front matter

  • Published online by Cambridge University Press:
    01 February 2009, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Back Cover (IBC, OBC) and matter

  • MSC volume 19 issue 1 Cover and Back matter

  • Published online by Cambridge University Press:
    01 February 2009, pp. b1-b11
    • Article
      • You have access
    • PDF
    • Export citation

Page 3 of 3