The Elo system for rating chess players, also used in other games and sports, was adopted by the World Chess Federation over four decades ago. Although not without controversy, it is accepted as generally reliable and provides a method for assessing players' strengths and ranking them in official tournaments. It is generally accepted that the distribution of players' rating data is approximately normal but, to date, no stochastic model of how the distribution might have arisen has been proposed. We propose such an evolutionary stochastic model, which models the arrival of players into the rating pool, the games they play against each other, and how the results of these games affect their ratings, in a similar manner to the Elo system. Using a continuous approximation to the discrete model, we derive the distribution for players' ratings at timetas a normal distribution, where the variance increases in time as a logarithmic function oft. We validate the model using published rating data from 2007-2010, showing that the parameters obtained from the data can be recovered through simulations of the stochastic model. The distribution of players' ratings is only approximately normal and has been shown to have a small negative skew. We show how to modify our evolutionary stochastic model to take this skewness into account, and we validate the modified model using the published official rating data.

The mechanics of seventy-two different Java refactorings are described fully in Fowler's text. In the same text, Fowler describes seven categories of refactoring, into which each of the seventy-two refactorings can be placed. A current research problem in the refactoring and XP community is assessing the likely time and testing effort for each refactoring, since any single refactoring may use any number of other refactorings as part of its mechanics and, in turn, can be used by many other refactorings. In this paper, we draw on a dependency analysis carried out as part of our research in which we identify the 'Use' and 'Used By' relationships of refactorings in all seven categories. We offer reasons why refactorings in the 'Dealing with Generalisation' category seem to embrace two distinct refactoring sub-categories and how refactorings in the 'Moving Features between Objects' category also exhibit specific characteristics. In a wider sense, our meta-analysis provides a developer with concrete guidelines on which refactorings, due to their explicit dependencies, will prove problematic from an effort and testing perspective.

Protein families can be used to reconstruct evolutionary histories of organisms. The accuracy of protein assignment to such families is critical for the success of such studies. Here we investigate the automatic aggregation of motif-defined homologous protein families for further reconstruction of their evolutionary histories. We propose a method that utilises only parameters that can be adjusted by using the data. The building blocks of the method include: (a) a majority rule for combining protein homologous neighbourhood lists into that for a family, and (b) a robust clustering procedure whose only parameter, the similarity shift, can be estimated from information on proteins with known function. The method is applied to a herpesvirus protein dataset leading to insights into the composition of ancestors of herpesvirus superfamilies. Comparison of the computational reconstructions with more comprehensive analyses also show how alignment-based between-protein similarity scoring can be improved by using data on gene arrangements.

Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other networks that give rise to power-law distributions. These models are based on the notion of preferential attachment, leading to the “rich get richer” phenomenon. We present a generalization of the basic model by allowing deletion of individual links and show that it also gives rise to a power-law distribution. We derive the mean-field equations for this stochastic model and show that, by examining a snapshot of the distribution at the steady state of the model, we are able to determine the extent to which link deletion has taken place and estimate the probability of deleting a link. Applying our model to actual Web graph data provides evidence of the extent to which link deletion has occurred. We also discuss a problem that frequently arises in estimating the power-law exponent from empirical data and a few possible methods for dealing with this, indicating our preferred approach. Using this approach our analysis of the data suggests a power-law exponent of approximately 2.15 for the distribution of inlinks in the Web graph, rather than the widely published value of 2.1.

We introduce the concept of administrative scope in a role hierarchy and demonstrate that it can be used as a basis for role-based administration. We then develop a family of models for role hierarchy administration (RHA) employing administrative scope as the central concept. We then extend RHA 4 , the most complex model in the family, to a complete, decentralized model for role-based administration. We show that SARBAC, the resulting role-based administrative model, has significant practical and theoretical advantages over ARBAC97. We also discuss how administrative scope might be applied to the administration of general hierarchical structures, how our model can be used to reduce inheritance in the role hierarchy, and how it can be configured to support discretionary access control features.

The effectiveness of an access control mechanism in implementing a security policy in a centralized operating system is often weakened because of the large number of possible access rights involved, informal specification of security policy and a lack of tools for assisting systems administrators. Herein we present a logical foundation for automated tools that assist in determining which access rights should be granted by reasoning about the effects of an access control mechanism on the computations performed by an operating system. We demonstrate the practicality and utility of our logical approach by showing how it allows us to construct a deductive database capable of answering questions about the security of two real-world operating systems. We illustrate the application of our techniques by presenting the results of an experiment designed to assess how accurately the configuration of an access control mechanism implements a given security policy.

The effectiveness of an access control mechanism in implementing a security policy in a centralized operating system is often weakened because of the large number of possible access rights involved, informal specification of security policy and a lack of tools for assisting systems administrators. Herein we present a logical foundation for automated tools that assist in determining which access rights should be granted by reasoning about the effects of an access control mechanism on the computations performed by an operating system. We demonstrate the practicality and utility of our logical approach by showing how it allows us to construct a deductive database capable of answering questions about the security of two real-world operating systems. We illustrate the application of our techniques by presenting the results of an experiment designed to assess how accurately the configuration of an access control mechanism implements a given security policy.

