Narrow Results

In this paper, we are concerned with the $T$-Graphs, which are graphs defined based on the Topological structure of the given set. Precisely, for a given topology $T$ on a set $X$, a $T$-Graph ‘$G=(V,E)$’ is an undirected simple graph with the vertex set $V$ as $P(X)$ and the edge set $E$ as the set of all unordered pairs of nodes $u,v$ in $V$, denoted by $(u,v)\text{ or }(v,u)$, satisfying either ‘$u\in T$ and $u^{\text{c}}\cap v\in T$’ (or) ‘$v\in T$ and $v^{\text{c}}\cap u\in T$’.

The main purpose of this paper is to study the structure of $T$-Graphs for various topologies $T$ on a set $X$. Our goals in this paper are threefold. First, to show the $L_d(2,1)$ labeling number $\lambda (G,d)$ of any $T$-Graph $G$ exists finitely, if the labeling is $d$ multiple of non-negative integral values. In addition to show this labeling number $\lambda (G,d)$ is not just bounded above but bounded below as well. Second, to measure the bound values in terms of $d$ multiple of the order of the $T$-Graphs and finding a relation between the order of the $T$-Graphs and the maximum degree $\mathrm{\Delta }$ of the $T$-Graphs. Finally, third is to show that in case of $L(2,1)$$T$-graphs on a set with atleast 2 elements, the labeling number is $2(\mathrm{\Delta }+1)$ and is smaller than that of Griggs and Yeh’s conjecture value ${\mathrm{\Delta }}^2$.

It was noticed by Harel in [Har86] that "one can define -complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular ω-language is -complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is -complete to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about ω-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given ω-rational function is continuous, while we show here that it is -complete to determine whether a given ω-rational function has at least one point of continuity. Next we prove that it is -complete to determine whether the continuity set of a given ω-rational function is ω-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].

We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function $F:{\mathrm{\Sigma }}^{\omega }\to {\mathrm{\Gamma }}^{\omega }$, one can construct a deterministic Büchi automaton ${𝒜}$ accepting a dense ${\mathrm{\Pi }}_2^0$-subset of ${\mathrm{\Sigma }}^{\omega }$ such that the restriction of $F$ to $L({𝒜})$ is continuous. Secondly, we give a new proof of the decidability of the first Baire class for synchronous $\omega$-rational functions from which we get an extension of this result involving the notion of Wadge classes of regular $\omega$-languages.

The fastest supercomputers today such as Blue Gene/L, Blue Gene/P, Cray XT3 and XT4 are connected by a three-dimensional torus/mesh interconnect. Applications running on these machines can benefit from topology-awareness while mapping tasks to processors at runtime. By co-locating communicating tasks on nearby processors, the distance traveled by messages and hence the communication traffic can be minimized, thereby reducing communication latency and contention on the network. This paper describes preliminary work utilizing this technique and performance improvements resulting from it in the context of a n-dimensional k-point stencil program. It shows that even for simple benchmarks, topology-aware mapping can have a significant impact on performance. Automated topology-aware mapping by the runtime using similar ideas can relieve the application writer from this burden and result in better performance. Preliminary work towards achieving this for a molecular dynamics application, NAMD, is also presented. Results on up to 32,768 processors of IBM's Blue Gene/L, 4,096 processors of IBM's Blue Gene/P and 2,048 processors of Cray's XT3 support the ideas discussed in the paper.

In this paper, we devise an adaptive hardware architecture for ANNs that takes advantage of the dedicated adder blocks, commonly called MACs, to compute both the weighted sum and activation function. The proposed architecture requires a reduced silicon area considering the fact that the MACs come for free as these are FPGA's built-in hardcores and if not used, they cannot be optimized in the final design. The implementation uses integer fixed point arithmetic and operates with fractions to represent real numbers. The hardware is fast because it is massively parallel, yet it is compact as it has a single physical layer of neurons while the remaining are virtual. Besides, the proposed architecture is adaptive; so it is designed to adjust itself on-the-fly to the user-defined configuration of the neural network, i.e., the number of layers and neurons per layer as well as the topology of the ANN can be configured with no extra hardware changes nor any supplementary design effort.

