Invariant-free deduction systems for temporal logic

In this thesis we propose a new approach to deduction methods for temporal logic. Our proposal is based on an inductive definition of eventualities that is different from the usual one. On the basis of this non-customary inductive definition for eventualities, we first provide dual systems of tableaux and sequents for Propositional Linear-time Temporal Logic (PLTL). Then, we adapt the deductive approach introduced by means of these dual tableau and sequent systems to the resolution framework and we present a clausal temporal resolution method for PLTL. Finally, we make use of this new clausal temporal resolution method for establishing logical foundations for declarative temporal logic programming languages. The key element in the deduction systems for temporal logic is to deal with eventualities and hidden invariants that may prevent the fulfillment of eventualities. Different ways of addressing this issue can be found in the works on deduction systems for temporal logic. Traditional tableau systems for temporal logic generate an auxiliary graph in a first pass.Then, in a second pass, unsatisfiable nodes are pruned. In particular, the second pass must check whether the eventualities are fulfilled. The one-pass tableau calculus introduced by S. Schwendimann requires an additional handling of information in order to detect cyclic branches that contain unfulfilled eventualities. Regarding traditional sequent calculi for temporal logic, the issue of eventualities and hidden invariants is tackled by making use of a kind of inference rules (mainly, invariant-based rules or infinitary rules) that complicates their automation. A remarkable consequence of using either a two-pass approach based on auxiliary graphs or aone-pass approach that requires an additional handling of information in the tableau framework, and either invariant-based rules or infinitary rules in the sequent framework, is that temporal logic fails to carry out the classical correspondence between tableaux and sequents. In this thesis, we first provide a one-pass tableau method TTM that instead of a graph obtains a cyclic tree to decide whether a set of PLTL-formulas is satisfiable. In TTM tableaux are classical-like. For unsatisfiable sets of formulas, TTM produces tableaux whose leaves contain a formula and its negation. In the case of satisfiable sets of formulas, TTM builds tableaux where each fully expanded open branch characterizes a collection of models for the set of formulas in the root. The tableau method TTM is complete and yields a decision procedure for PLTL. This tableau method is directly associated to a one-sided sequent calculus called TTC. Since TTM is free from all the structural rules that hinder the mechanization of deduction, e.g. weakening and contraction, then the resulting sequent calculus TTC is also free from this kind of structural rules. In particular, TTC is free of any kind of cut, including invariant-based cut. From the deduction system TTC, we obtain a two-sided sequent calculus GTC that preserves all these good freeness properties and is finitary, sound and complete for PLTL. Therefore, we show that the classical correspondence between tableaux and sequent calculi can be extended to temporal logic. The most fruitful approach in the literature on resolution methods for temporal logic, which was started with the seminal paper of M. Fisher, deals with PLTL and requires to generate invariants for performing resolution on eventualities. In this thesis, we present a new approach to resolution for PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Our method is based on the dual methods of tableaux and sequents for PLTL mentioned above. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called TRS-resolution, that extends classical propositional resolution. Finally, we prove that TRS-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL. In the field of temporal logic programming, the declarative proposals that provide a completeness result do not allow eventualities, whereas the proposals that follow the imperative future approach either restrict the use of eventualities or deal with them by calculating an upper bound based on the small model property for PLTL. In the latter, when the length of a derivation reaches the upper bound, the derivation is given up and backtracking is used to try another possible derivation. In this thesis we present a declarative propositional temporal logic programming language, called TeDiLog, that is a combination of the temporal and disjunctive paradigms in Logic Programming. We establish the logical foundations of our proposal by formally defining operational and logical semantics for TeDiLog and by proving their equivalence. Since TeDiLog is, syntactically, a sublanguage of PLTL, the logical semantics of TeDiLog is supported by PLTL logical consequence. The operational semantics of TeDiLog is based on TRS-resolution. TeDiLog allows both eventualities and always-formulas to occur in clause heads and also in clause bodies. To the best of our knowledge, TeDiLog is the first declarative temporal logic programming language that achieves this high degree of expressiveness. Since the tableau method presented in this thesis is able to detect that the fulfillment of an eventuality is prevented by a hidden invariant without checking for it by means of an extra process, since our finitary sequent calculi do not include invariant-based rules and since our resolution method dispenses with invariant generation, we say that our deduction methods are invariant-free.

Training-free probability models for whole-image based place recognition

