Algebraic and Regular Trees

Courcelle, B.

Publications du Département de mathématiques (Lyon), (1985), p. 91-95 / Harvested from Numdam

Détail

Publié le : 1985-01-01

Bibliographie

[1] A. Arnold and M. Dauchet, Théorie des magmoïdes, RAIRO Inform. Théor. 12 (1978) 235-257. | Numdam | MR 510640 | Zbl 0391.68037

[2] A. Arnold and M. Nivat, Metric interpretations of infinite trees and semantics of non deterministic recursive programs, Theoret. Comput, Sci. 11 (1980) 181-205. | MR 572215 | Zbl 0427.68022

[3] A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties, Fund. Inform. III. 4 (1980) 445-476. | MR 604273 | Zbl 0453.68021

[4] H. Bekic, Definable operations in general algebras, and the theory of automata and flowcharts, Unpublished work, IBM Laboratory, Vienna (1969).

[5] S. Bloom, All solutions of a system of recursion equations in infinite trees and other contraction theories, J. Comput. System Sci., to appear. | MR 731317 | Zbl 0535.68006

[6] S. Bloom and C. Elgot, The existence and construction of free iterative theories, J. Comput. System Sci. 12 (1976) 305-318. | MR 505399 | Zbl 0333.68017

[7] S. Bloom, C. Elgot and J. Wright, Solutions of the iteration equation and extensions of the scalar iteration operation, SIAM J. Comput. 9 (1980) 25-45. | MR 557823 | Zbl 0454.18011

[8] S. Bloom, S. Ginali and J. Rutledge, Scalar and vector iteration, J. Comput. System Sci. 14 (1977) 251-256. | MR 480681 | Zbl 0358.68072

[9] S. Bloom and D. Patterson, Easy solutions are hard to find, Proc. 6th Colloquium on Trees in Algebra and Programming, Lecture Notes in Computer Science 112 (Springer, Berlin, 1981) 135-146. | MR 623269 | Zbl 0461.68046

[10] S. Bloom and R. Tindell, Compatible orderings on the metric theory of trees, SIAM J. Comput. 9 (1980) 683-691. | MR 592759 | Zbl 0447.05026

[11] S. Bloom and R. Tindell, Varieties of if-then-else, Submitted for publication (1981). | Zbl 0518.68010

[12] R. Book, The undecidability of a word problem : on a conjecture of Strong, Maggiolo-Schettini and Rosen, Inform. Process Lett. 12 (1981) 121-122. | MR 618920 | Zbl 0457.03036

[13] P. Casteran, Structures de contrôle : définitions opérationnelles et algébriques, Thèse de 3ème cycle, University Paris-7 (1979).

[14] B. Courcelle, On jump-deterministic pushdown automata, Math. Systems Theory 11 (1977) 87-109. | MR 464717 | Zbl 0365.02021

[15] B. Courcelle, A representation of trees by languages, Theoret. Comput. Sci. 6 (1978) 255-279 and 7 (1978) 25-55. | Zbl 0377.68040

[16] B. Courcelle, Frontiers of infinite trees, RAIRO Inform. Théor. 12 (1978) 319-337. | Numdam | MR 517634 | Zbl 0411.68065

[17] B. Courcelle, Arbres infinis et systèmes d'équations, RAIRO Inform. Théor. 13 (1979) 31-48. | Numdam | MR 525456 | Zbl 0406.68017

[18] B. Courcelle, Infinite trees in normal form and recursive equations having a unique solution, Math. Systems Theory 13 (1979) 131-180. | MR 553879 | Zbl 0418.68013

[19] B. Courcelle, An axiomatic approach to the Korenjak-Hopcroft algorithms, Math. Systems Theory, to appear. | MR 702448 | Zbl 0581.68032

[20] B. Courcelle, Work in preparation.

[21] B. Courcelle and P. Franchi-Zannettacci, On the equivalence problem for attribute systems, Information and Control, to appear. | MR 707578 | Zbl 0529.68005

[22] B. Courcelle and I. Guessarian, On some classes of interpretations, J. Comput. System Sci. 17 (1978) 388-413. | MR 516846 | Zbl 0392.68009