Network on Chip (NoC) is a new communication medium used for systems-on-chip (SoCs). In an SoC, the placement of the communicating elements across the network has an impact on system performance. Such a placing is called the MAPPING phase in networks on chip design process. Many approaches dealing with the mapping phase have been proposed but selecting the best technique for a given NoC remains a challenging problem. This paper attempts to provide an answer to this issue. It motivates and presents a definition and a classification according to some criteria: (i) the algorithms used for solving the mapping problem, (ii) the moment in which the mapping is executed, (iii) the impact of combining mapping with other phases during NoC design and (iv) the target architecture.

Given a two- or three-dimensional set S of arbitrary topology and a radius r, we show how to construct an r-tightening of S, which is a set whose boundary has mean curvature with magnitude less than or equal to 1/r and which only differs from S in a morphologically-defined tolerance zone we call the mortar. The mortar consists of the thin or highly curved parts of S and its complement, such as corners, gaps, and small connected components, while the boundary of a tightening consists of components of locally minimal length (in 2D) or area (in 3D) that lie in the mortar. Tightenings are defined independently of shape representation, and it may be possible to find them using a variety of algorithms. We describe how to approximately compute tightenings for two-dimensional sets represented as binary images and for three-dimensional sets represented as triangle meshes using constrained, level-set curvature flow.

Topology-based methods have been successfully used for the analysis and visualization of piecewise-linear functions defined on triangle meshes. This paper describes a mechanism for extending these methods to piecewise-quadratic functions defined on triangulations of surfaces. Each triangular patch is tessellated into monotone regions, so that existing algorithms for computing topological representations of piecewise-linear functions may be applied directly to the piecewise-quadratic function. In particular, the tessellation is used for computing the Reeb graph, a topological data structure that provides a succinct representation of level sets of the function.

The Doubly Linked Face List (DLFL) is a data structure for mesh representation that always ensures topological 2-manifold consistency. Furthermore, it uses a minimal amount of computer memory and allows queries to be performed very efficiently. However, the use of the DLFL for the implementation of practical applications is very limited, mainly because of two drawbacks: (1) the DLFL is only able to represent 2-manifold objects; (2) its operators may be ambiguous, modifying the structure in an unexpected way from the user's point of view. In order to overcome these drawbacks, we present the Extended Doubly Linked Face List (XDLFL), which extends the DLFL for the representation of 2-pseudomanifolds and 2-manifolds with boundaries, increasing its applicability for practical software applications. Using these extensions, we also show how to avoid ambiguities in the original DLFL's operators. A new set of intuitive operators for the manipulation of the extensions and for the unambiguous manipulation of the data structure is also presented. The implementation of these extensions is straightforward, since the modifications to the DLFL are trivial and based on behavioral observations of the DLFL's operators. After integrating the extensions to the DLFL, memory usage increases very slightly, while is still smaller than the memory usage of other well-known data structures. Furthermore, queries related to the new extensions, such as whether an edge belongs to a boundary, may be performed very efficiently. The proposed extensions and their operators are very beneficial for applications such as surgery simulation softwares, where the interactions with the models, such as cutting or appending objects to each other, must be performed in an efficient and transparent manner.

Watermarking techniques for vector graphics dislocate vertices in order to embed imperceptible, yet detectable, statistical features into the input data. The embedding process may result in a change of the topology of the input data, e.g., by introducing self-intersections, which is undesirable or even disastrous for many applications. In this paper we present a watermarking framework for two-dimensional vector graphics that employs conventional watermarking techniques but still provides the guarantee that the topology of the input data is preserved. The geometric part of this framework computes so-called maximum perturbation regions (MPR) of vertices. We propose two efficient algorithms to compute MPRs based on Voronoi diagrams and constrained triangulations. Furthermore, we present two algorithms to conditionally correct the watermarked data in order to increase the watermark embedding capacity and still guarantee topological correctness. While we focus on the watermarking of input formed by straight-line segments, one of our approaches can also be extended to circular arcs. We conclude the paper by demonstrating and analyzing the applicability of our framework in conjunction with two well-known watermarking techniques.