Whole-image descriptors such as GIST have been used successfully for persistent place recognition when combined with temporal filtering or sequential filtering techniques. However, whole-image descriptor localization systems often apply a heuristic rather than a probabilistic approach to place recognition, requiring substantial environmental-specific tuning prior to deployment. In this paper we present a novel online solution that uses statistical approaches to calculate place recognition likelihoods for whole-image descriptors, without requiring either environmental tuning or pre-training. Using a real world benchmark dataset, we show that this method creates distributions appropriate to a specific environment in an online manner. Our method performs comparably to FAB-MAP in raw place recognition performance, and integrates into a state of the art probabilistic mapping system to provide superior performance to whole-image methods that are not based on true probability distributions. The method provides a principled means for combining the powerful change-invariant properties of whole-image descriptors with probabilistic back-end mapping systems without the need for prior training or system tuning.

Towards Vision-Based Pose- and Condition-Invariant Place Recognition along Routes

Vision-based place recognition involves recognising familiar places despite changes in environmental conditions or camera viewpoint (pose). Existing training-free methods exhibit excellent invariance to either of these challenges, but not both simultaneously. In this paper, we present a technique for condition-invariant place recognition across large lateral platform pose variance for vehicles or robots travelling along routes. Our approach combines sideways facing cameras with a new multi-scale image comparison technique that generates synthetic views for input into the condition-invariant Sequence Matching Across Route Traversals (SMART) algorithm. We evaluate the system’s performance on multi-lane roads in two different environments across day-night cycles. In the extreme case of day-night place recognition across the entire width of a four-lane-plus-median-strip highway, we demonstrate performance of up to 44% recall at 100% precision, where current state-of-the-art fails.

Quantum-Ohmic Resistance Fluctuation In Disordered Conductors - An Invariant Imbedding Approach

It is now well known that in extreme quantum limit, dominated by the elastic impurity scattering and the concomitant quantum interference, the zero-temperature d.c. resistance of a strictly one-dimensional disordered system is non-additive and non-self-averaging. While these statistical fluctuations may persist in the case of a physically thin wire, they are implicitly and questionably ignored in higher dimensions. In this work, we have re-examined this question. Following an invariant imbedding formulation, we first derive a stochastic differential equation for the complex amplitude reflection coefficient and hence obtain a Fokker-Planck equation for the full probability distribution of resistance for a one-dimensional continuum with a Gaussian white-noise random potential. We then employ the Migdal-Kadanoff type bond moving procedure and derive the d-dimensional generalization of the above probability distribution, or rather the associated cumulant function –‘the free energy’. For d=3, our analysis shows that the dispersion dominates the mobilitly edge phenomena in that (i) a one-parameter B-function depending on the mean conductance only does not exist, (ii) an approximate treatment gives a diffusion-correction involving the second cumulant. It is, however, not clear whether the fluctuations can render the transition at the mobility edge ‘first-order’. We also report some analytical results for the case of the one dimensional system in the presence of a finite electric fiekl. We find a cross-over from the exponential to the power-low length dependence of resistance as the field increases from zero. Also, the distribution of resistance saturates asymptotically to a poissonian form. Most of our analytical results are supported by the recent numerical simulation work reported by some authors.

Free and ATP-bound structures of Ap(4)A hydrolase from Aquifex aeolicus V5

Asymmetric diadenosine tetraphosphate (Ap(4)A) hydrolases degrade the metabolite Ap(4)A back into ATP and AMP. The three-dimensional crystal structure of Ap(4)A hydrolase (16 kDa) from Aquifex aeolicus has been determined in free and ATP-bound forms at 1.8 and 1.95 angstrom resolution, respectively. The overall three-dimensional crystal structure of the enzyme shows an alpha beta alpha-sandwich architecture with a characteristic loop adjacent to the catalytic site of the protein molecule. The ATP molecule is bound in the primary active site and the adenine moiety of the nucleotide binds in a ring-stacking arrangement equivalent to that observed in the X-ray structure of Ap(4)A hydrolase from Caenorhabditis elegans. Binding of ATP in the active site induces local conformational changes which may have important implications in the mechanism of substrate recognition in this class of enzymes. Furthermore, two invariant water molecules have been identified and their possible structural and/or functional roles are discussed. In addition, modelling of the substrate molecule at the primary active site of the enzyme suggests a possible path for entry and/or exit of the substrate and/or product molecule.

Free-volume dependent pressure sensitivity of Zr-based bulk metallic glass