[23] B. Courcelle, G. Kahn and J. Vuillemin, Algorithmes d'équivalence et de réduction à des expressions minimales dans une classe d'équations récursives simples, Proc. 2nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 14 (Springer, Berlin, 1974) 200-213. | MR 428778 | Zbl 0285.68022

[24] B. Courcelle and M. Nivat, Algebraic families of interpretations, Proc. Annual Symposium on Foundations of Computer Science, Houston, TX (1976) 137-146. | MR 451817

[25] B. Courcelle and M. Nivat, The algebraic semantics of recursive program schemes, in : Mathematical Foundations of Computer Science 78, Lecture Notes in Computer Science 64 (Springer, Berlin 1978) 16-30. | MR 519827 | Zbl 0384.68016

[26] B. Courcelle and J.C. Raoult, Completions of ordered magmas, Fund. Inform. III.1 (1980) 105-116. | MR 588060 | Zbl 0463.06005

[27] B. Courcelle and J. Vuillemin, Completeness results for the equivalence of recursive schemes, J. Comput. System Sci. 12 (1976) 179-197. | MR 411225 | Zbl 0342.68008

[28] G. Cousineau, La programmation en EXEL, Rev. Tech. Thomson-CSF 10 (1978) 209-234.

G. Cousineau, La programmation en EXEL, Rev. Tech. Thomson-CSF 11 (1979) 13-35.

