Topological mappings between graphs, trees and generalized trees

We present novel topological mappings between graphs, trees and generalized trees that means between structured objects with different properties. The two major contributions of this paper are, first, to clarify the relation between graphs, trees and generalized trees, a graph class recently introduced. Second, these transformations provide a unique opportunity to transform structured objects into a representation that might be beneficial for a processing, e.g., by machine learning techniques for graph classification. (c) 2006 Elsevier Inc. All rights reserved.

Goal Recognition through Goal Graph Analysis

We present a novel approach to goal recognition based on a two-stage paradigm of graph construction and analysis. First, a graph structure called a Goal Graph is constructed to represent the observed actions, the state of the world, and the achieved goals as well as various connections between these nodes at consecutive time steps. Then, the Goal Graph is analysed at each time step to recognise those partially or fully achieved goals that are consistent with the actions observed so far. The Goal Graph analysis also reveals valid plans for the recognised goals or part of these goals. Our approach to goal recognition does not need a plan library. It does not suffer from the problems in the acquisition and hand-coding of large plan libraries, neither does it have the problems in searching the plan space of exponential size. We describe two algorithms for Goal Graph construction and analysis in this paradigm. These algorithms are both provably sound, polynomial-time, and polynomial-space. The number of goals recognised by our algorithms is usually very small after a sequence of observed actions has been processed. Thus the sequence of observed actions is well explained by the recognised goals with little ambiguity. We have evaluated these algorithms in the UNIX domain, in which excellent performance has been achieved in terms of accuracy, efficiency, and scalability.

Monotonically normal topological vector spaces are stratifiable

We prove that for any Hausdorff topological vector space E over the field R there exists A subset of E such that E is homeomorphic to a subset of A x R and A x R is homeomorphic to a subset of E. Using this fact we prove that E is monotonically normal if and only if E is stratifiable.

Decay measures on locally compact abelian topological groups

Source: PROCEEDINGS OF THE ROYAL SOCIETY OF EDINBURGH SECTION A-MATHEMATICS Volume: 131 Pages: 1257-1273 Part: Part 6 Published: 2001 Times Cited: 5 References: 23 Citation MapCitation Map beta Abstract: We show that the Banach space M of regular sigma-additive finite Borel complex-valued measures on a non-discrete locally compact Hausdorff topological Abelian group is the direct sum of two linear closed subspaces M-D and M-ND, where M-D is the set of measures mu is an element of M whose Fourier transform vanishes at infinity and M-ND is the set of measures mu is an element of M such that nu is not an element of MD for any nu is an element of M \ {0} absolutely continuous with respect to the variation \mu\. For any corresponding decomposition mu = mu(D) + mu(ND) (mu(D) is an element of M-D and mu(ND) is an element of M-ND) there exist a Borel set A = A(mu) such that mu(D) is the restriction of mu to A, therefore the measures mu(D) and mu(ND) are singular with respect to each other. The measures mu(D) and mu(ND) are real if mu is real and positive if mu is positive. In the case of singular continuous measures we have a refinement of Jordan's decomposition theorem. We provide series of examples of different behaviour of convolutions of measures from M-D and M-ND.

Universal Abelian topological groups

A topological group G is said to be universal in a class K of topological groups if G is an element of K and if for every group H is an element of K there is a subgroup K of G that is isomorphic to H as a topological group. A group is constructed that is universal in the class of separable metrizable topological Abelian groups.

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.

Compact Toffoli gate using weighted graph states

We introduce three compact graph states that can be used to perform a measurement-based Toffoli gate. Given a weighted graph of six, seven, or eight qubits, we show that success probabilities of 1/4, 1/2, and 1, respectively, can be achieved. Our study puts a measurement-based version of this important quantum logic gate within the reach of current experiments. As the graphs are setup independent, they could be realized in a variety of systems, including linear optics and ion traps.