| Directed Topology |
Spaces often come equipped with directionality, like vector fields, partial orders, and simplicial orientations. Directed algebraic topology studies algebraic invariants on such spaces that can capture information about the topology and directionality.
| Applied Topology |
||| Flow-cut dualities for sheaves on graphs |
S. Krishnan, "Flow-cut dualities for sheaves on graphs," preprint, 2014.[pdf] [arXiv]
||| A Topological Max-Flow Min-Cut Theorem |
Abstract: This note generalizes the Max-Flow Min-Cut (MFMC) theorem from numerical edge capacities to cellular semimodule-valued sheaves on directed graphs. Examples of such sheaves include probability distributions, multicommodity constraints, and logical propositions.
R. Ghrist, S. Krishnan, "A Topological Max-Flow Min-Cut Theorem," Proceedings of Global Signals. Inf., (2013).[pdf]
||| Cubical approximation for directed topology I |
S. Krishnan, "Cubical approximation for directed topology I," Applied Categorical Structures, Springer Netherlands, (2013), doi: 10.1007/s10485-013-9330-y, pp 1-38.[pdf] [arXiv]
||| A free object in quantum information theory |
The homotopy theory of locally preordered state spaces can detect machine behavior unseen by the classical homotopy theory of spaces. The geometric realizations of simplicial sets and cubical sets admit "local preorders" encoding the orientations of simplices and 1-cubes, respectively. We prove simplicial and cubical approximation theorems appropriate for this homotopy theory. Along the way, we discover criteria under which two alternative definitions of a homotopy relation on locally monotone maps coincide.
J. Feng, K. Martin, S. Krishnan, "A free object in quantum information theory," Electronic Notes in Theoretical Computer Science, (2010), vol. 265, pp 35-47.[pdf]
||| Future path-components in directed topology |
The global states of complex systems often form pospaces, topological spaces equipped with compatible partial orders reflecting causal relationships between the states. The calculation of tractable invariants on such pospaces can reveal critical system behavior unseen by ordinary invariants on the underlying spaces, thereby sometimes cirumventing the state space problem bedevilling static analysis. We introduce a practical technique for calculating future path-components, algebraic invariants on pospaces of states and hence tractable descriptions of the qualitative behavior of concurrent processes.
E. Goubault, E. Haucourt, S. Krishnan, "Future path-components in directed topology," Electronic Notes in Theoretical Computer Science, (2010), vol. 265, pp 325-335.[pdf]
||| Covering space theory for directed topology |
The state space of a machine admits the structure of time. For example, the geometric realization of a precubical set, a generalization of an unlabeled asynchronous transition system, admits a "local preorder" encoding control flow. In the case where time does not loop, the "locally preordered" state space splits into causally distinct components. The set of such components often gives a computable invariant of machine behavior. In the general case, no such meaningful partition could exist. However, as we show in this note, the locally preordered geometric realization of a precubical set admits a "locally monotone" covering from a state space in which time does not loop. Thus we hope to extend geometric techniques in static program analysis to looping processes.
E. Goubault, E. Haucourt, S. Krishnan, "Covering space theory for directed topology," Theory and Application of Categories, (2009), vol. 22, pp. 252-268.[pdf] [arXiv]
||| Criteria for homotopic maps to be so along monotone homotopies The state spaces of machines admit the structure of time. A homotopy theory respecting this additional structure can detect machine behavior unseen by classical homotopy theory. In an attempt to bootstrap classical tools into the world of abstract spacetime, we identify criteria for classically homoAt, monotone maps of pospaces to future homotope, or homotope along homotopies monotone in both coordinates, to a common map. We show that consequently, a hypercontinuous lattice equipped with its Lawson topology is future contractible, or contractible along a future homotopy, if its underlying space has connected CW type. |
S. Krishnan, "Criteria for homoAt maps to be so along monotone homotopies," Electronic Notes in Theoretical Computer Science (2009), pp. 141-148, vol. 230, pp 141–148.[pdf] [arXiv]
||| A convenient category of locally preordered spaces |
As a practical foundation for a homotopy theory of abstract spacetime, we extend a category of certain compact partially ordered spaces to a convenient category of locally preordered spaces. In particular, we show that our new category is Cartesian closed and that the forgetful functor to the category of compactly generated spaces creates all limits and colimits.
S. Krishnan, "A convenient category of locally preordered spaces," Applied Categorical Structures, vol. 17 (5), pp 445-466.[arXiv]