×
Damm, Werner

The IO- and OI-hierarchies. (English) Zbl 0478.68012

Theor. Comput. Sci. 20, 95-207 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0478.68012

Cited in 4 Reviews
Cited in 59 Documents

MSC:

68N01 General topics in the theory of software
68Q65 Abstract data types; algebraic specification
68Q45 Formal languages and automata
03B40 Combinatory logic and lambda calculus
68Q60 Specification and verification (program logics, model checking, etc.)
03D05 Automata and formal grammars in connection with logical questions
03D20 Recursive functions and relations, subrecursive hierarchies

Keywords:

typed lambda-calculus; recursive procedures in ALGOL 68; finite modes; denotational semantics; program schemes; fixed-point operators; class of level-n schemes; call-by-value; call-by-name; context-free; macro languages; recursion on higher types; control structures

Software:

ALGOL 68; LCF; ALGOL 60
PDF BibTeX XML Cite
\textit{W. Damm}, Theor. Comput. Sci. 20, 95--207 (1982; Zbl 0478.68012)
Full Text: DOI

References:

[1] Abdali, S. K., A lambda-calculus model of programming languages I, II, J. Comput. Languages, 1, 287-320 (1976)
[2] Aho, A. V., Indexed grammars—an extension of context-free grammars, J. ACM, 15, 4, 647-671 (1968) · Zbl 0175.27801
[3] Astesiano, E.; Costa, G., Languages with reducing reflexive types, (Proc. 7th International Colloquium on Automata, Languages and Programming, 85 (1980), Springer: Springer Berlin), 38-50, Lecture Notes in Computer Science · Zbl 0444.68026
[4] Beeri, C., Two-way nested stack automata are equivalent to two-way stack automata, J. Comput. System Sci., 10, 317-339 (1975) · Zbl 0331.68029
[5] Bilstein, J.; Damm, W., Top-down tree-transducers for infinite trees I, (Proc. 6’ième Colloque sur les Arbres en Algebre et en Programmation, 112 (1981), Springer: Springer Berlin), 117-134, Lecture Notes in Computer Science · Zbl 0486.68012
[6] Boasson, B.; Courcelle, B.; Nivat, M., A new complexity measure for languages (1977), University of Waterloo, Proc. Conference on Theoretical Computer Science · Zbl 0431.68077
[7] Courcelle, B., A representation of trees by languages, Theoret. Comput. Sci., 7, 25-55 (1978) · Zbl 0428.68088
[8] Courcelle, B.; Franchi-Zannettacci, P., Attribute grammars and recursive program schemes, CNRS Report 8008, 1 (1980), University Bordeaux · Zbl 0481.68068
[9] Courcelle, B.; Nivat, M., The algebraic semantics of recursive program schemes, IRIA Laboratory Report 300 (1978) · Zbl 0384.68016
[10] Curry, H. B.; Feys, R., Combinatory Logic, Vol. 1 (1958), North-Holland: North-Holland Amsterdam · Zbl 0175.27601
[11] Damm, W., Higher type program schemes and their tree languages, (Proc. 3rd GI Conference on Theoretical Computer Science, 48 (1977), Springer: Springer Berlin), 51-72, Lecture Notes in Computer Science · Zbl 0358.68009
[12] Damm, W., Languages defined by higher type program schemes, (Proc. 4th International Colloquium on Automata, Languages and Programming, 52 (1977), Springer: Springer Berlin), 164-179, Lecture Notes in Computer Science
[13] Damm, W., An algebraic extension of the Chomsky-hierarchy, (Proc. Conference on Mathematical Foundations of Computer Science, 74 (1979), Springer: Springer Berlin), 266-276, Lecture Notes in Computer Science · Zbl 0412.68069
[14] Damm, W., A note on nondeterministic \(n\)-rational schemes, Schr. Informatik Angew. Math. (1980)
[15] Damm, W., The IO- and OI-hierarchies, Schr. Informatik Angew. Math., 41 (1981), revised. · Zbl 0471.68058
[16] Damm, W.; Fehr, E., On the power of self-application and higher type recursion, (Proc. 5th International Colloquium on Automata, Languages and Programming, 62 (1978), Springer: Springer Berlin), 177-191, Lecture Notes in Computer Science · Zbl 0391.68041
[17] Damm, W.; Fehr, E., A schematological approach to the analysis of the procedure concept in ALGOL-languages, Proc. 5 ième Colloque sur les Arbres en Algebre et en Programmation, 130-134 (1980), (abstract of [19]).
[19] Damm, W.; Fehr, E.; Indermark, K., Higher type recursion and self-application as control structures, (Neuhold, E., Formal Description of Programming Concepts (1978), North-Holland: North-Holland Amsterdam), 461-487 · Zbl 0373.68021
[21] Egli, H., Typed meaning in Scott’s λ-calculus models, (Proc. Symposium on λ-Calculus, 37 (1975), Springer: Springer Berlin), 220-239, Lecture Notes in Computer Science · Zbl 0378.02009
[22] Engelfriet, J., Tree automata and tree grammars, Datalogisk Afdelning Report (1975), Aarhus University, DAIMI FN-10 · Zbl 0938.68681
[23] Engelfriet, J., Some open questions and recent results on tree transducers and tree languages, Proc. Symposium on Formal Language Theory (1979), Academic Press: Academic Press New York, to appear.
[24] Engelfriet, J.; de Bakker, J. W.; van Leeuwen, J., Two-way automata and checking automata, Foundations of Computer Science III. Foundations of Computer Science III, Mathematical Centre Tracts, 108, 1-69 (1979)
[26] Engelfriet, J., Three hierarchies of transducers, Memorandum 217 (1978), Twente University of Technology · Zbl 0509.68078
[27] Engelfriet, J.; Schmidt, E. M., IO and OI, J. Comput. System Sci., 16, 1, 67-99 (1978) · Zbl 0371.68020
[28] Fehr, E., Lambda-calculus as control structures of programming languages, Schr. Informatik Angew. Math., 57 (1980) · Zbl 0448.68003
[29] Fischer, M. J., Grammars with macro-like productions, Proc. 9th IEEE Conference on Switching and Automata Theory, 131-142 (1968)
[30] Garland, S. J.; Luckham, D. C., Program schemes, recursion schemes, and formal languages, J. Comput. System Sci., 7, 113-160 (1979) · Zbl 0369.68014
[31] Goguen, J. A.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B., Initial algebra semantics and continuous algebras, J. ACM, 24, 1, 68-95 (1977) · Zbl 0359.68018
[32] Hayaschi, T., On derivations trees of indexed grammars –an extension of the uvwxy-theorem, Publ. Res. Inst. Math. Sci., 9, 1 (1973)
[33] Hennessy, M. C.B., The semantic of call by value and call by name in a nondeterministic environment, SIAM J. Comput., 9, 1, 67-84 (1980) · Zbl 0437.68002
[34] Indermark, K., Schemes with recursion on higher types, (Proc. 5th Conference on Mathematical Foundations of Computer Science, 45 (1976), Springer: Springer Berlin), 352-358, Lecture Notes in Computer Science
[35] Indermark, K., On rational definitions in complete algebras without rank, Schr. Informatik Ange. Math., 64 (1980) · Zbl 0472.68007
[36] Landin, P. J., A correspondence between ALGOL 60 and Church’s lambda notation, Comm. ACM, 8, 83-101 (1965) · Zbl 0134.33403
[37] Langmaack, H., On procedures as open subroutines, Acta Informat., 3, 227-241 (1974) · Zbl 0304.68016
[38] Langmaack, H., On a theory of decision problems in programming languages, (Proc. International Conference on Mathematical Studies of Information Processing, 75 (1979), Springer: Springer Berlin), 538-557, Lecture Notes in Computer Science
[39] Ledgard, H., Ten mini languages: A study of topical issues in programming languages, Comput. Surveys, 3, 3, 115-146 (1971) · Zbl 0228.68020
[40] Luckham, D. C.; Park, D. M.R.; Paterson, M. S., On formalised computer programs, J. Comput. System Sci., 4, 220-249 (1970) · Zbl 0209.18704
[41] Maibaum, T. S.E., A generalized approach to formal languages, J. Comput. System Sci., 8, 409-439 (1974) · Zbl 0361.68113
[42] Maslov, A. N., The hierarchy of indexed languages of an arbitrary level, Soviet. Math. Dokl., 15, 14, 1170-1174 (1974) · Zbl 0316.68042
[43] Maslov, A. N., Multilevel stack automata, Problemy Peredachi Informatsii, 12, 1, 55-62 (1976) · Zbl 0361.68079
[44] Mezei, J.; Wright, J. B., Algebraic automata and context-free sets, Information and Control, 11, 3-29 (1967) · Zbl 0155.34301
[45] Milne, R., The mathematical semantics of ALGOL 68, PRG report Oxford (1972)
[46] Milne, R.; Strachey, C., A Theory of Programming Language Semantics, Part a and b (1976), Chapman and Hall: Chapman and Hall London · Zbl 0357.68004
[47] Milner, R., Models of LCF, Memo AIM-186 (1973), Stanford University · Zbl 0364.02018
[48] Mitschke, G., The standardization theorem for λ-calculus, Z. Math. Logik. Grundlag. Math., 25, 1, 29-31 (1979) · Zbl 0442.03013
[49] Morris, J. M., Lambda calculus models of programming languages, Project MAC Report TR-57 (1968), Dissertation MIT
[50] Mosses, P., The mathematical semantics of ALGOL 60, PRG-Report 12 (1974), Oxford
[51] Nivat, M., Langages algébriques sur le magma libre et sémantique des schémas de programme, (Nivat, M., Automata, Languages, and Programming (1972), North-Holland: North-Holland Amsterdam), 293-307 · Zbl 0279.68010
[52] Nivat, M., On the interpretation of recursive program schemes, Symposia Matematica, Atti del convegno d’Informatica theorica (1972), Rome
[53] Plotkin, G. D., LCF considered as a programming language, Theoret. Comput. Sci., 5, 3, 223-255 (1977) · Zbl 0369.68006
[54] Reynolds, J. C., Towards a theory of type structure, Colloquium on Programming (1974), Paris · Zbl 0309.68016
[55] Rounds, W. C., Tree-oriented proofs of some theorems on context-free and indexed languages, 2nd Annual ACM Symposium on Theory of Computing, 109-116 (1970)
[56] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[57] Schmidt, E. M., Succintness of description of context-free, regular, and finite languages, Datalogisk Afdelning Report (1978), Aarhus University, DAIMI PB-84
[58] Scott, D., The lattice of flow diagrams, (Symposium on Semantics of Algorithmic Languages, 188 (1971), Springer: Springer Berlin), 311-366, Lecture Notes in Mathematics
[59] Scott, D., Continuous lattices, (Proc. Dalhousie Conference, 274 (1972), Springer: Springer Berlin), 97-134, Lecture Notes in Mathematics
[60] Steyaert, J. M., Evaluation des index rationnels de quelques families de langages, IRIA-Report No. 261 (1977)
[61] Stoy, J. E., Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory (1977), MIT Press: MIT Press Cambridge, MA · Zbl 0503.68059
[62] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math., 5, 285-309 (1955) · Zbl 0064.26004
[63] Tennent, R. D., The denotational semantics of programming languages, Comm. ACM, 19, 437-453 (1976) · Zbl 0337.68010
[64] Thatcher, J. W., Tree automata: an informal survey, (Aho, A. V., Currents in the theory of Computing (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 143-172
[65] Turner, R., An algebraic theory of formal languages, (Proc. 4th Conference on Mathematical Foundations of Computer Science, 32 (1975), Springer: Springer Berlin), 426-431, Lecture Notes in Computer Science
[66] Vuillemin, J., Syntaxe, sémantique et axiomatique d’un language de programmation simple, doctorial thesis, VI (1974), University Paris · Zbl 0327.68006
[67] Wadsworth, C., The relation between computational and denotational properties for Scott’s \(D_x\)-models of the lambda-calculus, SIAM J. Comput., 5, 3, 488-521 (1976) · Zbl 0346.02013
[68] Wand, M., A concrete approach to abstract recursive definitions, (Nivat, M., Automata, Languages, and Programming (1973), North-Holland: North-Holland Amsterdam), 331-341
[69] Wand, M., An algebraic formulation of the Chomsky-hierarchy, (Category Theory Applied to Computation and Control, 25 (1975), Springer: Springer Berlin), 209-213, Lecture Notes in Computer Science · Zbl 0305.68056
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.