Algebraic and Regular Trees

 Access to full text

 Full (PDF)

1. [1] A. Arnold and M. Dauchet, Théorie des magmoïdes, RAIRO Inform. Théor.12 (1978) 235-257. Zbl0391.68037MR510640
2. [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. Zbl0427.68022MR572215
3. [3] A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties, Fund. Inform.III. 4 (1980) 445-476. Zbl0453.68021MR604273
4. [4] H. Bekic, Definable operations in general algebras, and the theory of automata and flowcharts, Unpublished work, IBM Laboratory, Vienna (1969). 
5. [5] S. Bloom, All solutions of a system of recursion equations in infinite trees and other contraction theories, J. Comput. System Sci., to appear. Zbl0535.68006MR731317
6. [6] S. Bloom and C. Elgot, The existence and construction of free iterative theories, J. Comput. System Sci.12 (1976) 305-318. Zbl0333.68017MR505399
7. [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. Zbl0454.18011MR557823
8. [8] S. Bloom, S. Ginali and J. Rutledge, Scalar and vector iteration, J. Comput. System Sci.14 (1977) 251-256. Zbl0358.68072MR480681
9. [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 Science112 (Springer, Berlin, 1981) 135-146. Zbl0461.68046MR623269
10. [10] S. Bloom and R. Tindell, Compatible orderings on the metric theory of trees, SIAM J. Comput.9 (1980) 683-691. Zbl0447.05026MR592759
11. [11] S. Bloom and R. Tindell, Varieties of if-then-else, Submitted for publication (1981). Zbl0518.68010
12. [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. Zbl0457.03036MR618920
13. [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. [14] B. Courcelle, On jump-deterministic pushdown automata, Math. Systems Theory11 (1977) 87-109. Zbl0365.02021MR464717
15. [15] B. Courcelle, A representation of trees by languages, Theoret. Comput. Sci.6 (1978) 255-279 and 7 (1978) 25-55. Zbl0377.68040
16. [16] B. Courcelle, Frontiers of infinite trees, RAIRO Inform. Théor.12 (1978) 319-337. Zbl0411.68065MR517634
17. [17] B. Courcelle, Arbres infinis et systèmes d'équations, RAIRO Inform. Théor.13 (1979) 31-48. Zbl0406.68017MR525456
18. [18] B. Courcelle, Infinite trees in normal form and recursive equations having a unique solution, Math. Systems Theory13 (1979) 131-180. Zbl0418.68013MR553879
19. [19] B. Courcelle, An axiomatic approach to the Korenjak-Hopcroft algorithms, Math. Systems Theory, to appear. Zbl0581.68032MR702448
20. [20] B. Courcelle, Work in preparation. 
21. [21] B. Courcelle and P. Franchi-Zannettacci, On the equivalence problem for attribute systems, Information and Control, to appear. Zbl0529.68005MR707578
22. [22] B. Courcelle and I. Guessarian, On some classes of interpretations, J. Comput. System Sci.17 (1978) 388-413. Zbl0392.68009MR516846
23. [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 Science14 (Springer, Berlin, 1974) 200-213. Zbl0285.68022MR428778
24. [24] B. Courcelle and M. Nivat, Algebraic families of interpretations, Proc. Annual Symposium on Foundations of Computer Science, Houston, TX (1976) 137-146. MR451817
25. [25] B. Courcelle and M. Nivat, The algebraic semantics of recursive program schemes, in : Mathematical Foundations of Computer Science78, Lecture Notes in Computer Science64 (Springer, Berlin1978) 16-30. Zbl0384.68016MR519827
26. [26] B. Courcelle and J.C. Raoult, Completions of ordered magmas, Fund. Inform.III.1 (1980) 105-116. Zbl0463.06005MR588060
27. [27] B. Courcelle and J. Vuillemin, Completeness results for the equivalence of recursive schemes, J. Comput. System Sci.12 (1976) 179-197. Zbl0342.68008MR411225
28. [28] G. Cousineau, La programmation en EXEL, Rev. Tech. Thomson-CSF10 (1978) 209-234. 
29. G. Cousineau, La programmation en EXEL, Rev. Tech. Thomson-CSF11 (1979) 13-35. 
30. [29] G. Cousineau, An algebraic definition for control structures, Theoret. Comput. Sci.12 (1980, 175-192. Zbl0456.68015MR585111
31. [30] W. Damm, The IO- and OI-hicrarchies, Theoret. Comput. Sci.20 (1982) 95-207. Zbl0478.68012MR666544
32. [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. Zbl0373.68021MR537917
33. [32] C. Elgot, Monadic computation and iterative algebraic theories, in : H.E. Rose, Ed., Logic Colloquium73 (North-Holland, Amsterdam, 1975) 175-230. Zbl0327.02040MR413584
34. [33] C. Elgot, Structured programming with and without GOTO statements, IEEE Trans. Software Engrg.2 (1976) 41-54. Zbl0348.68008MR433942
35. [34] C. Elgot, S. Bloom and R. Tindell, The algebraic structure of rooted trees, J. Comput. System Sci.16 (1978) 362-399. Zbl0389.68007MR496954
36. [35] J. Engelfriet and E. Schmidt, IO and OI, J. Comput. System Sci.15 (1977) 328-361. Zbl0366.68053MR502290
37. J. Engelfriet and E. Schmidt, IO and OI, J. Comput. System Sci.16 (1978) 67-99. Zbl0371.68020MR502291
38. [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. Zbl0441.68007MR593490
39. P. Enjalbert, Systèmes de déductions pour les arbres et les schémas de programmes, RAIRO Inform. Théor.15 (1981) 3-21. Zbl0464.68019MR610943
40. [37] J. Gallier, DPDA's in atomic normal form and applications to the equivalence problems, Theoret. Comput. Sci.14 (1981) 155-186. Zbl0474.68065MR614414
41. [38] J. Gallier, Recursion closed algebraic theories, J. Comput. System Sci., to appear. Zbl0472.68006MR636181
42. [39] J. Gallier, N-rational algebras, I : Basic Properties and free algebras, II : Varieties and the logic of inequalities, Submitted for publication. Zbl0554.68018
43. [40] S. Ginali, Regular trees and the free iterative theory, J. Comput. System Sci.18 (1979) 228-242. Zbl0495.68042MR536398
44. [41] J. Goguen, J. Thatcher. E. Wagner and J. Wright, Initial algebra semantics and continuous algebras, J. ACM24 (1977) 68-95. Zbl0359.68018MR520711
45. [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. MR237245
46. [43] I. Guessarian, Program transformations and algebraic semantics, Theoret. Comput. Sci.9 (1979) 39-65. Zbl0399.68023MR535123
47. [44] I. Guessarian, Algebraic Semantics, Lecture Notes in Computer Science99 (Springer, Berlin, 1981). Zbl0474.68010MR617908
48. [45] M. Harrison, Introduction to Formal Language Theory (Addison-Wesley, Reading, MA, 1978). Zbl0411.68058MR526397
49. [46] M. Harrison, I. Havel and A. Yehudai, On equivalence of grammars through transformation trees, Theoret. Comput. Sci.9 (1979) 173-205. Zbl0409.68041MR540555
50. [47] S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words, RAIRO Inform. Theor.13 (1979) 131-141. Zbl0433.68062MR581673
51. [48] G. Huet, Résolution d’équations dans les langages d’ordre 1, 2, ...$\omega$, Doctoral dissertation, University Paris-7 (1976). 
52. [49] G. Huet, Confluent reductions : abstract properties and applications to term rewriting systems, J. ACM27 (1980) 797-821. Zbl0458.68007MR594700
53. [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. Zbl0242.68034MR312778
54. [51] G. Markowsky and B. Rosen, Bases for chain-complete posets, IBM J. Res. Develop.20 (1976) 138-147. Zbl0329.06001MR392706
55. [52] J. Mycielski and W. Taylor, A compactification of the algebra of terms, Algebra Universalis6 (1976) 159-163. Zbl0358.08001MR434922
56. [53] M. Nivat, On the interpretation of recursive polyadic program schemes, Symposia Mathematica15 (Academic Press, New York, 1975) 255-281. Zbl0346.68041MR391563
57. [54] M. Nivat, Mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor.11 (1977) 311-327. Zbl0371.68025MR468353
58. [55] M. Nivat, Private communication. 
59. [56] L. Nolin and G. Ruggin, A formalization of EXEL, Proc. ACM Symposium on Principles of Programming Languages, Boston (1973). Zbl0308.68011
60. [57] M. O'Donnell, Computing in Systems Described by Equations, Lecture Notes in Computer Science58 (Springer, Berlin, 1977). Zbl0421.68038MR483644
61. [58] M. Oyamaguchi and N. Honda, The decidability of the equivalence for deterministic stateless pushdown automata, Information and Control38 (1978) 367-376. Zbl0393.68078MR509559
62. [59] M. Oyamaguchi, N. Honda and Y. Inagaki, The equivalence problem for real-time strict deterministic languages, Information and Control45 (1980) 90-115. Zbl0444.68038MR582147
63. [60] M. Paterson and M. Wegman, Linear unification, J. Comput. System Sci.16 (1978) 158-167. Zbl0371.68013MR483794
64. [61] J. Robinson, A machine-oriented logic based on the resolution principle, J. ACM12 (1965) 23-41. Zbl0139.12303MR170494
65. [62] B. Rosen, Tree-manipulating systems and Church-Rosser theorems, J. ACM20 (1973) 160-187. Zbl0267.68013MR331850
66. [63] B. Rosen, Program equivalence and context-free grammars, J. Comput. System Sci.11 (1975) 358-374. Zbl0315.68063MR423889
67. [64] M. Schützenberger, On context-free languages and push-down automata. Information and Control6 (1963) 246-264. Zbl0123.12502MR163809
68. [65] J. Tiuryn, Fixed points and algebras with infinitely long expressions, Fund. Inform.II (1978) 107-128. Zbl0401.68062
69. [65] J. Tiuryn, Fixed points and algebras with infinitely long expressions, Fund. Inform.II (1979) 317-335. Zbl0436.68015MR573994
70. [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). Zbl0465.68022
71. [67] J. Tiuryn, Unique fixed points vs. least fixed points, Report 49, RWTH Aachen, West Germany (1978). Zbl0439.68026
72. [68] L. Valiant, The equivalence problem for deterministic finite-turn push-down automata. Information and Control25 (1974) 123-133. Zbl0285.68025MR391591
73. [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. MR478727
74. [70] J. Wright, E. Wagner and J. Thatcher, A uniform approach to inductive posets and inductive closure, Theoret. Comput. Sci.7 (1978) 57-77. Zbl0732.06001MR480224
75. [1] H. Barendregt. The Lambda-Calculus, Studies in Logic103 (North-Holland, Amsterdam, 1981). Zbl0467.03010MR622912
76. [2] S. Bloom and C. Elgot, The existence and construction of free iterative theories. J. Comput. System Sci.12 (1976) 305-318. Zbl0333.68017MR505399
77. [3] R. Cohen, Star-height of certain families of regular events. J. Comput. System Sci.4 (1970) 281-297. Zbl0245.94039MR294059
78. [4] R. Cohen, Techniques for establishing star-height of regular sets. Math. Systems Theory5 (1971) 97-114. Zbl0218.94028MR441581
79. [5] R. Cohen, Rank non-increasing transformations on transition graphs, Inform. and Control20 (1972) 93-113. Zbl0237.94020MR381887
80. [6] R. Cohen and J. Brzozowski, General properties of star-height of regular events, J. Comput. System Sci.4 (1970) 260-280. Zbl0245.94038MR294058
81. [7] B. Courcelle, A representation of trees by languagesPart I, Theoret. Comput. Sci.6 (1978) 255-279 ; Part II, Theoret. Comput. Sci.7 (1978) 25-55. Zbl0377.68040
82. [8] B. Courcelle, Fundamental properties of infinite trees. Theoret. Comput. Sci.25 (1983) 95-169. Zbl0521.68013MR693076
83. [9] G. Cousineau, An algebraic definition for control structures, Theoret. Comput. Sci.12 (1980) 175-192. Zbl0456.68015MR585111
84. [10] L. Eggan, Transition graphs and the star-height of regular events, Michigan Math. J.10 (1963) 385-397. Zbl0173.01504MR157840
85. [11] S. Eilenberg, Automata. Languages and Machines, Vol. A (Academic Press, New York. 1974). Zbl0359.94067MR530382
86. [12] C. Elgot, Monadic computations and iterative algebraic theories, in : H.E. Rose, ed.. Logic Colloquium 73 (North-Holland, Amsterdam, 1975) pp. 175-230. Zbl0327.02040MR413584
87. [13] C. Elgot, S. Bloom and R. Tindell, The algebraic structure of rooted trees, J. Comput. System Sci.16 (1978) 362-399. Zbl0389.68007MR496954
88. [14] S. Ginali, Regular trees and the free iterative theory, J. Comput. System Sci.18 (1979) 228-242. Zbl0495.68042MR536398
89. [15] G. Huet, Confluent reductions : abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach27 (1980) 797-821. Zbl0458.68007MR594700
90. [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. MR623276
91. [17] R. McNaughton, The loop complexity of pure-group events, Inform. Control11 (1967) 167-176. Zbl0166.26905MR249218
92. [18] R. McNaughton, The loop complexity of regular events, Inform. Sci.1 (1969) 305-328. MR249219