๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On Different Structure-preserving Translations to Normal Form

โœ Scribed by UWE EGLY

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
772 KB
Volume
22
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper, we compare different definitional transformations into normal form with respect to the Herbrand complexity of the resulting normal forms. Usually, such definitional transformations introduce labels defining subformulae. An obvious optimization is to use implications instead of equivalences, if the subformula occurs in one polarity only, in order to reduce the length of the resulting normal form. We identify a sequence of formulae H 1 , H 2 , . . ., for which the difference of the Herbrand complexity of the different translations of H k is bounded from below by a non-elementary function in k. If the optimized translation is applied instead of the unoptimized one, the length of any resolution or cut-free LK-proof of H k is non-elementary in k instead of exponential in k.

๐Ÿ“œ SIMILAR VOLUMES

Macro and File Structure Preservation in
Macro and File Structure Preservation in Source-to-source Translation
โœ KRISTY ANDREWS; PAUL DEL VIGNA; MARK MOLLOY ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 667 KB

This paper describes a strategy for translating macro definitions and uses in the context of performing automated source-to-source translation between high-level programming languages. This translation technology enables macros and other preprocessor structures to be preserved in the generated sourc

Operations on Ring Structures Preserved
Operations on Ring Structures Preserved by Normalized Automorphisms of Group Rings
โœ Frauke M Bleher; Ted Chinburg ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 103 KB

Let O O be a commutative ring, and suppose is a normalized O O-algebra automorphism of the group ring O OG of a finite group G over O O. In this paper we consider the action of on various algebraic structures associated to G. Suppose O O is an integral domain of characteristic 0, and that no prime d