The geometry of orthogonal reduction spaces. (English) Zbl 1401.68137
Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 649-659 (1997).
Summary: We investigate mutual dependencies of subexpressions of a computable expression, in orthogonal rewrite systems, and identify conditions for their concurrent independent 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 for 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 more relevant computationally, we relativize them w.r.t. stable sets of results, 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 for Stable Deterministic Residual Structures, Abstract Reduction Systems with an axiomatized residual relation, which model all orthogonal rewrite systems.
For the entire collection see [Zbl 1369.68020].
For the entire collection see [Zbl 1369.68020].
MSC:
| 68Q42 | Grammars and rewriting systems |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
References:
| [1] | [AL94]Asperti A., Laneve C. Interaction Systems I: The theory of optimal reductions. MSCS 11:1-48, Cambridge University Press, 1993. |
| [2] | [Bar84]Barendregt H. P. The Lambda Calculus, its Syntax and Semantics. North-Holland, 1984. · Zbl 0551.03007 |
| [3] | [GK96]Glauert J.R.W., Khasidashvili Z. Relative normalization in deterministic residual structures. CAAP’96, Springer LNCS, vol. 1059, H. Kirchner, ed. 1996, p. 180-195. · Zbl 1508.68155 |
| [4] | [GLM92]Gonthier G., Lévy J.-J., Melliès P.-A. An abstract Standardisation theorem. In: Proc. of LICS 1992, p. 72-81. |
| [5] | [Hin69]Hindley R.J. An abstract form of the Church-Rosser theorem I. JSL, 34(4):545-560, 1969. · Zbl 0195.02102 |
| [6] | [HL91]Huet G., Lévy J.-J. Computations in Orthogonal Rewriting Systems. In: Computational Logic, Essays in Honor of Alan Robinson, J.-L. Lassez and G. Plotkin, eds. MIT Press, 1991, p. 394-443. |
| [7] | [KKSV94]Kennaway J. R., Klop J. W., Sleep M. R., de Vries F.-J. On the adequacy of Graph Rewriting for simulating Term Rewriting. ACM Transactions on Programming Languages and Systems, 16(3):493-523, 1994. |
| [8] | [Kha93]Khasidashvili Z. Optimal normalization in orthogonal term rewriting systems. In: Proc. of RTA’93, Springer LNCS, vol. 690, C. Kirchner, ed. Montreal, 1993, p. 243-258. · Zbl 1508.68162 |
| [9] | [Kha94]Khasidashvili Z. On higher order recursive program schemes. In: Proc. of CAAP’94, Springer LNCS, vol. 787, S. Tison, ed. Edinburgh, 1994, p. 172-186. · Zbl 0938.68643 |
| [10] | [KG96]Khasidashvili Z., Glauert J. R. W. Discrete normalization and Standardization in Deterministic Residual Structures. In proc. of ALP’96, Springer LNCS, vol. 1139, M. Hanus, M. Rodríguez-Artalejo, eds. 1996, p.135-149. · Zbl 1355.68139 |
| [11] | [KG97]Khasidashvili Z., Glauert J.R.W. Zig-zag, extraction and separable families in non-duplicating stable deterministic residual structures. Technical Report IR-420, Free University, February 1997. |
| [12] | [KG97a]Khasidashvili Z., Glauert J. R. W. Relating conflict-free transition and event models. Submitted. · Zbl 0942.68061 |
| [13] | [Klo80]Klop J. W. Combinatory Reduction Systems. Mathematical Centre Tracts n. 127, Amsterdam, 1980. · Zbl 0466.03006 |
| [14] | [Klo92]Klop J. W. Term Rewriting Systems. In: S. Abramsky, D. Gabbay, and T. Maibaum eds. Handbook of Logic in Computer Science, vol. II, Oxford U. Press, 1992, p. 1-116. |
| [15] | [Lév80]Lévy J.-J. Optimal reductions in the λ-calculus. In: To H. B. Curry: Essays on Combinatory Logic, Lambda-calculus and Formalizm, Hindley J. R., Seldin J. P. eds, Academic Press, 1980, p. 159-192. · Zbl 0469.03006 |
| [16] | [Mar92]Maranget L. La stratégie paresseuse. Thèse de l’Université de Paris VII, 1992. |
| [17] | [Mil92]Milner R. Functions as processes. MSCS 2(2):119-141, 1992. · Zbl 0773.03012 |
| [18] | [Mel96]Melliès P.-A. Description Abstraite des Systèmes de Réécriture. Thèse de l’Université Paris 7, 1996. |
| [19] | [Oos94]Van Oostrom V. Confluence for Abstract and Higher-Order Rewriting. Ph.D. Thesis, Free University, Amsterdam, 1994. |
| [20] | [Oos96]Van Oostrom V. Higher order families. In: Proc. of RTA’96, Springer LNCS, vol. 1103, Ganzinger, H., ed., 1996, p. 392-407. · Zbl 1503.68164 |
| [21] | [Raa96]van Raamsdonk F. Confluence and normalisation for higher-order rewriting. Ph.D. Thesis, Free University, Amsterdam, 1996. |
| [22] | [Sta89]Stark E. W. Concurrent transition systems. J. TCS, 64(3):221-270, 1989. · Zbl 0671.68027 |
| [23] | [Win89]Winskel G. An introduction to Event Structures. Springer LNCS, vol. 354, 1989, p. 364-397. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
