Name
Abstract | ||
|---|---|---|
We investigate mutual dependencies of subexpressions of computable expressions in orthogonal rewrite systems, and identify conditions for their independent concurrent computation. To this end, we introduce concepts familiar from ordinary Euclidean Geometry (such as basis, projection, distance, etc.) for reduction spaces. We show how a basis at an expression can be constructed so that any reduction starting from that expression can be decomposed as the sum of its projections on the axes of the basis. To make the concepts computationally more relevant, we relativize them w.r.t. stable sets of results (such as the set of normal forms, head-normal forms, and weak-head-normal forms, in the λ-calculus), and show that an optimal concurrent computation of an expression w.r.t. S consists of optimal computations of its S-independent subexpressions. All these results are obtained in the framework of Deterministic Family Structures, which are Abstract Reduction Systems with axiomatized residual and family relations on redexes, that model all orthogonal rewrite systems. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.tcs.2005.07.037 | Theor. Comput. Sci. |
Keywords | Field | DocType |
conflict-free reduction geometry,expression w,optimal computation,optimal concurrent computation,S-independent subexpressions,Abstract Reduction Systems,reduction space,independent concurrent computation,family relation,computable expression,Deterministic Family Structures | Concurrent computation,Discrete mathematics,Expression (mathematics),Euclidean geometry,Mathematics | Journal |
Volume | Issue | ISSN |
347 | 3 | Theoretical Computer Science |
Citations | PageRank | References |
2 | 0.35 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zurab Khasidashvili | 1 | 307 | 25.40 |
| John R. W. Glauert | 2 | 77 | 9.24 |