One of the main unsolved problems confronting Hypertext is the navigation problem, namely, the problem of having to know where you are in the database graph representing the structure of a Hypertext database, and knowing how to get to some other place you are searching for in the database graph. In order to tackle this problem we introduce a formal model for Hypertext. In this model a Hypertext database consists of an information repository, which stores the contents of the database in the form of pages, and a reachability relation, which is a directed graph describing the structure of the database. The notion of a trail, which is a path in the database graph describing some logical association amongst the pages in the trail, is central to our model. We define a Hypertext query language for our model based on a subset of propositional linear temporal logic, which we claim to be a natural formalism as a basis for establishing navigation semantics for Hypertext. The output of a trail query in this language is the set (which may be infinite) of all trails that satisfy the query. We show that there is a strong connection between the output of a trail query and finite automata in the sense that, given a Hypertext database and a trail query, we can construct a finite automaton representing the output of the query, which accepts a star-free regular language. We show that the construction of the finite automaton can be done in time exponential in the number of conjunctions, between the subformulas of the trail query, plus one. Given a Hypertext database and a trail query, the problem of deciding whether there exists a trail in the database that satisfies the trail query is referred to as the model checking problem. We show that, although this problem is NP-complete for different subsets of our query language, it can be solved in polynomial time for some significant special cases. Thus the navigation problem can only be efficiently solved in some special cases, and therefore in practice Hypertext systems could include algorithms which return randomized and/or fuzzy solutions.

Although there has been a vast amount of research in the area of relational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If F only satisfies the intersection property then this problem is NP-complete, as in the general case. Moreover, we show that when F either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. Assume that a relation schema R is an appropriate normal form with respect to a set of FDs F. We show that when F satisfies the intersection property then the notions of second normal form and third normal form are equivalent. We also show that when R is in Boyce-Codd Normal Form (BCNF), then F is monodependent if and only if either there is a unique key for R, or for all keys X for R, the cardinality of X is one less than the number of attributes associated with R. Finally, we tackle a long-standing problem in relational database theory by showing that when a set of FDs F over R satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of R with respect to F is also dependecy preserving. As a corollary of this result we are able to show that when F satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of R, which is in BCNF, is also dependency preserving. Our final result is that when F is monodependent, then there exists a unique optimum lossless join decomposition of R, which is in BCNF, and is also dependency preserving. Furthermore, this ultimate decomposition can be attained in polynomial time in the size of F.

We present an alternative approach to that of Chandra and Harel [5] and Abiteboul and Vianu [1] in considering computable database queries, which are mappings from sets of records to sets of records. In particular, we view a computable database query as being realised via a Turing-computable mapping from strings to strings and an encoding, which encodes the input set of records into an appropriate string. An encoding of a set of records consists of two components: an ordering function, which orders the records in a set as well as the values of each record in the set, and an isomorphism, which maps the values in the records of the set to strings. An important class of encodings, called free encodings, whose isomorphism has the same semantics as the identity mapping on record values, is also defined. Our analysis of computable database queries elucidates the notion of a computable database query by dealing with the problem of how a database language can be implemented on a standard Turing machine that does not cater directly for mappings from sets of records to sets of records. We carry out our analysis by categorising computable database queries into subclasses and by establishing the relationships that exist amongst these subclasses. We also investigate an equivalence relation on computable database queries; two computable database queries are related if they are realised via the same Turing-computable mapping, say δ. We prove the following interesting result regarding the cardinality of the equivalence class of a computable query with respect to the said equivalence relation: either δ does not realise any computable query, or δ realises exactly one computable query, or δ realises a countably infinite set of computable queries. Our final result shows that, by adding membership queries to the class of encoding-independent computable queries, the closure of the resulting extended class under composition of mappings is the set of all isomorphism-independent computable queries.

A camera is mounted on a moving robot and can rotate, relative to the robot, about two axes. We show how the optical flow field can be used to control the camera's motion to keep a target at the center of the camera's field of view, but that this is not always possible when the target lies close to the plane defined by the camera's two axes of rotation. When the target is held at the center of the camera's field of view, then the magnitude of the camera's angular velocity about one axis never exceeds the magnitude of the flow vector associated with the target, but the angular velocity about the other axis is dependent on the inverse distance of the target from this axis, and hence can become large as this distance becomes small. Situations, where the magnitudes of the camera's angular velocity and acceleration become large, are considered in the special case where the relative motion between the robot and its environment is purely translational. The tracking strategy is experimentally evaluated using computer-generated optical flow fields.>

