×

Définitions récursives par cas. (French) Zbl 0562.68004

The authors study a class of recursive definitions which do not use explicitly the if...then...else construction. The approach, related to some constructs in PROLOG, is focused to non-deterministic programs producing a unique result and to the so-called semi-interpretation (which pertains only the left-hand side of assertions).
Reviewer: C.Calude

MSC:

68N01 General topics in the theory of software
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] 1. S. BLOOM et R. TINDELL, Varieties of if Then-else, Siam J. Comput. vol. 12, 1983, p. 677-707. Zbl0518.68010 MR721007 · Zbl 0518.68010 · doi:10.1137/0212047
[2] 2. G. BOUDOL, Calculs maximaux et sémantique opérationnelle des programmes non déterministes, Thèse doctorat, Université de Paris-7, 1980.
[3] 3. B. COURCELLE, Infinite Trees in Normal Form and Recursive Equations having a Unique Solution, Math. Systems Theory, vol. 13, 1979, p. 131-180. Zbl0418.68013 MR553879 · Zbl 0418.68013 · doi:10.1007/BF01744293
[4] 4. B. COURCELLE, Fundamental Properties of Infinite Trees, Theor. Comput. Sc., vol. 25, 1984, p. 95-169. Zbl0521.68013 MR693076 · Zbl 0521.68013 · doi:10.1016/0304-3975(83)90059-2
[5] 5. B. COURCELLE, An Axiomatic Approach to the Korenjak-Hopcroft Algorithms, Math. Systems Theory, vol. 16, 1983, p. 191-231. Zbl0581.68032 MR702448 · Zbl 0581.68032 · doi:10.1007/BF01744577
[6] 6. B. COURCELLE et P. FRANCHI-ZANNETTACCI, Attribute Grammars and Recursive Program Schemes, Theor. Comput. Sc., vol. 17, 1982, p. 163-191 and p. 235-257. Zbl0481.68068 · Zbl 0481.68068 · doi:10.1016/0304-3975(82)90003-2
[7] 7. B. COURCELLE et F. LAVANDIER, A Class of Program Schemes Based on Tree Rewriting Systems 8th C.A.A.P., L’Aquila, Lec. Notes Comp. Sc., Springer, vol.159, 1983, p. 191-204 Zbl0518.68015 MR744210 · Zbl 0518.68015
[8] 8. B. COURCELLE, M. NIVAT, The algebraic semantics of recursive program schemes: MFCS’78, Lec. Notes Comput. Sc., vol. 64, p. 16-30. Zbl0384.68016 MR519827 · Zbl 0384.68016
[9] 9. J. DARLINGTON, R. BURSTALL, A System which Automatically Improves Program, Acta Informatica, vol. 6, 1976, p. 41-60. Zbl0323.68008 · Zbl 0323.68008 · doi:10.1007/BF00263742
[10] 10. E. FRIEDMAN, Equivalence Problems for Deterministic Context-free Languages andMonadic Recursion Schemes, J. Comput. System Sc., 14, 1977, p. 334-359. Zbl0358.68109 MR443445 · Zbl 0358.68109 · doi:10.1016/S0022-0000(77)80019-6
[11] 11. S. GARLAND et D. LUCKHAM, Program Schemes, Recursion Schemes and Formal Languages, J. Comput. System Sc., vol.7, 1973, p. 119-160. Zbl0277.68010 MR315930 · Zbl 0277.68010 · doi:10.1016/S0022-0000(73)80040-6
[12] 12. J. GOGUEN, J. THATCHER, E. WAGNER et J. WRIGHT, Initial Algebra Semantics and Continuons Algebras, J. Assoc. Comput. Mach., vol. 24, 1977, p. 68-95. Zbl0359.68018 MR520711 · Zbl 0359.68018 · doi:10.1145/321992.321997
[13] 13. I. GUESSARIAN, Algebraic Semantics, Lec. Notes Comput. Sc., vol. 99, Springer-Verlag, 1981. Zbl0474.68010 MR617908 · Zbl 0474.68010
[14] 14. G. HUET, Confluent Reductions, Abstract Properties and Applications to Term Rewriting Systems, J. Assoc. Comput. Mach., vol. 27, 1980, p. 797-821. Zbl0458.68007 MR594700 · Zbl 0458.68007 · doi:10.1145/322217.322230
[15] 15. G. HUET et J. M. HULLOT, Proofs by induction in Equational Theories with Constructors, I. Compt. System Sc., Vol. 25, 1982, p. 239-266. Zbl0532.68041 MR680519 · Zbl 0532.68041 · doi:10.1016/0022-0000(82)90006-X
[16] 16. G. HUET et B. LANG, Proving and Applyind Program Transformations Expressed with 2nd Order Patterns, Acta Informatica, vol.11, 1978, p. 31-55. Zbl0389.68008 MR514752 · Zbl 0389.68008 · doi:10.1007/BF00264598
[17] 17. G. HUET et J. J. LEVY, Call by Need Computations in Nonambigous Linear Term Rewriting System, Laboria report, vol. 359, 1979.
[18] 18. G. HUET et D. OPPEN, Equations and Rewrite Rules, a Survey, Proceedings of the International Symposium on Formal Languages Theory, Santa Barbara, California (December 10-14, 1979),
[19] 19. F. LAVANDIER, Sur les systèmes de définitions récursives par cas. Application à la sémantique dénotationnelle, Thèse de 3e cycle, Université de Bordeaux-I, 1982.
[20] 20. Z. MANNA, A. SHAMIR, The Theoretical Aspects of the Optimal Fixedpoint, S.I.A.M., J. Comput., vol. 5, 1976, p. 414-426. Zbl0358.68017 MR440995 · Zbl 0358.68017 · doi:10.1137/0205033
[21] 21. B. MAYOH, Attribute Grammars and Mathematical Semantics; S.I.A.M. J. Comput., vol. 10, 1981, p. 503-518. Zbl0462.68062 MR623062 · Zbl 0462.68062 · doi:10.1137/0210037
[22] 22. M. NIVAT, On the Interpretation of Polyadic Recursive Program Schemes, Symposia Mathematica, vol.15, Academic Press, 1975, p. 255-281. Zbl0346.68041 MR391563 · Zbl 0346.68041
[23] 23. J. C. RAOULT et J. VUILLEMIN, Operational and Semantic Equivalence between Recursive Programs, J. Assoc. Comput. Mach., vol. 27, 1980, p. 772-796. Zbl0447.68004 MR594699 · Zbl 0447.68004 · doi:10.1145/322217.322229
[24] 24. B. ROSEN, Tree Manipulation Systems and Church-Rosser Theorems, J. Assoc. Comput. Mach., vol. 20, 1973, p. 160-187. Zbl0267.68013 MR331850 · Zbl 0267.68013 · doi:10.1145/321738.321750
[25] 25. J. STOY, Semantic models, in Theoretical Foundations of Programming Methodology, M. BROY and G. SCHMIDT, éd., D. Reidel Pub. Co., Dordrecht, Holland, 1982, p. 293-325. Zbl0513.68072 MR696964 · Zbl 0513.68072
[26] 26. R. TENNENT, The denotational Semantics of Programming Languages, Comm. of A.C.M., vol.19-8, 1976, p.437-453. Zbl0337.68010 MR428771 · Zbl 0337.68010 · doi:10.1145/360303.360308
[27] 27. S. WALKER et H. STRONG, Characterizations of Flow-chartable Recursions, J. Comput. System Sc., vol. 7, 1973, p. 404-447. Zbl0266.68011 MR331854 · Zbl 0266.68011 · doi:10.1016/S0022-0000(73)80032-7
[28] 28. J. ENGELFRIET, Some Open Questions and Recent Results on Tree Transducers and Tree Languages, même volume que [18]
[29] 29. P. FRANCHI-ZANNETTACCI, Attributs sémantiques et schémas de programmes, Thèse d’État, Université de Bordeaux-I, 1982.
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.