Algebraic and Regular Trees

Courcelle, B.

Courcelle, B.

Publications du Département de mathématiques (Lyon), Compte rendu des journées infinitistes, no. 2B (1985), pp. 91-95.

EuDML

@article{PDML_1985___2B_91_0,
     author = {Courcelle, B.},
     title = {Algebraic and {Regular} {Trees}},
     journal = {Publications du D\'epartement de math\'ematiques (Lyon)},
     pages = {91--95},
     publisher = {Universit\'e Claude Bernard - Lyon 1},
     number = {2B},
     year = {1985},
     language = {en},
     url = {http://archive.numdam.org/item/PDML_1985___2B_91_0/}
}

TY  - JOUR
AU  - Courcelle, B.
TI  - Algebraic and Regular Trees
JO  - Publications du Département de mathématiques (Lyon)
PY  - 1985
SP  - 91
EP  - 95
IS  - 2B
PB  - Université Claude Bernard - Lyon 1
UR  - http://archive.numdam.org/item/PDML_1985___2B_91_0/
LA  - en
ID  - PDML_1985___2B_91_0
ER  -

%0 Journal Article
%A Courcelle, B.
%T Algebraic and Regular Trees
%J Publications du Département de mathématiques (Lyon)
%D 1985
%P 91-95
%N 2B
%I Université Claude Bernard - Lyon 1
%U http://archive.numdam.org/item/PDML_1985___2B_91_0/
%G en
%F PDML_1985___2B_91_0

Courcelle, B. Algebraic and Regular Trees. Publications du Département de mathématiques (Lyon), Compte rendu des journées infinitistes, no. 2B (1985), pp. 91-95. http://archive.numdam.org/item/PDML_1985___2B_91_0/

Bibliographie
Cité par

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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 | Zbl

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

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

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

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

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

[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

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

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

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

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

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

[48] G. Huet, Résolution d’équations dans les langages d’ordre 1, 2, ... $ω$ , 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 | Zbl

[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 | Zbl

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

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

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

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

[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

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

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

[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 | Zbl

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

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

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

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

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

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

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

[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

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

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

[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

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

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

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

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

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

[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 | Zbl

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

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

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

[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

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

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