Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-09T21:53:34.419Z Has data issue: false hasContentIssue false

Trace spaces of directed tori with rectangular holes

Published online by Cambridge University Press:  17 June 2013

LISBETH FAJSTRUP*
Affiliation:
Department of Mathematical Sciences, Aalborg University, Fredrik Bajers Vej 7G2-117, DK-9220 Aalborg ∅, Denmark Email: [email protected]

Abstract

Raussen (2010) gave the trace space, which corresponds to the executions of parallel non-looped, non-branching processes as a prod-simplicial complex derived from a poset. The connected components represent equivalent executions. For looped processes, the state space is a torus and the trace space is a disjoint union of trace spaces of deloopings. In the current paper, we develop the index poset for the trace space of the deloopings from the once delooped case. When just one process is looped, the index poset is generated as words in a regular language. We also construct a corresponding automaton.

Type
Paper
Copyright
Copyright © Cambridge University Press 2013 

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.)

References

Dijkstra, E. W.Cooperating Sequential Processes, Academic Press.CrossRefGoogle Scholar
Fajstrup, L. (2003) Dicovering spaces. Homology Homotopy and Applications 5 (2)117.CrossRefGoogle Scholar
Fajstrup, L., Goubault, E., Haucourt, E., Mimram, S. and Raussen, M. (2012) Trace spaces: An efficient new technique for state-space reduction. In: Seidl, H. (ed.) Programming Languages and Systems. 21st European Symposium on Programming, ESOP 2012. Springer-Verlag Lecture Notes in Computer Science 7211274294.Google Scholar
Fajstrup, L., Goubault, E. and Raussen, M. (2006) Algebraic topology and concurrency. Theoretical Computer Science 357 241278.CrossRefGoogle Scholar
Hopcroft, J. E. and Ullman, J. D. (1979) Introduction to Automata Theory, Languages and Computation, Addison-Wesley.Google Scholar
Raussen, M. (2007) Invariants of directed spaces. Applied Categorical Structures 15 355386.CrossRefGoogle Scholar
Raussen, M. (2010) Simplicial models of trace spaces. Algebraic and Geometric Topology 10 16831714.CrossRefGoogle Scholar