Instrumented indentation experiments on a Zr-based bulk metallic glass (BMG) in as-cast, shot-peened and structurally relaxed conditions were conducted to examine the dependence of plastic deformation on its structural state. Results show significant differences in hardness, H, with structural relaxation increasing it and shot peening markedly reducing it, and slightly changed morphology of shear bands around the indents. This is in contrast to uniaxial compressive yield strength, sigma(y), which remains invariant with the change in the structural state of the alloys investigated. The plastic constraint factor, C = H/sigma(y), of the relaxed BMG increases compared with that of the as-cast glass, indicating enhanced pressure sensitivity upon annealing. In contrast, C of the shot-peened layer was found to be similar to that observed in crystalline metals, indicating that severe plastic deformation could eliminate pressure sensitivity. Microscopic origins for this result, in terms of shear transformation zones and free volume, are discussed.

Conjugacy invariant pseudo-norms, representability and RNA secondary structures

To a reasonable approximation, a secondary structures of RNA is determined by Watson-Crick pairing without pseudo-knots in such a way as to minimise the number of unpaired bases: We show that this minimal number is determined by the maximal conjugacy-invariant pseudo-norm on the free group on two generators subject to bounds on the generators. This allows us to construct lower bounds on the minimal number of unpaired bases by constructing conjugacy invariant pseudo-norms. We show that one such construction, based on isometric actions on metric spaces, gives a sharp lower bound. A major goal here is to formulate a purely mathematical question, based on considering orthogonal representations, which we believe is of some interest independent of its biological roots.

Exact Phase Retrieval in Principal Shift-Invariant Spaces

We address the problem of phase retrieval from Fourier transform magnitude spectrum for continuous-time signals that lie in a shift-invariant space spanned by integer shifts of a generator kernel. The phase retrieval problem for such signals is formulated as one of reconstructing the combining coefficients in the shift-invariant basis expansion. We develop sufficient conditions on the coefficients and the bases to guarantee exact phase retrieval, by which we mean reconstruction up to a global phase factor. We present a new class of discrete-domain signals that are not necessarily minimum-phase, but allow for exact phase retrieval from their Fourier magnitude spectra. We also establish Hilbert transform relations between log-magnitude and phase spectra for this class of discrete signals. It turns out that the corresponding continuous-domain counterparts need not satisfy a Hilbert transform relation; notwithstanding, the continuous-domain signals can be reconstructed from their Fourier magnitude spectra. We validate the reconstruction guarantees through simulations for some important classes of signals such as bandlimited signals and piecewise-smooth signals. We also present an application of the proposed phase retrieval technique for artifact-free signal reconstruction in frequency-domain optical-coherence tomography (FDOCT).

Gauge Invariant Spectral Cauchy Characteristic Extraction of Gravitational Waves in Computational General Relativity

We present a complete system for Spectral Cauchy characteristic extraction (Spectral CCE). Implemented in C++ within the Spectral Einstein Code (SpEC), the method employs numerous innovative algorithms to efficiently calculate the Bondi strain, news, and flux.

Spectral CCE was envisioned to ensure physically accurate gravitational wave-forms computed for the Laser Interferometer Gravitational wave Observatory (LIGO) and similar experiments, while working toward a template bank with more than a thousand waveforms to span the binary black hole (BBH) problem’s seven-dimensional parameter space.

The Bondi strain, news, and flux are physical quantities central to efforts to understand and detect astrophysical gravitational wave sources within the Simulations of eXtreme Spacetime (SXS) collaboration, with the ultimate aim of providing the first strong field probe of the Einstein field equation.

In a series of included papers, we demonstrate stability, convergence, and gauge invariance. We also demonstrate agreement between Spectral CCE and the legacy Pitt null code, while achieving a factor of 200 improvement in computational efficiency.

Spectral CCE represents a significant computational advance. It is the foundation upon which further capability will be built, specifically enabling the complete calculation of junk-free, gauge-free, and physically valid waveform data on the fly within SpEC.

Norbornenyl- and nortricyclyl free radicals

The number, symmetry, and product-forming capabilities of the intermediates in the photoinitiated reductions of endo- and exo-5- bromonorbornene and 2-bromonortricyclene with tri-n-butyltin hydride at temperatures between -10° and 22° were investigated.

Three mechanisms were evaluated:

1. The 5-norbornenyl- and 2-nortricyclyl radicals isomerize reversibly with the former producing nortricyclene by abstraction of hydrogen from tri-n-butyltin hydride.

2. The 5-norbornenyl- and 2-nortricyclyl radicals isomerize reversibly, but some norbornene can be formed from the 2-nortricyclyl radical or some nortricyclene can be formed from the 5-norbornenyl radical by abstraction of hydrogen.

