skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Towards Directed Collapsibility (Research)
In the directed setting, the spaces of directed paths between fixed initial and terminal points are the defining feature for distinguishing different directed spaces. The simplest case is when the space of directed paths is homotopy equivalent to that of a single path; we call this the trivial space of directed paths. Directed spaces that are topologically trivial may have non-trivial spaces of directed paths, which means that information is lost when the direction of these topological spaces is ignored. We define a notion of directed collapsibility in the setting of a directed Euclidean cubical complex using the spaces of directed paths of the underlying directed topological space, relative to an initial or a final vertex. In addition, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex. We also give sufficient conditions for the path space between two vertices in a Euclidean cubical complex to be disconnected. Our results have applications to speeding up the verification process of concurrent programming and to understanding partial executions in concurrent programs.  more » « less
Award ID(s):
1618605
PAR ID:
10176042
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
Association for Women in Mathematics series
Volume:
21
ISSN:
2364-5733
Page Range / eLocation ID:
255-271
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; (, Association for Women in Mathematics series)
    Gasparovic, Ellen; Robins, Vanessa; Turner, Katharine (Ed.)
    While collapsibility of CW complexes dates back to the 1930s, collapsibility of directed Euclidean cubical complexes has not been well studied to date. The classical definition of collapsibility involves certain conditions on pairs of cells of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In the undirected setting, pairs of cells are removed that create a deformation retract. In the directed setting, topological properties---in particular, properties of spaces of directed paths---are not always preserved. In this paper, we give computationally simple conditions for preserving the topology of past links. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of spaces of directed paths. Throughout, we provide illustrative examples. 
    more » « less
  2. ; (, Journal of Applied and Computational Topology)
    Abstract. We develop persistent homology in the setting of filtrations of (Cˇech) closure spaces. Examples of filtrations of closure spaces include metric spaces, weighted graphs, weighted directed graphs, and filtrations of topological spaces. We use various products and intervals for closure spaces to obtain six homotopy theories, six cubical singular homology theories, and three simplicial singular homology theories. Applied to filtrations of closure spaces, these homology theories produce persistence modules. We extend the definition of Gromov-Hausdorff distance from metric spaces to filtrations of closure spaces and use it to prove that any persistence module obtained from a homotopy-invariant functor on closure spaces is stable. 
    more » « less
  3. (, Proceedings of the Canadian Conference on Computational Geometry)
    The Frechet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Frechet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Frechet distance, in an effort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 
    more » « less
  4. ; ; ; ; (, CCCG)
    The Fréchet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Fréchet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Fréchet distance, in an eort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 
    more » « less
  5. ; ; ; ; (, Young Researcher's Forum (CG Week))
    We examine topological properties of spaces of paths and graphs mapped to $$\R^d$$ under the Fr\'echet distance. We show that these spaces are path-connected if the map is either continuous or an immersion. If the map is an embedding, we show that the space of paths is path-connected, while the space of graphs only maintains this property in dimensions four or higher. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email