Hostname: page-component-cb9f654ff-kl2l2 Total loading time: 0 Render date: 2025-08-07T04:29:15.688Z Has data issue: false hasContentIssue false

Non-Hausdorff parallelized manifolds over geometric models of conservative programs

Published online by Cambridge University Press:  22 July 2025

Emmanuel Haucourt*
Affiliation:
École polytechnique, LIX - UMR, 7161, Palaiseau, France

Abstract

Every directed graph $G$ induces a locally ordered metric space $\mathcal{X}_{(G)}$ together with a local order $\tilde {\mathcal{X}}_{(G)}$ that is locally dihomeomorphic to the standard pospace $\mathbb{R}$; both are related by a morphism ${\beta }_{(G)} G:\tilde {\mathcal{X}}_{(G)}\to {\mathcal{X}}_{(G)}$ satisfying a universal property. The underlying set of $\tilde {\mathcal{X}_{(G)}}$ admits a non-Hausdorff atlas $\mathcal{A}_{G}$ equipped with a non-vanishing vector field ${{f}}_{G}$; the latter is associated to $\tilde {\mathcal{X}}_{(G)}$ through the correspondence between local orders and cone fields on manifolds. The above constructions are compatible with Cartesian products, so the geometric model of a conservative program is lifted through ${{\beta }_{G_1}} \times \cdots \times {{\beta }}_{G_n}$ to a subset $M$ of the parallelized manifold $\mathcal{A}_{G_1} \times \cdots \times \mathcal{A}_{G_n}$. By assigning the suitable norm to each tangent space of $\mathcal{A}_{G_1} \times \cdots \times \mathcal{A}_{G_n}$, the length of every directed smooth path $\gamma$ on $M$, i.e. $\int {{|\gamma '(t)|}}_{\gamma (t)}dt$, corresponds to the execution time of the sequence of multi-instructions associated to $\gamma$. This induces a pseudometric ${{d}}_{\mathcal{A}}$ whose restrictions to sufficiently small open sets of $\mathcal{A}_{G_1} \times \cdots \times \mathcal{A}_{G_n}$ (we refer to the manifold topology, which is strictly finer than the pseudometric topology) are isometric to open subspaces of ${\mathbb{R}}^n$ with the $\alpha$-norm for some $\alpha \in [{{1}},{{\infty }}]$. The transition maps of $\mathcal{A}_{G}$ are translations, so the representation of a tangent vector does not depend on the chart of $\mathcal{A}_{G}$ in which it is represented; consequently, differentiable maps between open subsets of $\mathcal{A}_{G_{1}} \times \cdots \times \mathcal{A}_{G_{n}}$ are handled as if they were maps between open subsets of ${\mathbb{R}}^n$. For every directed path $\gamma$ on $M$ (possibly the representation of a sequence $\sigma$ of multi-instructions), there is a shorter directed smooth path on $M$ that is arbitrarily close to $\gamma$, and that can replace $\gamma$ as a representation of $\sigma$.

Information

Type
Paper
Copyright
© The Author(s), 2025. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Adachi, M. (1993). Embeddings and Immersions. American Mathematical Society.Google Scholar
Aho, A. V., Lam, M. S., Sethi, R. and Ullman, J. D. (2007). Compilers: Principles, Techniques, and Tools (2nd edn.). Pearson.Google Scholar
Arenas, F. G. (1999). Alexandroff spaces. Acta mathematica Universitatis Comenianae. New Series (1) 17–25.Google Scholar
Ayala, D., Francis, J. and Tanaka, H. L. (2017). Local structures on stratified spaces. Advances in Mathematics 307 9031028.10.1016/j.aim.2016.11.032CrossRefGoogle Scholar
Baez, J. C. and Hoffnung, A. E. (2011). Convenient categories of smooth spaces. Transactions of the American Mathematical Society 363 (11) 57895825.10.1090/S0002-9947-2011-05107-XCrossRefGoogle Scholar
Baillif, M. and Gabard, A. (2008). Manifolds: Hausdorffness versus homogeneity. Proceedings of the American Mathematical Society. 136 (3) 11051111.10.1090/S0002-9939-07-09100-9CrossRefGoogle Scholar
Bao, D., Chern, S.-S. and Shen, Z. (2000). An Introduction to Riemann-Finsler Geometry, Springer.10.1007/978-1-4612-1268-3CrossRefGoogle Scholar
Benedetti, R. (2021). Lectures on Differential Topology, American Mathematical Society.10.1090/gsm/218CrossRefGoogle Scholar
Bishop, R. L. and Crittenden, R. J. (1964). Geometry of Manifolds, Academic Press.Google Scholar
Brazas, J. (2024). Constructing arcs from paths by collapsing subloops. Rocky Mountain Journal of Mathematics 54 (4) 965974.10.1216/rmj.2024.54.965CrossRefGoogle Scholar
Brickell, F. and Clark, R. S. (1970). Differentiable Manifolds: An Introduction, Van Nostrand.Google Scholar
Bridson, M. R. and Haefliger, A. (1999). Metric Spaces of Non-Positive Curvature, Springer.10.1007/978-3-662-12494-9CrossRefGoogle Scholar
Bröcker, T. and Jänich, K. (1982). Introduction to Differential Topology, Cambridge University Press.Google Scholar
Brokate, M. and Kersting, G. (2015). Measure and Integral, Birkhäuser.10.1007/978-3-319-15365-0CrossRefGoogle Scholar
Carson, S. D. and Reynolds, P. F. Jr. (1987). The geometry of semaphore programs. ACM Transactions on Programming Languages and Systems 9 (1) 2553.10.1145/9758.9759CrossRefGoogle Scholar
Chern, S.-S. and Shen, Z. (2005). Riemann-Finsler Geometry, World Scientific.10.1142/5263CrossRefGoogle Scholar
Coffman, E. G., Elphick, M. and Shoshani, A. (1971). System deadlocks. ACM Computing Surveys 3 (2) 6778.10.1145/356586.356588CrossRefGoogle Scholar
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2022). Introduction to Algorithms, (4th edn.), MIT Press.Google Scholar
Coursolle, P.-Y. and Haucourt, E. (2024). Non-existing and ill-behaved coequalizers of locally ordered spaces. Journal of Applied and Computational Topology 8 (4) 9711021.10.1007/s41468-023-00155-4CrossRefGoogle Scholar
Dang, T. and Gerner, P. (2004) Computing schedules for multithreaded real-time programs using geometry. In: Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems. Springer, 325342.Google Scholar
Dijkstra, E. W. (1968) Cooperating sequential processes. In: Programming Languages. Academic Press, 43112.Google Scholar
Do Carmo, M. P. (1992). Riemannian Geometry (2ndPrinting), Birkhäuser.10.1007/978-1-4757-2201-7CrossRefGoogle Scholar
Fahrenberg, U. and Raussen, M. (2007). Reparametrizations of continuous paths. Journal of Homotopy and Related Structures 2 (2) 93117.Google Scholar
Fajstrup, L., Goubault, É. and Raussen, M. (2006). Algebraic topology and concurrency. Theoretical Computer Science 357 (1) 241278.10.1016/j.tcs.2006.03.022CrossRefGoogle Scholar
Gale, D. (1987). The classification of 1-manifolds: a take-home exam. The American Mathematical Monthly 94 (2) 170175.10.1080/00029890.1987.12000613CrossRefGoogle Scholar
Gauld, D. B. (1982). Differential Topology, Marcel Dekker.Google Scholar
Gauld, D. B. (2014). Non-metrisable Manifolds, Springer.10.1007/978-981-287-257-9CrossRefGoogle Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. W. and Scott, D. S. (1980). A Compendium of Continuous Lattices, Springer.10.1007/978-3-642-67678-9CrossRefGoogle Scholar
Goel, S. K. (1987). Nonseparated manifolds and completely unstable flows. International Journal of Mathematics and Mathematical Sciences 10 (4) 745756.10.1155/S016117128700084XCrossRefGoogle Scholar
Grillet, P. A. (2007). Abstract Algebra, Springer.Google Scholar
Guillemin, V. and Pollack, A. (1974). Differential Topology (2010 Reprint), American Mathematical Society.Google Scholar
Haefliger, A. and Reeb, G. (1957). Variétés (non séparées) à une dimension et structures feuilletées du plan. L’Enseignement Mathématique 3 (2) 107125.Google Scholar
Hájíček, P. (1971a). Bifurcate space-times. Journal of Mathematical Physics 12 (1) 157160.10.1063/1.1665474CrossRefGoogle Scholar
Hájíček, P. (1971b). Causality in non-hausdorff space-times. Communications in Mathematical Physics 21) 7484.10.1007/BF01646486CrossRefGoogle Scholar
Hartshorne, R. (1977). Algebraic Geometry, Springer.10.1007/978-1-4757-3849-0CrossRefGoogle Scholar
Hatcher, A. (2002). Algebraic Topology, Cambridge University Press.Google Scholar
Haucourt, E. (2012). Streams, d-spaces and their fundamental categories. Electronic Notes in Theoretical Computer Science 283) 111151.10.1016/j.entcs.2012.05.008CrossRefGoogle Scholar
Haucourt, E. (2018). The geometry of conservative programs. Mathematical Structures in Computer Science 28 (10) 17231769.10.1017/S0960129517000226CrossRefGoogle Scholar
Hempel, J. (1976). 3-Manifolds, American Mathematical Society.Google Scholar
Herlihy, M., Shavit, N., Luchangco, V. and Spear, M. (2020). The Art of Multiprocessor Programming, Morgan Kaufmann.Google Scholar
Heymann, M. (2015). Minimum Action Curves in Degenerate Finsler Metrics, Springer.10.1007/978-3-319-17753-3CrossRefGoogle Scholar
Hicks, N. J. (1965). Notes on Differential Geometry, Van Nostrand.Google Scholar
Hilgert, J., Hofmann, K. H. and Lawson, J. D. (1989). Lie Groups, Convex Cones, and Semigroups, Oxford University Press.Google Scholar
Hirsch, M. W. (1976). Differential Topology, Springer.10.1007/978-1-4684-9449-5CrossRefGoogle Scholar
Iglesias-Zemmour, P. (2013). Diffeology, American Mathematical Society.10.1090/surv/185CrossRefGoogle Scholar
Jaco, W. (1980). Lectures on Three-Manifold Topology, American Mathematical Society.10.1090/cbms/043CrossRefGoogle Scholar
Kent, S. L., Mimna, RA. and Tartir, J. K. (2009). A note on topological properties of non-Hausdorff manifolds. International Journal of Mathematics and Mathematical Sciences.10.1155/2009/891785CrossRefGoogle Scholar
Kosinski, A. A. (1993). Differential Manifolds, Academic Press.Google Scholar
Kreck, M. (1999) A guide to the classification of manifolds. In: Cappell, S., Ranicki, A. and Rosenberg, J. (eds.) Surveys On Surgery Theory, vol. 1, Princeton University Press, 121134.Google Scholar
Kung, H. T., Papadimitriou, C. H. and Yannakakis, M. Z. (1979). Locking policies: safety and freedom for deadlock. In: Proc. 20th Annual Symposium on Foundations of Computer Science, 286297.Google Scholar
Lafontaine, J. (2015). An Introduction to Differential Manifolds, Springer.10.1007/978-3-319-20735-3CrossRefGoogle Scholar
Lang, S. (1999). Fundamentals of Differential Geometry (corr. 2nd Printing), Springer.10.1007/978-1-4612-0541-8CrossRefGoogle Scholar
Lang, S. (2002). Introduction to Differentiable Manifolds (2nd edn.), Springer.10.1007/b97450CrossRefGoogle Scholar
Lawson, J. D. (1989). Ordered manifolds, invariant cone fields, and semigroups. Forum Mathematicum 1 (1) 273308.10.1515/form.1989.1.273CrossRefGoogle Scholar
Lee, J. M. (2012). Introduction to Smooth Manifolds (2nd edn.), Springer.10.1007/978-1-4419-9982-5CrossRefGoogle Scholar
Lee, J. M. (2018). Introduction to Riemannian Manifolds (2nd edn.), Springer.10.1007/978-3-319-91755-9CrossRefGoogle Scholar
Lipski, W. Jr. and Papadimitriou, C. H. (1981). A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems. Journal of Algorithms 2 (3) 211226.10.1016/0196-6774(81)90023-7CrossRefGoogle Scholar
Luc, J. and Placek, T. (2020). Interpreting non-Hausdorff manifolds in general relativity. Philosophy of Science 87 (1) 2142.10.1086/706116CrossRefGoogle Scholar
Mac Lane, S. and Moerdijk, I. (1994). Sheaves in Geometry and Logic (corr. 2nd printing) edn. Springer.10.1007/978-1-4612-0927-0CrossRefGoogle Scholar
Mardani, A. (2014). Topics in the General Topology of Non-metric Manifolds. PhD dissertation, University of Auckland.Google Scholar
Marsden, J. E., Ratiu, T. and Abraham, R. (1988). Manifolds, Tensor Analysis, and Applications (2nd edn.), Springer.Google Scholar
Massey, W. S. (1991). A Basic Course in Algebraic Topology (3rd edn.), Springer.10.1007/978-1-4939-9063-4CrossRefGoogle Scholar
Milnor, J. (1965). Topology From the Differential Viewpoint, University Press of Virginia.Google Scholar
Mukherjee, A. (2015). Differential Topology (2nd edn.), Birkhäuser.10.1007/978-3-319-19045-7CrossRefGoogle Scholar
Müller, T. (2013). A generalized manifold topology for branching space-times. Philosophy of Science 80 (5) 10891100.10.1086/673895CrossRefGoogle Scholar
Munkres, J. R. (2000). Topology (2nd ed), Prentice-Hall.Google Scholar
Nachbin, L. (1965). Topology and Order, Van Nostrand.Google Scholar
Nachbin, L. (1981). Introduction to Functional Analysis: Banach Spaces and Differential Calculus, Marcel Dekker.Google Scholar
Nestruev, J. (2020). Smooth Manifolds and Observables (2nd ed), Springer.10.1007/978-3-030-45650-4CrossRefGoogle Scholar
Nocera, G. and Volpe, M. (2023). Whitney stratifications are conically smooth. Selecta Mathematica-New Series. 29 (68.10.1007/s00029-023-00877-4CrossRefGoogle Scholar
Papadopoulos, A. (2013). Metric Spaces, Convexity, and Nonpositive Curvature (2nd ed), European Mathematical Society.Google Scholar
Pflaum, M. J. (2001). Analytic and Geometric Study of Stratified Spaces, Springer.Google Scholar
Pratt, V. (2000). Higher dimensional automata revisited. Mathematical Structures in Computer Science 10 (4) 525548.10.1017/S0960129500003169CrossRefGoogle Scholar
Rudin, W. (1976). Principles of Mathematical Analysis (3rd ed), McGraw-Hill.Google Scholar
Schaefer, H. H. and Wolff, M. P. (1999). Topological Vector Spaces (2nd ed), Springer.10.1007/978-1-4612-1468-7CrossRefGoogle Scholar
Schröder, B. S. W. (2003). Ordered Sets, An Introduction, Birkhäuser.10.1007/978-1-4612-0053-6CrossRefGoogle Scholar
Scorpan, A. (2005). The Wild World of 4-Manifolds, American Mathematical Society.Google Scholar
Segal, I. E. (1976). Mathematical Cosmology and Extragalacic Astronomy, Academic Press.Google Scholar
Stacey, A. (2011). Comparative smootheology. Theory and Applications of Categories 25 (4) 64117.Google Scholar
Wall, C. T. C. (2016). Differential Topology, Cambridge University Press.10.1017/CBO9781316597835CrossRefGoogle Scholar
Whitney, H. (1944). The self-intersections of a smooth $n$ -manifold in 2n-space. Annals of Mathematics 45 (2) 220246.10.2307/1969265CrossRefGoogle Scholar