29669559
Relating Z and First-Order Logic
Despite being widely regarded as a gloss on first-order logic and set theory, Z has not been found to be very supportive of proof. This paper attempts to distinguish between the different philosophies of proof in Z. It discusses some of the issues which must be addressed in creating a proof technology for Z, namely schemas, undefinedness, and what kind of logic to use.
6469757
Teaching Formal Methods in Context
The Software Engineering Programme at Oxford teaches formal methods as an integral part of its programme of professional education in software engineering. This paper explains how the methods are taught—in the context of emerging trends in software development, and in the context of existing practice—and how their use is promoted through course design and motivating examples.
14174107
Lifting in Z
Formal notations such as Z provide powerful support for writing clear specifications, and for undertaking proofs of properties of those specifications. In this paper, we explore one particular style of specification, with applications in control theory and real-time specification. The notation we define permits the accurate description of concepts in these fields without significant overhead or notational clutter. This notation has long been used by practitioners in these fields; we demonstrate that it may be defined within Draft Standard Z, and that the resulting specifications are amenable to proof.
14876206
E-science experiences: software engineering practice and the EU DataGrid
The conduct of collaborative scientific study mediated by the internet -e-science - is giving rise to a new type of large distributed software project. This paper reports initial experiences of one such project: the European DataGrid. We record observations about the intended lifecycle and process, compared with actual practice. The paper explores the applicability of current software development practices from academic, commercial, and open source sectors in the context of such Grid projects.
34718551
Encoding W: A Logic for Z in 2OBJ
A prototype proof system for “\(\mathcal{W}\): A Logic for Z” has been produced using the 2OBJ metalogical theorem-prover. 2OBJ permits an encoding which is very similar in structure to that of \(\mathcal{W}\), and the details are presented here. Like \(\mathcal{W}\)the encoding assumes that all its inputs are well-typed. The structure of the encoding is enhanced by a meta-rule on the lifting of proof rules and tactics. There is some discussion of how tactics can make \(\mathcal{W}\)more easily usable.
265154
A Set-Theoretic Model for Real-Time Specification and Reasoning
Timed-trace formalisms have emerged as a powerful method for specifying and reasoning about concurrent real-time systems. We present a simple variant which builds methodically on set theory, and is thus suitable for use by programmers with little formal methods experience.
145836
Packing Steiner trees: polyhedral investigations
LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightswe, edge capacitiesce,e∈E, and node setT1,…,TN, find edge setsS1,…,SN such that eachSk is a Steiner tree forTk, at mostce of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).
23466253
The CATH Database provides insights into protein structure/function relationships
We report the latest release (version 1.4) of the CATH protein domains database (http://www.biochem.ucl.ac.uk/bsm/cath). This is a hierarchical classification of 13 359 protein domain structures into evolutionary families and structural groupings. We currently identify 827 homologous families in which the proteins have both structual similarity and sequence and/or functional similarity. These can be further clustered into 593 fold groups and 32 distinct architectures. Using our structural classification and associated data on protein functions, stored in the database (EC identifiers, SWISS-PROT keywords and information from the Enzyme database and literature) we have been able to analyse the correlation between the 3D structure and function. More than 96% of folds in the PDB are associated with a single homologous family. However, within the superfolds, three or more different functions are observed. Considering enzyme functions, more than 95% of clearly homologous families exhibit either single or closely related functions, as demonstrated by the EC identifiers of their relatives. Our analysis supports the view that determining structures, for example as part of a 'structural genomics' initiative, will make a major contribution to interpreting genome data.
15221918
Maintaining the Identity of Dynamically Embodied Agents
Virtual agents are traditionally constrained in their embodiment, as they are restricted to one form of body. We propose allowing them to change their embodiment in order to expand their capabilities. This presents users with a number of difficulties in maintaining the identity of the agents, but these can be overcome by using identity cues, certain features that remain constant across embodiment forms. This paper outlines an experiment that examines these identity cues, and shows that they can be used to help address this identity problem.
5379517
Packing Steiner Trees: Further Facets
Abstract In this paper we continue the investigations in [3] for the Steiner tree packing polyhedron. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-definining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic curcuits.
18494896
The steiner tree packing problem in VLSI design
In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.