3. There is intervention of a "bridged" radical which may be for med reversibly or irreversibly from the 5-norbornenyl- and 2-nortricyclyl radicals.

Within small error limits, the ratios of norbornene to nortricyclene as a function of the concentration of tri-n-butyltin hydride are consistent with the first mechanism.

In the reductions with tri-n-butyltin deuteride, primary deuterium isotope effects of 2. 3 and 2. 1 for the abstraction of deuterium by the 2-nortricyclyl- and 5-norbornenyl radicals, respectively, were found. The primary deuterium isotope effects were invariant with the concentration of tri-n-butyltin deuteride, although the ratios of norbornene to nortricyclene changed appreciably over this range. This is consistent with the first mechanism, and can accommodate the formation of either product from more than one intermediate only if the primary kinetic deuterium isotope effects are nearly equal for all reactions leading to the single product.

The reduction of endo-5-bromonorbornene-5, 6, 6-d₃ with tri-n-butyltin hydride or tri-n-butyltin deuteride leads to both unrearranged and rearranged norbornenes. The ratios of unrearranged to rearranged norbornene require that the 5-norbornenyl-5, 6, 6-d₃ radical isomerize to an intermediate with the symmetry expected of a nortricyclyl free radical. The results are consistent with mechanism 1, but imply a surprising normal secondary kinetic deuterium isotope effect of about 1.25 for the abstraction of hydrogen by the 5-norbornenyl- 5, 6, 6-d₃ radical.

Approximate calculations show that there does not appear to be any substantial difference in the stabilities of the 5-norbornenyl and 2-nortricyclyl radicals.

Although the results can not exclude a small contribution by a mechanism other than mechanism 1, no such contribution is required to adequately explain the results.

Topologically invariant reaction coordinates for simulating multistate chemical reactions.

Evaluating free energy profiles of chemical reactions in complex environments such as solvents and enzymes requires extensive sampling, which is usually performed by potential of mean force (PMF) techniques. The reliability of the sampling depends not only on the applied PMF method but also the reaction coordinate space within the dynamics is biased. In contrast to simple geometrical collective variables that depend only on the positions of the atomic coordinates of the reactants, the E(gap) reaction coordinate (the energy difference obtained by evaluating a suitable force field using reactant and product state topologies) has the unique property that it is able to take environmental effects into account leading to better convergence, a more faithful description of the transition state ensemble and therefore more accurate free energy profiles. However, E(gap) requires predefined topologies and is therefore inapplicable for multistate reactions, in which the barrier between the chemically equivalent topologies is comparable to the reaction activation barrier, because undesired "side reactions" occur. In this article, we introduce a new energy-based collective variable by generalizing the E(gap) reaction coordinate such that it becomes invariant to equivalent topologies and show that it yields more well behaved free energy profiles than simpler geometrical reaction coordinates.

Size invariant measures of association: characterization and difficulties

A measure of association is row-size invariant if it is unaffected by the multiplication of all entries in a row of a cross-classification table by a same positive number. It is class-size invariant if it is unaffected by the multiplication of all entries in a class (i.e., a row or a column). We prove that every class-size invariant measure of association as-signs to each m x n cross-classification table a number which depends only on the cross-product ratios of its 2 x 2 subtables. We propose a monotonicity axiom requiring that the degree of association should increase after shifting mass from cells of a table where this mass is below its expected value to cells where it is above .provided that total mass in each class remains constant. We prove that no continuous row-size invariant measure of association is monotonic if m ≥ 4. Keywords: association, contingency tables, margin-free measures, size invariance, monotonicity, transfer principle.

Spectral invariant behavior of zenith radiance around cloud edges observed by ARM SWS

The ARM Shortwave Spectrometer (SWS) measures zenith radiance at 418 wavelengths between 350 and 2170 nm. Because of its 1-sec sampling resolution, the SWS provides a unique capability to study the transition zone between cloudy and clear sky areas. A spectral invariant behavior is found between ratios of zenith radiance spectra during the transition from cloudy to cloud-free. This behavior suggests that the spectral signature of the transition zone is a linear mixture between the two extremes (definitely cloudy and definitely clear). The weighting function of the linear mixture is a wavelength-independent characteristic of the transition zone. It is shown that the transition zone spectrum is fully determined by this function and zenith radiance spectra of clear and cloudy regions. An important result of these discoveries is that high temporal resolution radiance measurements in the clear-to-cloud transition zone can be well approximated by lower temporal resolution measurements plus linear interpolation.