We extensively discuss a new interconnection network topology, denoted by ϒ(n,r). Firstly, the ϒ(n,2) network is shown to provide average cost 3 log₂ n while providing superior fault tolerance characteristics. It is defined over any natural number of nodes n using 2n-3 edges for an average degree of 4 and has diameter no greater than k=⌈log₂n⌉ with average diameter as small as . The network is planar and has cyclomatic number n-2. For n=2^t the unbounded maximum degree is 2 log₂ n-1 believed indicative of generally a maximum unbounded degree O(log₂n). The bisection width ranges from 3 when n=2^t to t+1 when n=2^t+1. Secondly, we provide the ϒ*(n,r) network of bounded degree 2r. For n=r^t the ϒ*(n,r) network has asymptotically better average cost than the general deBruijn(r,t) network while also maintaining planarity and cyclomatic property of ϒ(n,2). The ϒ family exhibits unique extremal properties of both theoretical interest and practical importance.

Partial Differential Equations (PDEs) have dominated image processing research recently. The three main reasons for their success are: first, their ability to transform a segmentation modeling problem into a partial differential equation framework and their ability to embed and integrate different regularizers into these models; second, their ability to solve PDEs in the level set framework using finite difference methods; and third, their easy extension to a higher dimensional space.

This paper is an attempt to survey and understand the power of PDEs to incorporate into geometric deformable models for segmentation of objects in 2D and 3D in still and motion imagery. The paper first presents PDEs and their solutions applied to image diffusion. The main concentration of this paper is to demonstrate the usage of regularizers in PDEs and level set framework to achieve the image segmentation in still and motion imagery. Lastly, we cover miscellaneous applications such as: mathematical morphology, computation of missing boundaries for shape recovery and low pass filtering, all under the PDE framework. The paper concludes with the merits and the demerits of PDEs and level set-based framework for segmentation modeling. The paper presents a variety of examples covering both synthetic and real world images.

With the recent advances in computed tomography and magnetic resonance devices, cross-sectional images are now commonly used for diagnosis. However, how contours between cross-sections should be connected is often ambiguous. In this paper, we propose an algorithm that enumerates all possible cases of the correspondence of contours. This is useful for achieving fully automatic interpolation of contours, although our current implementation still requires some degree of manual interaction.

The persistent homology provides a mathematical tool to describe "features" in a principled manner. The persistence algorithm proposed by Edelsbrunner et al. can compute not only the persistent homology for a filtered simplicial complex, but also representative generating cycles for persistent homology groups. However, if there are dynamic changes either in the filtration or in the underlying simplicial complex, the representative generating cycle can change wildly.

In this paper, we consider the problem of tracking generating cycles with temporal coherence. Specifically, our goal is to track a chosen essential generating cycle so that the changes in it are "local". This requires reordering simplices in the filtration. To handle reordering operations, we build upon the matrix framework proposed by Cohen-Steiner et al. to swap two consecutive simplices, so that we can process a reordering directly. We present an application showing how our algorithm can track an essential cycle in a complex constructed out of a point cloud data.

We study the transition graph of generic Hamiltonian surface flows, whose vertices are the topological equivalence classes of generic Hamiltonian surface flows and whose edges are the generic transitions. Using the transition graph, we can describe time evaluations of generic Hamiltonian surface flows (e.g., fluid phenomena) as walks on the graph. We propose a method for constructing the complete transition graph of all generic Hamiltonian flows. In fact, we construct two complete transition graphs of Hamiltonian surface flows having three and four genus elements. Moreover, we demonstrate that a lower bound on the transition distance between two Hamiltonian surface flows with any number of genus elements can be calculated by solving an integer programming problem using vector representations of Hamiltonian surface flows.