Currently, database researchers are investigating new data models in order to remedy the deficiencies of the flat relational model when applied to nonbusiness applications. Herein we concentrate on a recent graph based data model called the hypernode model. The single underlying data structure of this model is the hypernode which is a digraph with a unique defining label. We present in detail the three components of the model, namely its data structure, the hypernode, its query and update language, called HNQL, and its provision for enforcing integrity constraints. We first demonstrate that the said data model is a natural candidate for formalising hypertext. We then compare it with other graph based data models and with set based data models. We also investigate the expressive power of HNQL. Finally, using the hypernode model as a paradigm for graph based data modelling, we show how to bridge the gap between graph based and set based data models, and at what computational cost this can be done.>

The nested relational model extends the flat relational model by relaxing the first normal form assumption in order to allow the modeling of complex objects. Much of the previous work on the nested relational model has concentrated on defining the data structures and query language for the model. The work done on integrity constraints in nested relations has mainly focused on characterizing subclasses of nested relations and defining normal forms for nested relations with certain desirable properties. In this paper we define the semantics of nested relations, which may contain null values, in terms of integrity constraints, called null extended data dependencies , which extend functional dependencies and join dependencies encountered in flat relational database theory. We formalize incomplete information in nested relations by allowing only one unmarked generic null value , whose semantics we do not further specify. The motivation for the choice of a generic null is our desire to investigate only fundamental semantics which are common to all unmarked null types. This lead us to define a preorder on nested relations, which allows us to measure the relative information content of nested relations. We also define a procedure, called the extended chase procedure , for testing satisfaction of null extended data dependencies and for making inferences by using these null extended data dependencies. The extended chase procedure is shown to generalize the classical chase procedure, which is of major importance in flat relational database theory. As a consequence of our approach we are able to capture the novel notion of losslessness in nested relations, called herein null extended lossless decomposition . Finally, we show that the semantics of nested relations are a natural extension of the semantics of flat relations.

To date most previous approaches to incomplete information within the relational model depend on the specific semantics of the null types incorporated into this model. Herein we propose a model for incomplete information in nested relational databases which is independent of the semantics of the null types pertaining to incomplete information. Thus, the proposed model, called the nested relation type (NRT) model, allows, in addition to system-defined null types, user-defined null types. The NRT model extends the nested relational model by incorporating a form of built-in inheritance. This allows us to define a partial order between nester-relations types and a partial order between the data values of these types. By utilizing these partial orders, we define an instance, over a NRT, to be incomplete when its information content may increase. In addition, we define an algebra for the NRT model, called the NRT algebra, which is shown to supersede known algebras for relations with nulls and for nested relations by showing faithfulness to these algebras. We then investigate the monotonicity of the operators of the NRT algebra, which allows us to predict how increasing or decreasing the information content of the instances in the database affects the information content of the user's view, which is constructed from an algebraic expression over the instances in the database. Finally, we enhance the expressive power of the NRT-algebra with a least fixpoint operator in order to allow users to pose recursive queries.

The (k, l) nearest neighbor method of pattern classification is compared to the Bayes method. If the two acceptance rates are equal then the asymptotic error rates satisfy the inequalities Ek,l + 1 ¿ E*(¿) ¿ Ek,l dE*(¿), where d is a function of k, l, and the number of pattern classes, and ¿ is the reject threshold for the Bayes method. An explicit expression for d is given which is optimal in the sense that for some probability distributions Ek,l and dE* (¿) are equal.

We define and characterize orderings of the set of partitions of a positive integer n obtained by traversing the binary tree of the set of partitions of n in each of the three principal orders. Loop-free algorithms for generating the set of partitions in each of these three orders and also in the three corresponding reverse orders are derived. The asymptotic behaviour of each of these six algorithms is examined and compared.

A representation of the partitions of an integer as a binary tree is presented, and the structure of this tree is related to the lexicographic ordering of the set of partitions. The appropriate recursive traversal algorithm for this binary tree immediately yields a recursive algorithm for generating the set of partitions in lexicographic order. Further consideration of the structure of the tree enables us to transform this version of the algorithm into a non-recursive loop-free version. Similar consideration of another recursive traversal algorithm yields corresponding algorithms for generating the set of partitions in a different order.

New lower bounds on the minimal condition numbers of a matrix with respect to both one-sided and two-sided scaling by diagonal matrices are obtained. These bounds improve certain results obtained by F. L. Bauer.

In this paper it is proved that the Jacobi method for normal matrices, due to Goldstine and Horwitz, after a certain stage in the process, is quadratically convergent. The pivot pair (p, q) is chosen so that the sum of the absolute squares of the elements in positions (p, q) and (q, p) is greatest. In this respect, the results obtained here supplement those of Ruhe who considered only the special row cyclic method of enumerating pivot elements.

A lower bound for the departure from normality of an n X n matrix A is given. Furthermore, various inequalities are obtained for certain condition numbers associated with the reduction of A to its Jordan canonical form.

An empirical method is described for providing, with a minimum of effort, useful estimates for the relative errors in individual components of the computed solution x of the system of linear equations Ax = b. The estimate for the error is in no sense a rigorous upper bound, but in view of the economy of effort it is felt that extensions of the method described here a valuable addition to known methods of a posteriori error analyses.