Efficient reducibility between programming systems (Preliminary Report)
Nancy Ann Lynch, Edward K. Blum · 1977
Much of the research on semantic theories has concentrated on qualitative properties such as definability (of such programming concepts as recursive procedures), equivalence (of different language constructs), and verifiability (of the correctness, or consistency, of one expression relative to another). Current qualitative theories are in a tentative state and much remains to be done. However, there is also a quantitative side to semantics. Indeed, many of the questions which any semantic theory must answer are at once qualitative and quantitative. We would like to draw upon complexity-theoretic techniques to answer such questions. We are currently working on the development of new algebraic constructs to provide a mathematical framework for both qualitative and quantitative analysis of semantic problems.