1,721,044 research outputs found
Cubical local partial orders on cubically subdivided spaces - Existence and construction
No full textThe geometric models of higher dimensional automata (HDA) and Dijkstra's PV-model are cubically subdivided topological spaces with a local partial order. If a cubicalization of a topological space is free of immersed cubic Möbius bands, then there are consistent choices of direction in all cubes, such that any n-cube in the cubic subdivision is dihomeomorphic to [0,1]^n with the induced partial order from R^n. After subdivision once, any cubicalized space has a cubical local partial order. In particular, all triangularized spaces have a cubical local partial order. This implies in particular that the underlying geometry of an HDA may be quite complicated. Udgivelsesdato: NOV 12The geometric models of higher dimensional automata (HDA) and Dijkstra's PV-model are cubically subdivided topological spaces with a local partial order. If a cubicalization of a topological space is free of immersed cubic Möbius bands, then there are consistent choices of direction in all cubes, such that any n-cube in the cubic subdivision is dihomeomorphic to [0,1]^n with the induced partial order from R^n. After subdivision once, any cubicalized space has a cubical local partial order. In particular, all triangularized spaces have a cubical local partial order. This implies in particular that the underlying geometry of an HDA may be quite complicated
Cut-off Theorems for the PV-model
Get PDFWe prove cut-off results for deadlocks and serializability of a -thread
run in parallel with itself: For a thread which accesses a set
of resources, each with a maximal capacity
, the PV-program , where copies of
are run in parallel, is deadlock free for all if and only if is
deadlock free where . This is a sharp
bound: For all and finite there
is a thread using these resources such that has a deadlock, but
does not for . Moreover, we prove a more general theorem: There are no
deadlocks in if and only if there are no deadlocks in
for any subset . For , is serializable for all if and only
if is serializable. For general capacities, we define a local obstruction
to serializability. There is no local obstruction to serializability in
for all if and only if there is no local obstruction to serializability in
for . The obstructions may be
found using a deadlock algorithm in . These serializability results
also have a generalization: If there are no local obstructions to
serializability in any of the -dimensional sub programs,
, then is serializable
Dipaths and dihomotopies in a cubical complex
No full textIn the geometric realization of a cubical complex without degeneracies, a -set, dipaths and dihomotopies may not be combinatorial, i.e., not geometric realizations of combinatorial dipaths and equivalences. When we want to use geometric/topological tools to classify dipaths on the 1-skeleton, combinatorial dipaths, up to dihomotopy, and in particular up to combinatorial dihomotopy, we need that all dipahts are in fact dihomotopic to a combinatorial dipath. And moreover that two combinatorial dipaths which are dihomotopic are then combinatorially dihomotopic. We prove that any dipath from a vertex to a vertex is dihomotopic to a combinatorial dipath, in a non-selfintersecting -set. And that two combinatorial dipaths which are dihomotopic threough a non-combinatorial dihomogopy are in fact combinatorially dihomotopic, in a geometric -set. Moreover, we prove that in a geometric -set, the d-homotopy introdced in [M. Grandis (2003)] coincides with the dihomotopy in [L. Fajstrup, E. Goubault, M. Raussen (1999)]. Udgivelsesdato: AUGIn the geometric realization of a cubical complex without degeneracies, a -set, dipaths and dihomotopies may not be combinatorial, i.e., not geometric realizations of combinatorial dipaths and equivalences. When we want to use geometric/topological tools to classify dipaths on the 1-skeleton, combinatorial dipaths, up to dihomotopy, and in particular up to combinatorial dihomotopy, we need that all dipahts are in fact dihomotopic to a combinatorial dipath. And moreover that two combinatorial dipaths which are dihomotopic are then combinatorially dihomotopic. We prove that any dipath from a vertex to a vertex is dihomotopic to a combinatorial dipath, in a non-selfintersecting -set. And that two combinatorial dipaths which are dihomotopic threough a non-combinatorial dihomogopy are in fact combinatorially dihomotopic, in a geometric -set. Moreover, we prove that in a geometric -set, the d-homotopy introdced in [M. Grandis (2003)] coincides with the dihomotopy in [L. Fajstrup, E. Goubault, M. Raussen (1999)]
Dihomotopy classes of dipaths in the geometric realization of a cubical set: from discrete to continuous and back again
Get PDFThe geometric models of concurrency - Dijkstra's PV-models and V. Pratt's Higher Dimensional Automata - rely on a translation of discrete or algebraic information to geometry. In both these cases, the translation is the geometric realisation of a semi cubical complex, which is then a locally partially ordered space, an lpo space. The aim is to use the algebraic topology machinery, suitably adapted to the fact that there is a preferred time direction. Then the results - for instance dihomotopy classes of dipaths, which model the number of inequivalent computations should be used on the discrete model and give the corresponding discrete objects. We prove that this is in fact the case for the models considered: Each dipath is dihomotopic to a combinatorial dipath and if two combinatorial dipaths are dihomotopic, then they are combinatorially equivalent. Moreover, the notions of dihomotopy (LF., E. Goubault, M. Raussen) and d-homotopy (M. Grandis) are proven to be equivalent for these models - hence the Van Kampen theorem is available for dihomotopy. Finally we give an idea of how many spaces have a local po-structure given by cubes. The answer is, that any cubicalized space has such a structure after at most one subdivision. In particular, all triangulable spaces have a cubical local po-structure.The geometric models of concurrency - Dijkstra's PV-models and V. Pratt's Higher Dimensional Automata - rely on a translation of discrete or algebraic information to geometry. In both these cases, the translation is the geometric realisation of a semi cubical complex, which is then a locally partially ordered space, an lpo space. The aim is to use the algebraic topology machinery, suitably adapted to the fact that there is a preferred time direction. Then the results - for instance dihomotopy classes of dipaths, which model the number of inequivalent computations should be used on the discrete model and give the corresponding discrete objects. We prove that this is in fact the case for the models considered: Each dipath is dihomotopic to a combinatorial dipath and if two combinatorial dipaths are dihomotopic, then they are combinatorially equivalent. Moreover, the notions of dihomotopy (LF., E. Goubault, M. Raussen) and d-homotopy (M. Grandis) are proven to be equivalent for these models - hence the Van Kampen theorem is available for dihomotopy. Finally we give an idea of how many spaces have a local po-structure given by cubes. The answer is, that any cubicalized space has such a structure after at most one subdivision. In particular, all triangulable spaces have a cubical local po-structure
Classification of dicoverings
Get PDFThe dicoverings of a "well pointed" d-space are classified as quotients of the universal dicovering space under congruence relations. We prove that the subcategory of d-spaces generated by the subcategory of directed cubes is equal to the category generated by the interval and the directed interval. Similarly, the category of topological spaces generated by simplices may be generated by the interval.The dicoverings of a "well pointed" d-space are classified as quotients of the universal dicovering space under congruence relations. We prove that the subcategory of d-spaces generated by the subcategory of directed cubes is equal to the category generated by the interval and the directed interval. Similarly, the category of topological spaces generated by simplices may be generated by the interval
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
