×

zbMATH — the first resource for mathematics

Fundamental properties of infinite trees. (English) Zbl 0521.68013

MSC:
68N01 General topics in the theory of software
68Q60 Specification and verification (program logics, model checking, etc.)
68Q55 Semantics in the theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold, A.; Dauchet, M., Théorie des magmoïdes, RAIRO inform. théor., 12, 235-257, (1978) · Zbl 0391.68037
[2] Arnold, A.; Nivat, M., Metric interpretations of infinite trees and semantics of non deterministic recursive programs, Theoret. comput. sci., 11, 181-205, (1980) · Zbl 0427.68022
[3] Arnold, A.; Nivat, M., The metric space of infinite trees. algebraic and topological properties, Fund. inform., III.4, 445-476, (1980) · Zbl 0453.68021
[4] Bekić, H., Definable operations in general algebras, and the theory of automata and flowcharts, (1969), IBM Laboratory Vienna, Unpublished work
[5] S. Bloom, All solutions of a system of recursion equations in infinite trees and other contraction theories, J. Comput. System Sci., to appear. · Zbl 0535.68006
[6] Bloom, S.; Elgot, C., The existence and construction of free iterative theories, J. comput. system sci., 12, 305-318, (1976) · Zbl 0333.68017
[7] Bloom, S.; Elgot, C.; Wright, J., Solutions of the iteration equation and extensions of the scalar iteration operation, SIAM J. comput., 9, 25-45, (1980) · Zbl 0454.18011
[8] Bloom, S.; Ginali, S.; Rutledge, J., Scalar and vector iteration, J. comput. system sci., 14, 251-256, (1977) · Zbl 0358.68072
[9] Bloom, S.; Patterson, D., Easy solutions are hard to find, (), 135-146, Lecture Notes in Computer Science
[10] Bloom, S.; Tindell, R., Compatible orderings on the metric theory of trees, SIAM J. comput., 9, 683-691, (1980) · Zbl 0447.05026
[11] Bloom, S.; Tindell, R., Varieties of “if-then-else”, (1981), Submitted for publication · Zbl 0518.68010
[12] Book, R., The undecidability of a word problem: on a conjecture of strong, maggiolo-schettini and Rosen, Inform. process lett., 12, 121-122, (1981) · Zbl 0457.03036
[13] Casteran, P., Structures de contrôle: définitions opérationnelles et algébriques., Thése de 3ème cycle, 7, (1979), University Paris
[14] Courcelle, B., On jump-deterministic pushdown automata, Math. systems theory, 11, 87-109, (1977) · Zbl 0365.02021
[15] Courcelle, B.; Courcelle, B., A representation of trees by languages, Theoret. comput. sci., Theoret. comput. sci., 7, 25-55, (1978) · Zbl 0428.68088
[16] Courcelle, B., Frontiers of infinite trees, RAIRO inform. théor., 12, 319-337, (1978) · Zbl 0411.68065
[17] Courcelle, B., Arbres infinis et systèmes d’équations, RAIRO inform. théor., 13, 31-48, (1979) · Zbl 0406.68017
[18] Courcelle, B., Infinite trees in normal form and recursive equations having a unique solution, Math. systems theory, 13, 131-180, (1979) · Zbl 0418.68013
[19] B. Courcelle, An axiomatic approach to the Korenjak-Hoperoft algorithms, Math. Systems Theory, to appear. · Zbl 0462.68008
[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. · Zbl 0529.68005
[22] Courcelle, B.; Guessarian, I., On some classes of interpretations, J. comput. system sci., 17, 388-413, (1978) · Zbl 0392.68009
[23] Courcelle, B.; Khan, G.; Vuillemin, I., Algorithmes d’équivalence et de réduction á des expressions minimales, dam une classe d’équations récursive simples, (), 200-213, Lecture Notes in Computer Science
[24] Courcelle, B.; Nivat, M., Algebraic families of interpretations, Proc. annual symposium on foundations of computer science, 137-146, (1976), Houston, TX
[25] Courcelle, B.; Nivat, M., The algebraic semantics of recursive program schemes, (), 16-30, Lecture Notes in Computer Science · Zbl 0384.68016
[26] Courcelle, B.; Raoult, J.C., Completions of ordered magmas, Fund. inform., 111.1, 105-116, (1980) · Zbl 0463.06005
[27] Courcelle, B.; Vuillemin, J., Completeness results for the equivalence of recursive schemes, J. comput. system sci., 12, 179-197, (1976) · Zbl 0342.68008
[28] Cousineau, G.; Cousineau, G., La programmation en EXEL, Rev. tech. thomson-CSF, Rev. tech. thomson-CSF, 11, 13-35, (1979)
[29] Cousineau, G., An algebraic definition for control structures, Theoret. comput. sci., 12, 175-192, (1980) · Zbl 0456.68015
[30] Damm, W., The IO-and OI-hierarchies, Theoret. comput. sci., 20, 95-207, (1982) · Zbl 0478.68012
[31] Damm, W.; Fehr, E.; Indermark, K., Higher type recursion and self-application as control structures, (), 461-487 · Zbl 0373.68021
[32] Elgot, C., Monadic computation and iterative algebraic theories, (), 175-230 · Zbl 0327.02040
[33] Elgot, C., Structured programming with and without GOTO statements, IEEE trans. software engrg., 2, 41-54, (1976) · Zbl 0348.68008
[34] Elgot, C.; Bloom, S.; Tindell, R., The algebraic structure of rooted trees, J. comput. system sci., 16, 362-399, (1978) · Zbl 0389.68007
[35] Engelfriet, J.; Schmidt, E.; Engelfriet, J.; Schmidt, E., IO and OI, J. comput. system sci., J. comput. system sci., 16, 67-99, (1978) · Zbl 0371.68020
[36] Enjalbert, P.; Enjalbert, P., Systèmes de déductions pour LES arbres et LES schémas de programmes, RAIRO inform. théor., RAIRO inform. théor., 15, 3-21, (1981) · Zbl 0464.68019
[37] Gallier, J., DPDA’s in atomic normal form and applications to the equivalence problems, Theoret. comput. sci., 14, 155-186, (1981) · Zbl 0474.68065
[38] J. Gallier, Recursion closed algebraic theories, J. Comput. System Sci., to appear. · 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] Ginali, S., Regular trees and the free iterative theory, J. comput. system sci., 18, 228-242, (1979) · Zbl 0495.68042
[41] Goguen, J.; Thatcher, J.; Wagner, E.; Wright, J., Initial algebra semantics and continuous algebras, J. ACM, 24, 68-95, (1977) · Zbl 0359.68018
[42] Gorn, S., Explicit definitions and linguistic dominoes, (), 77-105
[43] Guessarian, I., Program transformations and algebraic semantics, Theoret. comput. sci., 9, 39-65, (1979) · Zbl 0399.68023
[44] Guessarian, I., Algebraic semantics, Lecture notes in computer science, 99, (1981), Springer Berlin · Zbl 0474.68010
[45] Harrison, M., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[46] Harrison, M.; Havel, I.; Yehudai, A., On equivalence of grammars through transformation trees, Theoret. comput. sci., 9, 173-205, (1979) · Zbl 0409.68041
[47] Heilbrunner, S., An algorithm for the solution of fixed-point equations for infinite words, RAIRO inform. theor., 13, 131-141, (1979) · Zbl 0433.68062
[48] Huet, G., Résolution d’équations dans LES langages d’ordre 1, 2,…ω, Doctoral dissertation, (1976), University Paris-7
[49] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. ACM, 27, 797-821, (1980) · Zbl 0458.68007
[50] Leszczylowski, J., A theorem on resolving equations in the space of languages, Bull. acad. polon. sci., ser. sci. math. astrotom. phys., 19, 967-970, (1979) · Zbl 0242.68034
[51] Markowsky, G.; Rosen, B., Bases for chain-complete posets, IBM J. res. develop., 20, 138-147, (1976) · Zbl 0329.06001
[52] Mycielski, J.; Taylor, W., A compactification of the algebra of term, Algebra universalis, 6, 159-163, (1976) · Zbl 0358.08001
[53] Nivat, M., On the interpretation of recursive polvadie program schemes, (), 255-281
[54] Nivat, M., Mots infinis engendrés par une grammaire algebrique, RAIRO inform. theor., 11, 311-327, (1977) · Zbl 0371.68025
[55] M. Nivat, Private communication.
[56] Nolin, I.; Ruggin, G., A formalization of EXEL, Proc. ACM symposium on principles of programming languages, (1973), Boston · Zbl 0308.68011
[57] O’Donnell, M., Computing in systems described by equations, Lecture notes in computer science, 58, (1977), Springer Berlin · Zbl 0421.68038
[58] Oyamaguchi, M.; Honda, N., The decidability of the equivalence for deterministic stateless pushdown automata, Information and control, 38, 367-376, (1978) · Zbl 0393.68078
[59] Oyamaguchi, M.; Honda, N.; Inagaki, Y., The equivalence problem for real-time strict deterministic languages, Information and control, 45, 90-115, (1980) · Zbl 0444.68038
[60] Paterson, M.; Wegman, M., Linear unification, J. comput. system sci., 16, 158-167, (1978) · Zbl 0371.68013
[61] Robinson, J., A machine-oriented logic based on the resolution principle, J. ACM, 12, 23-41, (1965) · Zbl 0139.12303
[62] Rosen, B., Tree-manipulating systems and church-rosser theorems, J. ACM, 20, 160-187, (1973) · Zbl 0267.68013
[63] Rosen, B., Program equivalence and context-free grammars, J. comput. system sci., 11, 358-374, (1975) · Zbl 0315.68063
[64] Schützenberger, M., On context-free languages and push-down automata, Information and control, 6, 246-264, (1963) · Zbl 0123.12502
[65] Tiuryn, J.; Tiuryn, J., Fixed points and algebras with infinitely long expressions, Fund. inform., Fund. inform., II, 317-335, (1979) · Zbl 0436.68015
[66] Tiuryn, J., On a connection between regular algebras and rational algebraic theories, Proc. 2nd workshop on categorical and algebraic methods in computer science and system theory, (1978), Dortmund, West Germany · Zbl 0465.68022
[67] Tiuryn, J., Unique fixed points vs least fixed points, Report 49, (1978), RWTH Aachen, West Germany · Zbl 0439.68026
[68] Valiant, L., The equivalence problem for deterministic finite-turn push-down automata, Information and control, 25, 123-133, (1974) · Zbl 0285.68025
[69] Wright, J.; Thatcher, J.; Wagner, E.; Goguen, J., Rational algebraic theories and fixed-point solutions, Proc. 17th symposium on foundations of computer science, 147-158, (1976), Houston, TX
[70] Wright, J.; Wagner, E.; Thatcher, J., A uniform approach to inductive posets and inductive closure, Theoret. comput. sci., 7, 57-77, (1978) · Zbl 0732.06001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.