@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://www.numdam.org/item/PDML_1985___2B_91_0/} }
Courcelle, B. Algebraic and Regular Trees. Publications du Département de mathématiques (Lyon), no. 2B (1985), pp. 91-95. http://www.numdam.org/item/PDML_1985___2B_91_0/
[1] Théorie des magmoïdes, RAIRO Inform. Théor. 12 (1978) 235-257. | Numdam | MR | Zbl
and ,[2] Metric interpretations of infinite trees and semantics of non deterministic recursive programs, Theoret. Comput, Sci. 11 (1980) 181-205. | MR | Zbl
and ,[3] The metric space of infinite trees. Algebraic and topological properties, Fund. Inform. III. 4 (1980) 445-476. | MR | Zbl
and ,[4] Definable operations in general algebras, and the theory of automata and flowcharts, Unpublished work, IBM Laboratory, Vienna (1969).
,[5] All solutions of a system of recursion equations in infinite trees and other contraction theories, J. Comput. System Sci., to appear. | MR | Zbl
,[6] The existence and construction of free iterative theories, J. Comput. System Sci. 12 (1976) 305-318. | MR | Zbl
and ,[7] Solutions of the iteration equation and extensions of the scalar iteration operation, SIAM J. Comput. 9 (1980) 25-45. | MR | Zbl
, and ,[8] Scalar and vector iteration, J. Comput. System Sci. 14 (1977) 251-256. | MR | Zbl
, and ,[9] 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
and ,[10] Compatible orderings on the metric theory of trees, SIAM J. Comput. 9 (1980) 683-691. | MR | Zbl
and ,[11] Varieties of if-then-else, Submitted for publication (1981). | Zbl
and ,[12] 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] Structures de contrôle : définitions opérationnelles et algébriques, Thèse de 3ème cycle, University Paris-7 (1979).
,[14] On jump-deterministic pushdown automata, Math. Systems Theory 11 (1977) 87-109. | MR | Zbl
,[15] A representation of trees by languages, Theoret. Comput. Sci. 6 (1978) 255-279 and 7 (1978) 25-55. | Zbl
,[16] Frontiers of infinite trees, RAIRO Inform. Théor. 12 (1978) 319-337. | Numdam | MR | Zbl
,[17] Arbres infinis et systèmes d'équations, RAIRO Inform. Théor. 13 (1979) 31-48. | Numdam | MR | Zbl
,[18] Infinite trees in normal form and recursive equations having a unique solution, Math. Systems Theory 13 (1979) 131-180. | MR | Zbl
,[19] An axiomatic approach to the Korenjak-Hopcroft algorithms, Math. Systems Theory, to appear. | MR | Zbl
,[20]
, Work in preparation.[21] On the equivalence problem for attribute systems, Information and Control, to appear. | MR | Zbl
and ,[22] On some classes of interpretations, J. Comput. System Sci. 17 (1978) 388-413. | MR | Zbl
and ,[23] 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
, and ,[24] Algebraic families of interpretations, Proc. Annual Symposium on Foundations of Computer Science, Houston, TX (1976) 137-146. | MR
and ,[25] 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
and ,[26] Completions of ordered magmas, Fund. Inform. III.1 (1980) 105-116. | MR | Zbl
and ,[27] Completeness results for the equivalence of recursive schemes, J. Comput. System Sci. 12 (1976) 179-197. | MR | Zbl
and ,[28] La programmation en EXEL, Rev. Tech. Thomson-CSF 10 (1978) 209-234.
,La programmation en EXEL, Rev. Tech. Thomson-CSF 11 (1979) 13-35.
,[29] An algebraic definition for control structures, Theoret. Comput. Sci. 12 (1980, 175-192. | MR | Zbl
,[30] The IO- and OI-hicrarchies, Theoret. Comput. Sci. 20 (1982) 95-207. | MR | Zbl
,[31] 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
, and ,[32] Monadic computation and iterative algebraic theories, in : H.E. Rose, Ed., Logic Colloquium 73 (North-Holland, Amsterdam, 1975) 175-230. | MR | Zbl
,[33] Structured programming with and without GOTO statements, IEEE Trans. Software Engrg. 2 (1976) 41-54. | MR | Zbl
,[34] The algebraic structure of rooted trees, J. Comput. System Sci. 16 (1978) 362-399. | MR | Zbl
, and ,[35] IO and OI, J. Comput. System Sci. 15 (1977) 328-361. | MR | Zbl
and ,IO and OI, J. Comput. System Sci. 16 (1978) 67-99. | MR | Zbl
and ,[36] 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
,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] DPDA's in atomic normal form and applications to the equivalence problems, Theoret. Comput. Sci. 14 (1981) 155-186. | MR | Zbl
,[38] Recursion closed algebraic theories, J. Comput. System Sci., to appear. | MR | Zbl
,[39] N-rational algebras, I : Basic Properties and free algebras, II : Varieties and the logic of inequalities, Submitted for publication. | Zbl
,[40] Regular trees and the free iterative theory, J. Comput. System Sci. 18 (1979) 228-242. | MR | Zbl
,[41] Initial algebra semantics and continuous algebras, J. ACM 24 (1977) 68-95. | MR | Zbl
, . and ,[42] 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] Program transformations and algebraic semantics, Theoret. Comput. Sci. 9 (1979) 39-65. | MR | Zbl
,[44] Algebraic Semantics, Lecture Notes in Computer Science 99 (Springer, Berlin, 1981). | MR | Zbl
,[45] Introduction to Formal Language Theory (Addison-Wesley, Reading, MA, 1978). | MR | Zbl
,[46] On equivalence of grammars through transformation trees, Theoret. Comput. Sci. 9 (1979) 173-205. | MR | Zbl
, and ,[47] An algorithm for the solution of fixed-point equations for infinite words, RAIRO Inform. Theor. 13 (1979) 131-141. | EuDML | Numdam | MR | Zbl
,[48] Résolution d’équations dans les langages d’ordre 1, 2, ..., Doctoral dissertation, University Paris-7 (1976).
,[49] Confluent reductions : abstract properties and applications to term rewriting systems, J. ACM 27 (1980) 797-821. | MR | Zbl
,[50] 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] Bases for chain-complete posets, IBM J. Res. Develop. 20 (1976) 138-147. | MR | Zbl
and ,[52] A compactification of the algebra of terms, Algebra Universalis 6 (1976) 159-163. | MR | Zbl
and ,[53] On the interpretation of recursive polyadic program schemes, Symposia Mathematica 15 (Academic Press, New York, 1975) 255-281. | MR | Zbl
,[54] Mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor. 11 (1977) 311-327. | EuDML | Numdam | MR | Zbl
,[55]
, Private communication.[56] A formalization of EXEL, Proc. ACM Symposium on Principles of Programming Languages, Boston (1973). | Zbl
and ,[57] Computing in Systems Described by Equations, Lecture Notes in Computer Science 58 (Springer, Berlin, 1977). | MR | Zbl
,[58] The decidability of the equivalence for deterministic stateless pushdown automata, Information and Control 38 (1978) 367-376. | MR | Zbl
and ,[59] The equivalence problem for real-time strict deterministic languages, Information and Control 45 (1980) 90-115. | MR | Zbl
, and ,[60] Linear unification, J. Comput. System Sci. 16 (1978) 158-167. | MR | Zbl
and ,[61] A machine-oriented logic based on the resolution principle, J. ACM 12 (1965) 23-41. | MR | Zbl
,[62] Tree-manipulating systems and Church-Rosser theorems, J. ACM 20 (1973) 160-187. | MR | Zbl
,[63] Program equivalence and context-free grammars, J. Comput. System Sci. 11 (1975) 358-374. | MR | Zbl
,[64] On context-free languages and push-down automata. Information and Control 6 (1963) 246-264. | MR | Zbl
,[65] Fixed points and algebras with infinitely long expressions, Fund. Inform. II (1978) 107-128. | Zbl
,[65] Fixed points and algebras with infinitely long expressions, Fund. Inform. II (1979) 317-335. | MR | Zbl
,[66] 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] Unique fixed points vs. least fixed points, Report 49, RWTH Aachen, West Germany (1978). | Zbl
,[68] The equivalence problem for deterministic finite-turn push-down automata. Information and Control 25 (1974) 123-133. | MR | Zbl
,[69] Rational algebraic theories and fixed-point solutions, Proc. 17th Symposium on Foundations of Computer Science, Houston, TX (1976) 147-158. | MR
, , and ,[70] A uniform approach to inductive posets and inductive closure, Theoret. Comput. Sci. 7 (1978) 57-77. | MR | Zbl
, and ,[1] The Lambda-Calculus, Studies in Logic 103 (North-Holland, Amsterdam, 1981). | MR | Zbl
.[2] The existence and construction of free iterative theories. J. Comput. System Sci. 12 (1976) 305-318. | MR | Zbl
and ,[3] Star-height of certain families of regular events. J. Comput. System Sci. 4 (1970) 281-297. | MR | Zbl
,[4] Techniques for establishing star-height of regular sets. Math. Systems Theory 5 (1971) 97-114. | MR | Zbl
,[5] Rank non-increasing transformations on transition graphs, Inform. and Control 20 (1972) 93-113. | MR | Zbl
,[6] General properties of star-height of regular events, J. Comput. System Sci. 4 (1970) 260-280. | MR | Zbl
and ,[7] 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] Fundamental properties of infinite trees. Theoret. Comput. Sci. 25 (1983) 95-169. | MR | Zbl
,[9] An algebraic definition for control structures, Theoret. Comput. Sci. 12 (1980) 175-192. | MR | Zbl
,[10] Transition graphs and the star-height of regular events, Michigan Math. J. 10 (1963) 385-397. | MR | Zbl
,[11] Automata. Languages and Machines, Vol. A (Academic Press, New York. 1974). | MR | Zbl
,[12] Monadic computations and iterative algebraic theories, in : H.E. Rose, ed.. Logic Colloquium 73 (North-Holland, Amsterdam, 1975) pp. 175-230. | MR | Zbl
,[13] The algebraic structure of rooted trees, J. Comput. System Sci. 16 (1978) 362-399. | MR | Zbl
, and ,[14] Regular trees and the free iterative theory, J. Comput. System Sci. 18 (1979) 228-242. | MR | Zbl
,[15] Confluent reductions : abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach 27 (1980) 797-821. | MR | Zbl
,[16] Calcul du rang des arbres infinis réguliers, Proc. CAAP' 81, Lecture Notes Comput. Sci. 112 (Springer, Berlin, 1981) pp. 238-254. | MR
,[17] The loop complexity of pure-group events, Inform. Control 11 (1967) 167-176. | MR | Zbl
,[18] The loop complexity of regular events, Inform. Sci. 1 (1969) 305-328. | MR
,