This paper shows that the topological structures of particle orbits generated by a generic class of vector fields on spherical surfaces, called the flow of finite type, are in one-to-one correspondence with discrete structures such as trees/graphs and sequences of letters. The flow of finite type is an extension of structurally stable Hamiltonian vector fields, which appear in many theoretical and numerical investigations of two-dimensional (2D) incompressible fluid flows. Moreover, it contains compressible 2D vector fields such as the Morse–Smale vector fields and the projection of 3D vector fields onto 2D sections. The discrete representation is not only a simple symbolic identifier for the topological structure of complex flows, but it also gives rise to a new methodology of topological data analysis for flows when applied to data brought by measurements, experiments, and numerical simulations of complex flows. As a proof of concept, we provide some applications of the representation theory to 2D compressible vector fields and a 3D vector field arising in an industrial problem.

Electric spring (ES) is an emerging power quality adjustment method that can effectively solve the power quality problem, especially voltage fluctuations caused by renewable energy sources. However, the existing topologies of ES have the shortcoming of limited compensation range due to their structure, in which ES is in series with non-critical load (NCL). In this paper, a novel ES is proposed based on a passively damped LCL filter. Unlike the existing ES topologies, LCL-ES employs NCL to implement passive damping of LCL filter, which not only overcomes the passive damping but also extends the compensation range. Besides, the key points on topology design and control strategy are discussed. Finally, the effectiveness of the proposed LCL-ES has been verified via simulation.

Artistic anatomy involves the study of 3D forms which is related to the human body itself and its constitutive structures as the basis for 3D modeling of topographic line structures. Understanding artistic anatomy relies on visual and 3D spatial concepts and is the foundation of students’ education in developing games and making animations. By combining graphical data of anatomical structures with the production of digital sculptures, students were provided a new way to interact with anatomical structures. Six human sculpture sessions were planned for the course and tested both before and after the sessions. The results showed that the digital sculpture course resulted in a consistent improvement in students’ understanding and concepts of artistic anatomy and an understanding of the relationship between the line structure of the 3D model and the texture of the human body.

We show that a whole bunch of well known topological constructs have isomorphic descriptions by means of sets structured by some collection of (generalized) metrics of a certain type together with suitable morphisms. The classification of the categories listed in the table at the end of the paper, is based on different saturation conditions acting on certain collections of generalized metrics. These conditions are composed out of different building blocks. For instance on collections of quasi-pre-metrics we encounter saturation conditions that are combinations of the following properties: prime ideal, ideal, locally qualified saturation, uniform qualified saturation, locally quantified saturation and uniform quantified saturation. Combinations of these enable us to characterize the constructs in the first colum of the summarizing table at the end of the paper: pretopological spaces, preclosure spaces, semi-quasi uniform spaces, pre-approach spaces, quasi -pre metric spaces. The more important subconstructs of these examples, such as topological spaces, completely regular spaces, uniform spaces, proximity spaces, approach spaces and metric spaces, are characterized using essentially the same building blocks of saturation properties, restricted to particular subclasses of generalised metrics.

We show here some of our results on intuitionistic fuzzy topological spaces. In 1983, K.T. Atanassov proposed a generalization of the notion of fuzzy set: the concept of intuitionistic fuzzy set. D. Çoker constructed the fundamental theory on intuitionistic fuzzy topological spaces, and D. Çoker and other mathematicians studied compactness, connectedness, continuity, separation, convergence and paracompactness in intuitionistic fuzzy topological spaces. Finally, G.-J Wang and Y.Y. He showed that every intuitionistic fuzzy set may be regarded as an L-fuzzy set for some appropriate lattice L. Nevertheless, the results obtained by above authors are not redundant with other for ordinary fuzzy sense. Recently, Smarandache defined and studied neutrosophic sets (NSs) which generalize IFSs. This author defined also the notion of neutrosophic topology. We proved that neutrosophic topology does not generalize the concept of intuitionistic fuzzy topology.