Execution spaces for simple higher dimensional automata (Q714637): Difference between revisions

This paper belongs to a series of papers about the calculation of the (homotopy type of) spaces of execution paths of a higher dimensional automaton. With respect to the previous paper [Algebr. Geom. Topol. 10, No. 3, 1683--1714 (2010; Zbl 1198.55004)], the author still sticks here to semaphores, i.e. PV models which are all modelled in a hypercube \([0,1]^n\) (this restriction will be removed in the next paper [ibid. 12, No. 3, 1745-1765 (2012; Zbl 1251.55004)]). With respect to the previous paper [op. cit.], two restrictions are removed: 1) the forbidden hyperrectangles can now intersect the boundary of \([0,1]^n\); 2) the calculations made in this paper enable the author also to describe the intermediate execution paths, i.e. not only the execution paths from the bottom vertex (initial state) to the top vertex (final state) of the hypercube, but also the execution paths starting and stopping at intermediate states; this is important for inductive reasoning and calculations. A close look is taken at semaphore models with semaphores all of arity one: the space of execution paths are always homotopy discrete with components representing sets of compatible permutations. Finally, the author describes a model for the complement of the space of execution paths seen as a subspace of a product of spheres which seems to be algorithmically easier and quicker to determine.