[29] G. Cousineau, An algebraic definition for control structures, Theoret. Comput. Sci. 12 (1980, 175-192. | MR 585111 | Zbl 0456.68015

[30] W. Damm, The IO- and OI-hicrarchies, Theoret. Comput. Sci. 20 (1982) 95-207. | MR 666544 | Zbl 0478.68012

[31] W. Damm, E. Fehr and K. Indermark, Higher type recursion and self-application as control structures, in : E. Neuhold, Ed., Formal Descriptions of Programming Concepts (North-Holland, Amsterdam, 1978) 461-487. | MR 537917 | Zbl 0373.68021

[32] C. Elgot, Monadic computation and iterative algebraic theories, in : H.E. Rose, Ed., Logic Colloquium 73 (North-Holland, Amsterdam, 1975) 175-230. | MR 413584 | Zbl 0327.02040

[33] C. Elgot, Structured programming with and without GOTO statements, IEEE Trans. Software Engrg. 2 (1976) 41-54. | MR 433942 | Zbl 0348.68008

[34] C. Elgot, S. Bloom and R. Tindell, The algebraic structure of rooted trees, J. Comput. System Sci. 16 (1978) 362-399. | MR 496954 | Zbl 0389.68007

[35] J. Engelfriet and E. Schmidt, IO and OI, J. Comput. System Sci. 15 (1977) 328-361. | MR 502290 | Zbl 0366.68053

J. Engelfriet and E. Schmidt, IO and OI, J. Comput. System Sci. 16 (1978) 67-99. | MR 502291 | Zbl 0371.68020

[36] P. Enjalbert, Systèmes de déductions pour les arbres et les schémas de programmes, RAIRO Inform. Théor. 14 (1980) 247-278. | Numdam | MR 593490 | Zbl 0441.68007

P. Enjalbert, Systèmes de déductions pour les arbres et les schémas de programmes, RAIRO Inform. Théor. 15 (1981) 3-21. | Numdam | MR 610943 | Zbl 0464.68019

[37] J. Gallier, DPDA's in atomic normal form and applications to the equivalence problems, Theoret. Comput. Sci. 14 (1981) 155-186. | MR 614414 | Zbl 0474.68065

[38] J. Gallier, Recursion closed algebraic theories, J. Comput. System Sci., to appear. | MR 636181 | Zbl 0472.68006

[39] J. Gallier, N-rational algebras, I : Basic Properties and free algebras, II : Varieties and the logic of inequalities, Submitted for publication. | Zbl 0554.68018

[40] S. Ginali, Regular trees and the free iterative theory, J. Comput. System Sci. 18 (1979) 228-242. | MR 536398 | Zbl 0495.68042

[41] J. Goguen, J. Thatcher. E. Wagner and J. Wright, Initial algebra semantics and continuous algebras, J. ACM 24 (1977) 68-95. | MR 520711 | Zbl 0359.68018

[42] S. Gorn, Explicit definitions and linguistic dominoes, in : J. Hart and S. Takasu, Eds., Systems and Computer Science (University of Toronto Press, 1967) 77-105. | MR 237245

[43] I. Guessarian, Program transformations and algebraic semantics, Theoret. Comput. Sci. 9 (1979) 39-65. | MR 535123 | Zbl 0399.68023

[44] I. Guessarian, Algebraic Semantics, Lecture Notes in Computer Science 99 (Springer, Berlin, 1981). | MR 617908 | Zbl 0474.68010

[45] M. Harrison, Introduction to Formal Language Theory (Addison-Wesley, Reading, MA, 1978). | MR 526397 | Zbl 0411.68058

[46] M. Harrison, I. Havel and A. Yehudai, On equivalence of grammars through transformation trees, Theoret. Comput. Sci. 9 (1979) 173-205. | MR 540555 | Zbl 0409.68041

[47] S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words, RAIRO Inform. Theor. 13 (1979) 131-141. | Numdam | MR 581673 | Zbl 0433.68062

[48] G. Huet, Résolution d’équations dans les langages d’ordre 1, 2, ...$\omega $, Doctoral dissertation, University Paris-7 (1976).

[49] G. Huet, Confluent reductions : abstract properties and applications to term rewriting systems, J. ACM 27 (1980) 797-821. | MR 594700 | Zbl 0458.68007

[50] J. Leszczylowski, A theorem on resolving equations in the space of languages, Bull. Acad. Polon. Sci., Ser. Sci. Math. Astronom. Phys. 19 (1979) 967-970. | MR 312778 | Zbl 0242.68034

[51] G. Markowsky and B. Rosen, Bases for chain-complete posets, IBM J. Res. Develop. 20 (1976) 138-147. | MR 392706 | Zbl 0329.06001

[52] J. Mycielski and W. Taylor, A compactification of the algebra of terms, Algebra Universalis 6 (1976) 159-163. | MR 434922 | Zbl 0358.08001

[53] M. Nivat, On the interpretation of recursive polyadic program schemes, Symposia Mathematica 15 (Academic Press, New York, 1975) 255-281. | MR 391563 | Zbl 0346.68041

[54] M. Nivat, Mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor. 11 (1977) 311-327. | Numdam | MR 468353 | Zbl 0371.68025

[55] M. Nivat, Private communication.

[56] L. Nolin and G. Ruggin, A formalization of EXEL, Proc. ACM Symposium on Principles of Programming Languages, Boston (1973). | Zbl 0308.68011

[57] M. O'Donnell, Computing in Systems Described by Equations, Lecture Notes in Computer Science 58 (Springer, Berlin, 1977). | MR 483644 | Zbl 0421.68038

[58] M. Oyamaguchi and N. Honda, The decidability of the equivalence for deterministic stateless pushdown automata, Information and Control 38 (1978) 367-376. | MR 509559 | Zbl 0393.68078

[59] M. Oyamaguchi, N. Honda and Y. Inagaki, The equivalence problem for real-time strict deterministic languages, Information and Control 45 (1980) 90-115. | MR 582147 | Zbl 0444.68038

[60] M. Paterson and M. Wegman, Linear unification, J. Comput. System Sci. 16 (1978) 158-167. | MR 483794 | Zbl 0371.68013

[61] J. Robinson, A machine-oriented logic based on the resolution principle, J. ACM 12 (1965) 23-41. | MR 170494 | Zbl 0139.12303

[62] B. Rosen, Tree-manipulating systems and Church-Rosser theorems, J. ACM 20 (1973) 160-187. | MR 331850 | Zbl 0267.68013

[63] B. Rosen, Program equivalence and context-free grammars, J. Comput. System Sci. 11 (1975) 358-374. | MR 423889 | Zbl 0315.68063

[64] M. Schützenberger, On context-free languages and push-down automata. Information and Control 6 (1963) 246-264. | MR 163809 | Zbl 0123.12502

[65] J. Tiuryn, Fixed points and algebras with infinitely long expressions, Fund. Inform. II (1978) 107-128. | Zbl 0401.68062

[65] J. Tiuryn, Fixed points and algebras with infinitely long expressions, Fund. Inform. II (1979) 317-335. | MR 573994 | Zbl 0436.68015

[66] J. Tiuryn, On a connection between regular algebras and rational algebraic theories, Proc. 2nd Workshop on Categorical and Algebraic Methods in Computer Science and System Theory, Dortmund, West Germany (1978). | Zbl 0465.68022

[67] J. Tiuryn, Unique fixed points vs. least fixed points, Report 49, RWTH Aachen, West Germany (1978). | Zbl 0439.68026

[68] L. Valiant, The equivalence problem for deterministic finite-turn push-down automata. Information and Control 25 (1974) 123-133. | MR 391591 | Zbl 0285.68025

[69] J. Wright, J. Thatcher, E. Wagner and J. Goguen, Rational algebraic theories and fixed-point solutions, Proc. 17th Symposium on Foundations of Computer Science, Houston, TX (1976) 147-158. | MR 478727

[70] J. Wright, E. Wagner and J. Thatcher, A uniform approach to inductive posets and inductive closure, Theoret. Comput. Sci. 7 (1978) 57-77. | MR 480224 | Zbl 0732.06001

[1] H. Barendregt. The Lambda-Calculus, Studies in Logic 103 (North-Holland, Amsterdam, 1981). | MR 622912 | Zbl 0467.03010

[2] S. Bloom and C. Elgot, The existence and construction of free iterative theories. J. Comput. System Sci. 12 (1976) 305-318. | MR 505399 | Zbl 0333.68017

[3] R. Cohen, Star-height of certain families of regular events. J. Comput. System Sci. 4 (1970) 281-297. | MR 294059 | Zbl 0245.94039

[4] R. Cohen, Techniques for establishing star-height of regular sets. Math. Systems Theory 5 (1971) 97-114. | MR 441581 | Zbl 0218.94028

[5] R. Cohen, Rank non-increasing transformations on transition graphs, Inform. and Control 20 (1972) 93-113. | MR 381887 | Zbl 0237.94020

[6] R. Cohen and J. Brzozowski, General properties of star-height of regular events, J. Comput. System Sci. 4 (1970) 260-280. | MR 294058 | Zbl 0245.94038

[7] B. Courcelle, A representation of trees by languages Part I, Theoret. Comput. Sci. 6 (1978) 255-279 ; Part II, Theoret. Comput. Sci. 7 (1978) 25-55. | MR 495226 | Zbl 0377.68040

[8] B. Courcelle, Fundamental properties of infinite trees. Theoret. Comput. Sci. 25 (1983) 95-169. | MR 693076 | Zbl 0521.68013

[9] G. Cousineau, An algebraic definition for control structures, Theoret. Comput. Sci. 12 (1980) 175-192. | MR 585111 | Zbl 0456.68015

[10] L. Eggan, Transition graphs and the star-height of regular events, Michigan Math. J. 10 (1963) 385-397. | MR 157840 | Zbl 0173.01504

[11] S. Eilenberg, Automata. Languages and Machines, Vol. A (Academic Press, New York. 1974). | MR 530382 | Zbl 0359.94067

[12] C. Elgot, Monadic computations and iterative algebraic theories, in : H.E. Rose, ed.. Logic Colloquium 73 (North-Holland, Amsterdam, 1975) pp. 175-230. | MR 413584 | Zbl 0327.02040

[13] C. Elgot, S. Bloom and R. Tindell, The algebraic structure of rooted trees, J. Comput. System Sci. 16 (1978) 362-399. | MR 496954 | Zbl 0389.68007

[14] S. Ginali, Regular trees and the free iterative theory, J. Comput. System Sci. 18 (1979) 228-242. | MR 536398 | Zbl 0495.68042

[15] G. Huet, Confluent reductions : abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach 27 (1980) 797-821. | MR 594700 | Zbl 0458.68007

[16] G. Jacob, Calcul du rang des arbres infinis réguliers, Proc. CAAP' 81, Lecture Notes Comput. Sci. 112 (Springer, Berlin, 1981) pp. 238-254. | MR 623276

[17] R. Mcnaughton, The loop complexity of pure-group events, Inform. Control 11 (1967) 167-176. | MR 249218 | Zbl 0166.26905

[18] R. Mcnaughton, The loop complexity of regular events, Inform. Sci. 1 (1969) 305-328. | MR 249219