No description available.

No description available.

No description available.

No description available.

Feder and Vardi have proved that the class captured by a monadic fragment of existential second-order logic, MMSNP, is computationally equivalent (via randomised reductions) to the class of constraint satisfaction problems (CSP) while the latter is strictly included in the former. I introduce a new class of combinatorial problems, the so-called forbidden patterns problems (FP), that correspond exactly to the logic MMSNP and introduce some novel algebraic tools like the re-colouring that allow me to construct a normal form. This leads to a constructive characterisation of the borderline of CSP within FP: a given problem in FP is either given as a problem in CSP or we build counter-examples. I relate this result to a recent and independent work by Tardif and Nesetril which relies heavily on a correspondence between duality and density. I generalise this approach to FP. Finally, I investigate homomorphism problems for unary algebras.

No description available.

The focus of this research is on the human side of an agile methodology because most of the other research on methodologies tends to focus on the technical aspect. The context for this research is the Software Engineering Observatory at the University of Sheffield, a research facility, which is run by the Verification and Testing (VT) research group. The objective of this observatory is two- fold: firstly, it is to create an environment for the training and development of skills that are associated with the successful construction of a software solution with a real commercial client, and secondly, it is for the carrying out of research work that would be impossible to do in the real software industry. The observatory allows empirical researchers to observe, question or interview software developers working on real industrial projects. The general relevance of this research lies in the ability to evaluate the effectiveness of an agile methodology by first, identifying the difficult practices in the XP methodology and the reasons for the difficulties, with the intention to improve the methodology. Cognitive theory indicates that for a new approach to be accepted easily, it must conform to the ways the brain accepts information, stimulates the mind, and thus motivates the developers. The research demonstrates qualitatively and quantitatively the effect of this improvement on the software developers. Comparison studies between the Extreme Programming (an agile methodology) with the Discovery Method (a design-led methodology) were conducted to evaluate the effect of the XP methodology in term of the work related well being, the work group cohesion, the positive affectivity and finally the quality of the software. To achieve generalisability for some findings, data was collected from an XP team in IBM, Hursley, United Kingdom.

No description available.

A wide variety of real-world optimisation problems can be modelled as Weighted Constraint Satisfaction Problems (WCSPs). Such problems are NP-hard and require an exponential amount of time to find the optimal solution. This thesis concentrates on the University Examination Timetabling Problem. A general abstraction of this problem has been used, as there are many institution-specific rules which could be incorporated into the problem. The use of this problem type allows WCSPs to be investigated using realistic problem data and allows a comparison with previously published results for the problem instances used. We have examined some existing variable ordering heuristics and defined new ones. An analysis methodology has been defined that allows the characteristics of good solutions to be identified. Different methods of identifying difficult to solve sub-problems and the use of such methods in variable ordering has been investigated. Incorporating the weight, or preference, associated with constraints into variable ordering heuristics has been found to be beneficial to finding solutions of low cost. The analysis methodology has been used to examine the relationship between solutions of different quality and the knowledge derived has been used to define, and justify, two new variable ordering heuristics. The usefulness of different value ordering heuristics has been examined. Value selection on the error incurred with past assignments and the use of look-ahead have been investigated. Variable ordering heuristics have been extended to try and exploit the advantages of such value ordering heuristics. The use of stochasticity with such orderings has been investigated and has led to a new class of hybrid value ordering heuristics being defined. Finally two hybrid search algorithms have been defined that attempt to concentrate search upon the sections of the problem instance which have the largest effect upon the overall quality of solutions found. Such methods are shown to be at least competitive with standard tree based search techniques.

Spider diagrams are a recently developed visual logic that make statements about relationships between sets, their members and their cardinalities. By contrast, the study of regular languages is one of the oldest active branches of computer science research. The work in this thesis examines the previously unstudied relationship between spider diagrams and regular languages. In this thesis, the existing spider diagram logic and the underlying semantic theory is extended to allow direct comparison of spider diagrams and star-free regular languages. Thus it is established that each spider diagram defines a commutative star-free regular language. Moreover, we establish that every com- mutative star-free regular language is definable by a spider diagram. From the study of relationships between spider diagrams and commutative star-free regular languages, an extension of spider diagrams is provided. This logic, called spider diagrams of order, increases the expressiveness of spider di- agrams such that the language of every spider diagram of order is star-free and regular, but not-necessarily commutative. Further results concerning the expres- sive power of spider diagrams of order are gained through the use of a normal form for the diagrams. Sound reasoning rules which take a spider diagram of order and produce a semantically equivalent diagram in the normal form are pro- vided. A proof that spider diagrams of order define precisely the star-free regular languages is subsequently presented. Further insight into the structure and use of spider diagrams of order is demonstrated by restricting the syntax of the logic. Specifically, we remove spiders from spider diagrams of order. We compare the expressiveness of this restricted fragment of spider diagrams of order with the unrestricted logic.