Ordinal Arithmetic: A Case Study for Rippling in a Higher Order Domain

This paper reports a case study in the use of proof planning in the context of higher order syntax. Rippling is a heuristic for guiding rewriting steps in induction that has been used successfully in proof planning inductive proofs using first order representations. Ordinal arithmetic provides a natural set of higher order examples on which transfinite induction may be attempted using rippling. Previously Boyer-Moore style automation could not be applied to such domains. We demonstrate that a higher-order extension of the rippling heuristic is sufficient to plan such proofs automatically. Accordingly, ordinal arithmetic has been implemented in lambda-clam, a higher order proof planning system for induction, and standard undergraduate text book problems have been successfully planned. We show the synthesis of a fixpoint for normal ordinal functions which demonstrates how our automation could be extended to produce more interesting results than the textbook examples tried so far.

Structure of the N-terminal oligomerization domain of DnaD reveals a unique tetramerization motif and provides insights into scaffold formation

DnaD is a primosomal protein that remodels supercoiled plasmids. It binds to supercoiled forms and converts them to open forms without nicking. During this remodeling process, all the writhe is converted to twist and the plasmids are held around the periphery of large scaffolds made up of DnaD molecules. This DNA-remodeling function is the sum of a scaffold-forming activity on the N-terminal domain and a DNA-dependent oligomerization activity on the C-terminal domain. We have determined the crystal structure of the scaffold-forming N-terminal domain, which reveals a winged-helix architecture, with additional structural elements extending from both N- and C-termini. Four monomers form dimers that join into a tetramer. The N-terminal extension mediates dimerization and tetramerization, with extensive interactions and distinct interfaces. The wings and helices of the winged-helix domains remain exposed on the surface of the tetramer. Structure-guided mutagenesis and atomic force microscopy imaging indicate that these elements, together with the C-terminal extension, are involved in scaffold formation. Based upon our data, we propose a model for the DnaD-mediated scaffold formation.