@inproceedings{496, abstract = {We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.}, author = {Rabinovich, Alexander and Rubin, Sasha}, location = {Dubrovnik, Croatia}, publisher = {IEEE}, title = {{Interpretations in trees with countably many branches}}, doi = {10.1109/LICS.2012.65}, year = {2012}, } @inproceedings{497, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, location = {Fontainebleau, France}, pages = {167 -- 182}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.4230/LIPIcs.CSL.2012.167}, volume = {16}, year = {2012}, } @article{498, abstract = {Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.}, author = {Pickup, Melinda and Field, David and Rowell, David and Young, Andrew}, journal = {Evolutionary Applications}, number = {8}, pages = {913 -- 924}, publisher = {Wiley-Blackwell}, title = {{Predicting local adaptation in fragmented plant populations: Implications for restoration genetics}}, doi = {10.1111/j.1752-4571.2012.00284.x}, volume = {5}, year = {2012}, } @article{506, author = {Sixt, Michael K}, journal = {Journal of Cell Biology}, number = {3}, pages = {347 -- 349}, publisher = {Rockefeller University Press}, title = {{Cell migration: Fibroblasts find a new way to get ahead}}, doi = {10.1083/jcb.201204039}, volume = {197}, year = {2012}, } @misc{5377, abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.}, author = {Chatterjee, Krishnendu and Velner, Yaron}, issn = {2664-1690}, pages = {33}, publisher = {IST Austria}, title = {{Mean-payoff pushdown games}}, doi = {10.15479/AT:IST-2012-0002}, year = {2012}, } @misc{5378, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, issn = {2664-1690}, pages = {21}, publisher = {IST Austria}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.15479/AT:IST-2012-0001}, year = {2012}, } @article{12649, abstract = {Physically based hydrological models describe natural processes more accurately than conceptual models but require extensive data sets to produce accurate results. To identify the value of different data sets for improving the performance of the distributed hydrological model TOPKAPI we combine a multivariable validation technique with Monte Carlo simulations. The study is carried out in the snow and ice-dominated Rhonegletscher basin, as these types of mountainous basins are generally the most critical with respect to data availability and sensitivity to climate fluctuations. Each observational data set is used individually and in combination with the other data sets to determine a subset of best parameter combinations out of 10,000 Monte Carlos runs performed with randomly generated parameter sets. We validate model results against discharge, glacier mass balance, and satellite snow cover images for a 14 year time period (1994–2007). While the use of all data sets combined provides the best overall model performance (defined by the concurrent best agreement of simulated discharge, snow cover and mass balance with their respective measurements), the use of one or two variables for constraining the model results in poorer performance. Using only one data set for constraining the model glacier mass balance proved to be the most efficient observation leading to the best overall model performance. Our main result is that a combination of discharge and satellite snow cover images is best for improving model performance, since the volumetric information of discharge data and the spatial information of snow cover images are complementary.}, author = {Finger, David and Pellicciotti, Francesca and Konz, Markus and Rimkus, Stefan and Burlando, Paolo}, issn = {0043-1397}, journal = {Water Resources Research}, number = {7}, publisher = {American Geophysical Union}, title = {{The value of glacier mass balance, satellite snow cover images, and hourly discharge for improving the performance of a physically based distributed hydrological model}}, doi = {10.1029/2010wr009824}, volume = {47}, year = {2011}, } @inbook{12650, abstract = {Streamflow is a hydrological variable measured at a defined river cross-section; it spatially integrates the runoff generating processes in the contributing watershed, including precipitation and air temperature. Trends in streamflow are progressive changes in the time series of streamflow that can be detected with statistical methods and their statistical significance can be assessed. Mountainous regions are particularly vulnerable to streamflow change because of their high specific runoff and the sensitivity to the distribution of precipitation and air temperature, and the processes of snow accumulation and melt.}, author = {Molnar, Peter and Burlando, Paolo and Pellicciotti, Francesca}, booktitle = {Encyclopedia of Snow, Ice and Glaciers}, editor = {Singh, Vijay and Singh, Pratap and Haritashya, Umesh}, isbn = {978-90-481-2641-5}, issn = {1871-756X}, pages = {1084--1089}, publisher = {Springer Nature}, title = {{Streamflow Trends in Mountainous Regions}}, doi = {10.1007/978-90-481-2642-2_543}, year = {2011}, } @article{12651, abstract = {Temperature data from three Automatic Weather Stations and twelve Temperature Loggers are used to investigate the spatiotemporal variability of temperature over a glacier, its main atmospheric controls, the suitability of extrapolation techniques and their effect on melt modeling. We use data collected on Juncal Norte Glacier, central Chile, during one ablation season. We examine temporal and spatial variability in lapse rates (LRs), together with alternative statistical interpolation methods. The main control over the glacier thermal regime is the development of a katabatic boundary layer (KBL). Katabatic wind occurs at night and in the morning and is eroded in the afternoon. LRs reveal strong diurnal variability, with steeper LRs during the day when the katabatic wind weakens and shallower LRs during the night and morning. We suggest that temporally variable LRs should be used to account for the observed change. They tend to be steeper than equivalent constant LRs, and therefore result in a reduction in simulated melt compared to use of constant LRs when extrapolating from lower to higher elevations. In addition to the temporal variability, the temperature-elevation relationship varies also in space. Differences are evident between local LRs and including such variability in melt modeling affects melt simulations. Extrapolation methods based on the spatial variability of the observations after removal of the elevation trend, such as Inverse Distance Weighting or Kriging, do not seem necessary for simulations of gridded temperature data over a glacier.}, author = {Petersen, L. and Pellicciotti, Francesca}, issn = {0148-0227}, journal = {Journal of Geophysical Research: Atmospheres}, keywords = {Paleontology, Space and Planetary Science, Earth and Planetary Sciences (miscellaneous), Atmospheric Science, Earth-Surface Processes, Geochemistry and Petrology, Soil Science, Water Science and Technology, Ecology, Aquatic Science, Forestry, Oceanography, Geophysics}, number = {D23}, publisher = {American Geophysical Union}, title = {{Spatial and temporal variability of air temperature on a melting glacier: Atmospheric controls, extrapolation methods and their effect on melt modeling, Juncal Norte Glacier, Chile}}, doi = {10.1029/2011jd015842}, volume = {116}, year = {2011}, } @article{12652, abstract = {We explore the robustness and transferability of parameterizations of cloud radiative forcing used in glacier melt models at two sites in the Swiss Alps. We also look at the rationale behind some of the most commonly used approaches, and explore the relationship between cloud transmittance and several standard meteorological variables. The 2 m air-temperature diurnal range is the best predictor of variations in cloud transmittance. However, linear and exponential parameterizations can only explain 30–50% of the observed variance in computed cloud transmittance factors. We examine the impact of modelled cloud transmittance factors on both solar radiation and ablation rates computed with an enhanced temperature-index model. The melt model performance decreases when modelled radiation is used, the reduction being due to an underestimation of incoming solar radiation on clear-sky days. The model works well under overcast conditions. We also seek alternatives to the use of in situ ground data. However, outputs from an atmospheric model (2.2 km horizontal resolution) do not seem to provide an alternative to the parameterizations of cloud radiative forcing based on observations of air temperature at glacier automatic weather stations. Conversely, the correct definition of overcast conditions is important.}, author = {Pellicciotti, Francesca and Raschle, Thomas and Huerlimann, Thomas and Carenzo, Marco and Burlando, Paolo}, issn = {1727-5652}, journal = {Journal of Glaciology}, number = {202}, pages = {367--381}, publisher = {Cambridge University Press}, title = {{Transmission of solar radiation through clouds on melting glaciers: A comparison of parameterizations and their impact on melt modelling}}, doi = {10.3189/002214311796406013}, volume = {57}, year = {2011}, } @article{1299, abstract = {Recent experiments have shown that motion detection in Drosophila starts with splitting the visual input into two parallel channels encoding brightness increments (ON) or decrements (OFF). This suggests the existence of either two (ON-ON, OFF-OFF) or four (for all pairwise interactions) separate motion detectors. To decide between these possibilities, we stimulated flies using sequences of ON and OFF brightness pulses while recording from motion-sensitive tangential cells. We found direction-selective responses to sequences of same sign (ON-ON, OFF-OFF), but not of opposite sign (ON-OFF, OFF-ON), refuting the existence of four separate detectors. Based on further measurements, we propose a model that reproduces a variety of additional experimental data sets, including ones that were previously interpreted as support for four separate detectors. Our experiments and the derived model mark an important step in guiding further dissection of the fly motion detection circuit.}, author = {Eichner, Hubert and Maximilian Jösch and Schnell, Bettina and Reiff, Dierk F and Borst, Alexander}, journal = {Neuron}, number = {6}, pages = {1155 -- 1164}, publisher = {Elsevier}, title = {{Internal structure of the fly elementary motion detector}}, doi = {10.1016/j.neuron.2011.03.028}, volume = {70}, year = {2011}, } @article{8464, abstract = {Nonsymmetric motion: Solid‐state NMR measurements of dipolar coupling tensors provide insight into protein dynamics. The hitherto ignored asymmetry of the dipolar coupling tensor contains valuable information about motional asymmetry, which was used in the first direct site‐resolved measurement of such tensors. Important motions such as rotamer jumps can now be directly detected in the solid state.}, author = {Schanda, Paul and Huber, Matthias and Boisbouvier, Jérôme and Meier, Beat H. and Ernst, Matthias}, issn = {1433-7851}, journal = {Angewandte Chemie International Edition}, number = {46}, pages = {11005--11009}, publisher = {Wiley}, title = {{Solid-state NMR measurements of asymmetric dipolar couplings provide insight into protein side-chain motion}}, doi = {10.1002/anie.201103944}, volume = {50}, year = {2011}, } @article{8468, author = {Lalli, Daniela and Schanda, Paul and Chowdhury, Anup and Retel, Joren and Hiller, Matthias and Higman, Victoria A. and Handel, Lieselotte and Agarwal, Vipin and Reif, Bernd and van Rossum, Barth and Akbey, Ümit and Oschkinat, Hartmut}, issn = {0925-2738}, journal = {Journal of Biomolecular NMR}, number = {4}, pages = {477--485}, publisher = {Springer Nature}, title = {{Three-dimensional deuterium-carbon correlation experiments for high-resolution solid-state MAS NMR spectroscopy of large proteins}}, doi = {10.1007/s10858-011-9578-1}, volume = {51}, year = {2011}, } @article{8469, abstract = {The accurate experimental determination of dipolar-coupling constants for one-bond heteronuclear dipolar couplings in solids is a key for the quantification of the amplitudes of motional processes. Averaging of the dipolar coupling reports on motions on time scales up to the inverse of the coupling constant, in our case tens of microseconds. Combining dipolar-coupling derived order parameters that characterize the amplitudes of the motion with relaxation data leads to a more precise characterization of the dynamical parameters and helps to disentangle the amplitudes and the time scales of the motional processes, which impact relaxation rates in a highly correlated way. Here. we describe and characterize an improved experimental protocol – based on REDOR – to measure these couplings in perdeuterated proteins with a reduced sensitivity to experimental missettings. Because such effects are presently the dominant source of systematic errors in experimental dipolar-coupling measurements, these compensated experiments should help to significantly improve the precision of such data. A detailed comparison with other commonly used pulse sequences (T-MREV, phase-inverted CP,R18 5/2, and R18 7/1) is provided.}, author = {Schanda, Paul and Meier, Beat H. and Ernst, Matthias}, issn = {1090-7807}, journal = {Journal of Magnetic Resonance}, keywords = {Nuclear and High Energy Physics, Biophysics, Biochemistry, Condensed Matter Physics}, number = {2}, pages = {246--259}, publisher = {Elsevier}, title = {{Accurate measurement of one-bond H–X heteronuclear dipolar couplings in MAS solid-state NMR}}, doi = {10.1016/j.jmr.2011.03.015}, volume = {210}, year = {2011}, } @article{8470, abstract = {Adding a new dimension: 4D or 3D proton‐detected spectra of perdeuterated protein samples with 1H labelled amides and methyl groups permit collecting unambiguous distance restraints with high sensitivity and determining protein structure by solid‐state NMR (see picture).}, author = {Huber, Matthias and Hiller, Sebastian and Schanda, Paul and Ernst, Matthias and Böckmann, Anja and Verel, René and Meier, Beat H.}, issn = {1439-4235}, journal = {ChemPhysChem}, keywords = {Physical and Theoretical Chemistry, Atomic and Molecular Physics, and Optics}, number = {5}, pages = {915--918}, publisher = {Wiley}, title = {{A proton-detected 4D solid-state NMR experiment for protein structure determination}}, doi = {10.1002/cphc.201100062}, volume = {12}, year = {2011}, } @article{8471, abstract = {Despite the importance of protein fibrils in the context of conformational diseases, information on their structure is still sparse. Hydrogen/deuterium exchange measurements of backbone amide protons allow the identification hydrogen-bonding patterns and reveal pertinent information on the amyloid β-sheet architecture. However, they provide only little information on the identity of residues exposed to solvent or buried inside the fibril core. NMR spectroscopy is a potent method for identifying solvent-accessible residues in proteins via observation of polarization transfer between chemically exchanging side-chain protons and water protons. We show here that the combined use of highly deuterated samples and fast magic-angle spinning greatly attenuates unwanted spin diffusion and allows identification of polarization exchange with the solvent in a site-specific manner. We apply this measurement protocol to HET-s(218–289) prion fibrils under different conditions (including physiological pH, where protofibrils assemble together into thicker fibrils) and demonstrate that each protofibril of HET-s(218–289), is surrounded by water, thus excluding the existence of extended dry interfibril contacts. We also show that exchangeable side-chain protons inside the hydrophobic core of HET-s(218–289) do not exchange over time intervals of weeks to months. The experiments proposed in this study can provide insight into the detailed structural features of amyloid fibrils in general.}, author = {Van Melckebeke, Hélène and Schanda, Paul and Gath, Julia and Wasmer, Christian and Verel, René and Lange, Adam and Meier, Beat H. and Böckmann, Anja}, issn = {0022-2836}, journal = {Journal of Molecular Biology}, number = {3}, pages = {765--772}, publisher = {Elsevier}, title = {{Probing water accessibility in HET-s(218–289) amyloid fibrils by solid-state NMR}}, doi = {10.1016/j.jmb.2010.11.004}, volume = {405}, year = {2011}, } @article{8505, abstract = {The classical principle of least action says that orbits of mechanical systems extremize action; an important subclass are those orbits that minimize action. In this paper we utilize this principle along with Aubry-Mather theory to construct (Birkhoff) regions of instability for a certain three-body problem, given by a Hamiltonian system of 2 degrees of freedom. We believe that these methods can be applied to construct instability regions for a variety of Hamiltonian systems with 2 degrees of freedom. The Hamiltonian model we consider describes dynamics of a Sun-Jupiter-comet system, and under some simplifying assumptions, we show the existence of instabilities for the orbit of the comet. In particular, we show that a comet which starts close to an orbit in the shape of an ellipse of eccentricity e=0.66 can increase in eccentricity up to e=0.96. In the sequels to this paper, we extend the result to beyond e=1 and show the existence of ejection orbits. Such orbits are initially well within the range of our solar system. This might give an indication of why most objects rotating around the Sun in our solar system have relatively low eccentricity.}, author = {Galante, Joseph and Kaloshin, Vadim}, issn = {0012-7094}, journal = {Duke Mathematical Journal}, keywords = {General Mathematics}, number = {2}, pages = {275--327}, publisher = {Duke University Press}, title = {{Destruction of invariant curves in the restricted circular planar three-body problem by using comparison of action}}, doi = {10.1215/00127094-1415878}, volume = {159}, year = {2011}, } @inbook{881, author = {Fyodor Kondrashov}, booktitle = {Evolution after Gene Duplication}, pages = {57 -- 76}, publisher = {Wiley-Blackwell}, title = {{Gene Dosage and Duplication}}, doi = {10.1002/9780470619902.ch4}, year = {2011}, } @article{890, abstract = {Recent discovery of the Large-billed Reed Warbler (Acrocephalus orinus) in museums and in the wild significantly expanded our knowledge of its morphological traits and genetic variability, and revealed new data on geographical distribution of the breeding grounds, migration routes and wintering locations of this species. It is now certain that A. orinus is breeding in Central Asia; however, the precise area of distribution remains unclear. The difficulty in the further study of this species lies in the small number of known specimens, with only 13 currently available in museums, and in the relative uncertainty of the breeding area and habitat of this species. Following morphological and genetic analyses from Svensson, et al, we describe 14 new A. orinus specimens from collections of Zoological Museums of the former USSR from the territory of Central Asian states. All of these specimens were erroneously labeled as Blyth's Reed Warbler (A. dumetorum), which is thought to be a breeding species in these areas. The 14 new A. orinus specimens were collected during breeding season while most of the 85 A. dumetorum specimens from the same area were collected during the migration period. Our data indicate that the Central Asian territory previously attributed as breeding grounds of A. dumetorum is likely to constitute the breeding territory of A. orinus. This rare case of a re-description of the breeding territory of a lost species emphasizes the importance of maintenance of museum collections around the world. If the present data on the breeding grounds of A. orinus are confirmed with field observations and collections, the literature on the biology of A. dumetorum from the southern part of its range may have to be reconsidered.}, author = {Koblik, Evgeniy A and Red'Kin, Yaroslav A and Meer, Margarita S and Derelle, Romain and Golenkina, Sofia A and Fyodor Kondrashov and Arkhipov, Vladimir Y}, journal = {PLoS One}, number = {4}, publisher = {Public Library of Science}, title = {{Acrocephalus orinus: A case of Mistaken identity}}, doi = {10.1371/journal.pone.0017716}, volume = {6}, year = {2011}, } @article{90, abstract = {A popular method for generating micron-sized aerosols is to submerge ultrasonic (ω ∼ MHz) piezoelectric oscillators in a water bath. The submerged oscillator atomizes the fluid, creating droplets with radii proportional to the wavelength of the standing wave at the fluid surface. Classical theory for the Faraday instability predicts a parametric instability driving a capillary wave at the subharmonic (ω / 2) frequency. For many applications it is desirable to reduce the size of the droplets; however, using higher frequency oscillators becomes impractical beyond a few MHz. Observations are presented that demonstrate that smaller droplets may also be created by increasing the driving amplitude of the oscillator, and that this effect becomes more pronounced for large driving frequencies. It is shown that these observations are consistent with a transition from droplets associated with subharmonic (ω/2) capillary waves to harmonic (ω) capillary waves induced by larger driving frequencies and amplitudes, as predicted by a stability analysis of the capillary waves.}, author = {Higginbotham, Andrew P and Guillen, A and Jones, Nick and Donnelly, Tom and Bernoff, Andrew}, journal = {Journal of the Acoustical Society of America}, number = {5}, pages = {2694 -- 2699}, publisher = {Acoustical Society of America}, title = {{Evidence of the harmonic Faraday instability in ultrasonic atomization experiments with a deep, inviscid fluid}}, doi = {10.1121/1.3643816}, volume = {130}, year = {2011}, }