zbMATH — the first resource for mathematics

Rewriting logic as a metalogical framework. (English) Zbl 1044.03020
Kapoor, Sanjiv (ed.) et al., FST TCS 2000: Foundations of software technology and theoretical computer science. 20th conference, New Delhi, India, December 13–15, 2000. Proceedings. Berlin: Springer (ISBN 3-540-41413-4). Lect. Notes Comput. Sci. 1974, 55-80 (2000).
Summary: A metalogical framework is a logic with an associated methodology that is used to represent other logics and to reason about their metalogical properties. We propose that logical frameworks can be good metalogical frameworks when their logics support reflective reasoning and their theories always have initial models. We present a concrete realization of this idea in rewriting logic. Theories in rewriting logic always have initial models and this logic supports reflective reasoning. This implies that inductive reasoning is valid when proving properties about the initial models of theories in rewriting logic, and that we can use reflection to reason at the metalevel about these properties. In fact, we can uniformly reflect induction principles for proving metatheorems about rewriting logic theories and their parameterized extensions. We show that this reflective methodology provides an effective framework for different, non-trivial, kinds of formal metatheoretic reasoning; one can, for example, prove metatheorems that relate theories or establish properties of parameterized classes of theories. Finally, we report on the implementation of an inductive theorem prover in the Maude system, whose design is based on the results presented in this paper.
For the entire collection see [Zbl 0952.00044].

03B70 Logic in computer science
68Q42 Grammars and rewriting systems
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: Link