{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T08:00:56Z","timestamp":1757577656022},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1985,10,1]],"date-time":"1985-10-01T00:00:00Z","timestamp":496972800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1985,10]]},"DOI":"10.1007\/bf00288773","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T15:51:37Z","timestamp":1096905097000},"page":"347-377","source":"Crossref","is-referenced-by-count":16,"title":["Necessary and sufficient conditions for the universality of programming formalisms"],"prefix":"10.1007","volume":"22","author":[{"given":"A. J.","family":"Kfoury","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawel","family":"Urzyczyn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0019-9958(78)90296-6","volume":"36","author":"F. Abramson","year":"1978","unstructured":"Abramson, F.: Interpolation theorems for program schemata. Inf. Control 36, 217?233 (1978)","journal-title":"Inf. Control"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1137\/0201017","volume":"1","author":"S. Brown","year":"1972","unstructured":"Brown, S., Gries, D., Szymanski, T.: Program schemes with pushdown stores. SIAM J. Comput. 1, 242?268 (1972)","journal-title":"SIAM J. Comput."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0201006","volume":"1","author":"R.C. Constable","year":"1972","unstructured":"Constable, R.C., Gries, D.: On classes of program schemata. SIAM J. Comput. 1, 66?118 (1972)","journal-title":"SIAM J. Comput."},{"key":"CR4","volume-title":"Characterization of acceptable by Algol-like programming languages","author":"C. Crasemann","year":"1983","unstructured":"Crasemann, C., Langmaack, H.: Characterization of acceptable by Algol-like programming languages. Proceedings of 4th Workshop on Logics of Programs, June 6?9, Carnegie-Mellon University. Berlin-Heidelberg-New York: Springer 1983"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF01705528","volume":"1","author":"E. Engeler","year":"1967","unstructured":"Engeler, E.: Algorithmic properties of structures. Math. Syst. Theory 1, 183?195 (1967)","journal-title":"Math. Syst. Theory"},{"key":"CR6","unstructured":"Engeler, E.: Algorithmic logic. In: Foundations of Computer Science (J.W. de Bakker, ed.) Math. Cent. Tracts 63, 57?85 (1975)"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/S0304-3975(81)80002-3","volume":"13","author":"E. Engeler","year":"1981","unstructured":"Engeler, E.: Generalized Galois theory and its application to complexity. Theor. Comput. Sci. 13, 271?293 (March, 1981)","journal-title":"Theor. Comput. Sci."},{"key":"CR8","first-page":"361","volume-title":"Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory","author":"H. Friedman","year":"1971","unstructured":"Friedman, H.: Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory. In: Logic Colloquim 1969 (R.O. Gandy, C.M.E. Yates, eds.) pp. 361?389. Amsterdam: North Holland 1971"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0022-0000(73)80040-6","volume":"7","author":"S.J. Garland","year":"1973","unstructured":"Garland, S.J., Luckham, D.C.: Program schemes, recursion schemes, and formal languages. J. Comput. Syst. Sci. 7, 119 160 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Harel, D.: First-Order Dynamic Logic. Lect. Notes Comput. Sci. 68, N.Y.: Springer 1979","DOI":"10.1007\/3-540-09237-4"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0022-0000(74)80030-9","volume":"8","author":"A.J. Kfoury","year":"1974","unstructured":"Kfoury, A.J.: Translatability of schemas over restricted interpretations. J. Comput. Syst. Sci. 8, 387?408 (June 1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(83)90013-0","volume":"25","author":"A.J. Kfoury","year":"1983","unstructured":"Kfoury, A.J.: Definability by programs in first-order structures. Theor. Comput. Sci. 25, 1?66 (January, 1983)","journal-title":"Theor. Comput. Sci."},{"key":"CR13","unstructured":"Kfoury, A.J.: Definability by deterministic and non-deterministic programs (with new proofs of old and new results in dynamic logic). Information and Control (To appear)"},{"key":"CR14","first-page":"195","volume":"1","author":"A. Kreczmar","year":"1977","unstructured":"Kreczmar, A.: Programmability in fields. Fundam. Inf. 1, 195?230 (1977)","journal-title":"Fundam. Inf."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Lipton, R.J.: A necessary and sufficient condition for the existence of Hoare logics. Proc. IEEE 18th FOCS, 1977","DOI":"10.1109\/SFCS.1977.1"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D. Luckham","year":"1970","unstructured":"Luckham, D., Park, D.M.R., Paterson, M.S.: On formalized computer programs. J. Comput. Syst. Sci. 4, 220?249 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01776573","volume":"12","author":"N.A. Lynch","year":"1979","unstructured":"Lynch, N.A., Blum, E.K.: A difference in expressive power between flowcharts and recursion schemes. Math. Syst. Theory 12, 205?211 (1979)","journal-title":"Math. Syst. Theory"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01744295","volume":"13","author":"N.A. Lynch","year":"1980","unstructured":"Lynch, N.A., Blum, E.K.: Relative complexity of operations on numeric and bit-string algebras. Math. Syst. Theory 13, 187?207 (1980)","journal-title":"Math. Syst. Theory"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01752396","volume":"14","author":"N.A. Lynch","year":"1981","unstructured":"Lynch, N.A., Blum, E.K.: Relative complexity of algebras. Math. Syst. Theory 14, 193?214 (1981)","journal-title":"Math. Syst. Theory"},{"key":"CR20","unstructured":"McKay, R.: The equivalence of programme schemes in structures with equality. Ph. D. Thesis, University of Bristol, 1976"},{"key":"CR21","volume-title":"Computation: Finite and Infinite Machines","author":"M.L. Minsky","year":"1977","unstructured":"Minsky, M.L.: Computation: Finite and Infinite Machines. Englewood Cliffs, New Jersey: Prentice Hall 1977"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/322307.322324","volume":"29","author":"A.R. Meyer","year":"1982","unstructured":"Meyer, A.R., Halpern, J.Y.: Axiomatic definitions of programming languages: a theoretical assessment. J. ACM 29, 555?575 (April, 1982)","journal-title":"J. ACM"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Mitchell, J.C.: Termination assertions for recursive programs: Completeness and axiomatic definability. Inf. Control (To appear)","DOI":"10.1016\/S0019-9958(83)80053-9"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Parikh, R.: Definability in dynamic logic. Proc. ACM, 12th STOC 1980","DOI":"10.1145\/800141.804646"},{"key":"CR25","unstructured":"Paterson, M.S., Hewitt, C.: Comparative schematology. MIT AI Laboratory, Memo no. 201, November 1970"},{"key":"CR26","volume-title":"Pebbling","author":"N. Pippenger","year":"1980","unstructured":"Pippenger, N.: Pebbling. Proc. of Fifth IBM Symposium on Mathematical Foundations of Computer Science, IBM Japan, May 1980"},{"key":"CR27","first-page":"445","volume-title":"Computation over abstract structures: serial and parallel procedures and Friedman's effective definitional schemes","author":"J.C. Shepherdson","year":"1975","unstructured":"Shepherdson, J.C.: Computation over abstract structures: serial and parallel procedures and Friedman's effective definitional schemes. In: Logic Colloquium '73 (J.C. Shepherdson, J. Rose, eds.) pp. 445?513. Amsterdam, North-Holland 1975"},{"key":"CR28","first-page":"1","volume-title":"Recursion Theory, its Generalizations and Applications","author":"J.V. Tucker","year":"1980","unstructured":"Tucker, J.V.: Computing in algebraic systems. In: Recursion Theory, its Generalizations and Applications (F.R. Drake, S.S. Wainer, eds.), pp. 1?22. Cambridge: Cambridge University Press 1980)"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0019-9958(81)90163-7","volume":"50","author":"P. Urzyczyn","year":"1981","unstructured":"Urzyczyn, P.: The unwind property in certain algebras. Inf. Control 50, 91?109 (1981)","journal-title":"Inf. Control"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/S0019-9958(83)80006-0","volume":"56","author":"P. Urzyczyn","year":"1983","unstructured":"Urzyczyn, P.: A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs. Inf. Control 56, 212?219 (1983)","journal-title":"Inf. Control"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0019-9958(83)80057-6","volume":"58","author":"P. Urzyczyn","year":"1983","unstructured":"Urzyczyn, P.: Non-trivial definability by flowchart programs. Inf. Control 58, 59?87 (1983)","journal-title":"Inf. Control"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"Urzyczyn, P.: Deterministic context-free dynamic logic is more expressive than deterministic dynamic logic of regular programs. Proc. Int. Conf. on Foundations of Computation Theory Borgholm, Sweden, August 1983","DOI":"10.1007\/3-540-12689-9_130"},{"key":"CR33","unstructured":"Venkataram, K.N., Yasuhara, A., Hawrusik, F.: A view of computability on term algebras. J. Comput. Syst. Sci. (To appear)"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF02483111","volume":"11","author":"P. Winker","year":"1980","unstructured":"Winker, P.: Classification of algebraic structures by work space. Algebra Univers. 11, 320?333 (1980)","journal-title":"Algebra Univers"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288773.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00288773\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T21:14:27Z","timestamp":1554758067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00288773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,10]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,10]]}},"alternative-id":["BF00288773"],"URL":"https:\/\/doi.org\/10.1007\/bf00288773","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,10]]}}}