Necessary and sufficient conditions for the universality of programming formalisms

DOI10.1007/BF00288773zbMath0552.68008OpenAlexW1977367505MaRDI QIDQ801666

A. J. Kfoury, Paweł Urzyczyn

Publication date: 1985

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288773

zbMATH Keywords

partial recursive functionalgebraic structuresdata typesflowchart

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Data structures (68P05) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (4)

The verification of modules ⋮ Composition aspects of programmology. I ⋮ On the expressive power of finitely typed and universally polymorphic recursive procedures ⋮ Characterizing complexity classes by general recursive definitions in higher types

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A view of computability on term algebras
• Classification of algebraic structures by work space
• Generalized galois theory and its application to complexity
• Definability in dynamic logic
• Definability by programs in first-order structures
• First-order dynamic logic
• Program schemes, recursion schemes, and formal languages
• Translatability of schemas over restricted interpretations
• On formalised computer programs
• Termination assertions for recursive programs: Completeness and axiomatic definability
• A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs
• Nontrivial definability by flow-chart programs
• Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
• A difference in expressive power between flowcharts and recursion schemes
• Relative complexity of operations on numeric and bit-string algebras
• Relative complexity of algebras
• Axiomatic Definitions of Programming Languages
• The unwind property in certain algebras
• Interpolation theorems for program schemata
• Program Schemes with Pushdown Stores
• Algorithmic properties of structures
• On Classes of Program Schemata

This page was built for publication: Necessary and sufficient conditions for the universality of programming formalisms