@misc{5384, abstract = {We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every ε > 0 there is a word that is accepted with probability at least 1 − ε. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions.}, author = {Chatterjee, Krishnendu and Tracol, Mathieu}, issn = {2664-1690}, pages = {30}, publisher = {IST Austria}, title = {{Decidable problems for probabilistic automata on infinite words}}, doi = {10.15479/AT:IST-2011-0004}, year = {2011}, } @inproceedings{3336, abstract = {We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.}, author = {Chen, Chao and Freedman, Daniel and Lampert, Christoph}, booktitle = {CVPR: Computer Vision and Pattern Recognition}, isbn = {978-1-4577-0394-2}, location = {Colorado Springs, CO, United States}, pages = {2089 -- 2096}, publisher = {IEEE}, title = {{Enforcing topological constraints in random field image segmentation}}, doi = {10.1109/CVPR.2011.5995503}, year = {2011}, } @inproceedings{3323, abstract = {We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.}, author = {Wies, Thomas and Muñiz, Marco and Kuncak, Viktor}, location = {Wrocław, Poland}, pages = {476 -- 491}, publisher = {Springer}, title = {{An efficient decision procedure for imperative tree data structures}}, doi = {10.1007/978-3-642-22438-6_36}, volume = {6803}, year = {2011}, } @inproceedings{3366, abstract = {We present an algorithmic method for the quantitative, performance-aware synthesis of concurrent programs. The input consists of a nondeterministic partial program and of a parametric performance model. The nondeterminism allows the programmer to omit which (if any) synchronization construct is used at a particular program location. The performance model, specified as a weighted automaton, can capture system architectures by assigning different costs to actions such as locking, context switching, and memory and cache accesses. The quantitative synthesis problem is to automatically resolve the nondeterminism of the partial program so that both correctness is guaranteed and performance is optimal. As is standard for shared memory concurrency, correctness is formalized "specification free", in particular as race freedom or deadlock freedom. For worst-case (average-case) performance, we show that the problem can be reduced to 2-player graph games (with probabilistic transitions) with quantitative objectives. While we show, using game-theoretic methods, that the synthesis problem is Nexp-complete, we present an algorithmic method and an implementation that works efficiently for concurrent programs and performance models of practical interest. We have implemented a prototype tool and used it to synthesize finite-state concurrent programs that exhibit different programming patterns, for several performance models representing different architectures. }, author = {Cerny, Pavol and Chatterjee, Krishnendu and Henzinger, Thomas A and Radhakrishna, Arjun and Singh, Rohit}, editor = {Gopalakrishnan, Ganesh and Qadeer, Shaz}, location = {Snowbird, USA}, pages = {243 -- 259}, publisher = {Springer}, title = {{Quantitative synthesis for concurrent programs}}, doi = {10.1007/978-3-642-22110-1_20}, volume = {6806}, year = {2011}, } @inproceedings{3345, abstract = {We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, location = {Warsaw, Poland}, pages = {206 -- 218}, publisher = {Springer}, title = {{Energy and mean-payoff parity Markov Decision Processes}}, doi = {10.1007/978-3-642-22993-0_21}, volume = {6907}, year = {2011}, } @misc{5387, abstract = {We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{Energy and mean-payoff parity Markov decision processes}}, doi = {10.15479/AT:IST-2011-0001}, year = {2011}, } @article{580, author = {Onur Hosten}, journal = {Nature}, number = {7350}, pages = {170 -- 171}, publisher = {Nature Publishing Group}, title = {{Quantum physics: How to catch a wave}}, doi = {10.1038/474170a}, volume = {474}, year = {2011}, } @inproceedings{585, abstract = {We present two independent schemes for the precise focusing of orthogonal polarizations of light at arbitrary relative locations. The first scheme uses a polarization Sagnac interferometer, the second a set of three birefringent elements. }, author = {Schmid, David and Hazrat, Shiraz and Rangarajan, Radhika and Onur Hosten and Quint, Stephan and Kwiat, Paul G}, publisher = {OSA}, title = {{Methods towards achieving precise birefringent focusing}}, doi = {10.1364/CLEO_AT.2011.JThB130}, year = {2011}, } @article{586, abstract = {We demonstrate a Raman laser using cold Rb87 atoms as the gain medium in a high-finesse optical cavity. We observe robust continuous wave lasing in the atypical regime where single atoms can considerably affect the cavity field. Consequently, we discover unusual lasing threshold behavior in the system causing jumps in lasing power, and propose a model to explain the effect. We also measure the intermode laser linewidth, and observe values as low as 80Hz. The tunable gain properties of this laser suggest multiple directions for future research.}, author = {Vrijsen, Geert and Onur Hosten and Lee, Jongmin and Bernon, Simon and Kasevich, Mark A}, journal = {Physical Review Letters}, number = {6}, publisher = {American Physical Society}, title = {{Raman lasing with a cold atom gain medium in a high-finesse optical cavity}}, doi = {10.1103/PhysRevLett.107.063904}, volume = {107}, year = {2011}, } @article{597, abstract = {The macromolecular assembly required to initiate transcription of protein-coding genes, known as the Pre-Initiation Complex (PIC), consists of multiple protein complexes and is approximately 3.5 MDa in size. At the heart of this assembly is the Mediator complex, which helps regulate PIC activity and interacts with the RNA polymerase II (pol II) enzyme. The structure of the human Mediator-pol II interface is not well-characterized, whereas attempts to structurally define the Mediator-pol II interaction in yeast have relied on incomplete assemblies of Mediator and/or pol II and have yielded inconsistent interpretations. We have assembled the complete, 1.9 MDa human Mediator-pol II-TFIIF complex from purified components and have characterized its structural organization using cryo-electron microscopy and single-particle reconstruction techniques. The orientation of pol II within this assembly was determined by crystal structure docking and further validated with projection matching experiments, allowing the structural organization of the entire human PIC to be envisioned. Significantly, pol II orientation within the Mediator-pol II-TFIIF assembly can be reconciled with past studies that determined the location of other PIC components relative to pol II itself. Pol II surfaces required for interacting with TFIIB, TFIIE, and promoter DNA (i.e., the pol II cleft) are exposed within the Mediator-pol II-TFIIF structure; RNA exit is unhindered along the RPB4/7 subunits; upstream and downstream DNA is accessible for binding additional factors; and no major structural re-organization is necessary to accommodate the large, multi-subunit TFIIH or TFIID complexes. The data also reveal how pol II binding excludes Mediator-CDK8 subcomplex interactions and provide a structural basis for Mediator-dependent control of PIC assembly and function. Finally, parallel structural analysis of Mediator-pol II complexes lacking TFIIF reveal that TFIIF plays a key role in stabilizing pol II orientation within the assembly.}, author = {Bernecky, Carrie A and Grob, Patricia and Ebmeier, Christopher and Nogales, Eva and Taatjes, Dylan}, journal = {PLoS Biology}, number = {3}, publisher = {Public Library of Science}, title = {{Molecular architecture of the human Mediator-RNA polymerase II-TFIIF assembly}}, doi = {10.1371/journal.pbio.1000603}, volume = {9}, year = {2011}, } @article{6140, abstract = {Genome sequence comparisons have highlighted many novel gene families that are conserved across animal phyla but whose biological function is unknown. Here, we functionally characterize a member of one such family, the macoilins. Macoilins are characterized by several highly conserved predicted transmembrane domains towards the N-terminus and by coiled-coil regions C-terminally. They are found throughout Eumetazoa but not in other organisms. Mutants for the single Caenorhabditis elegans macoilin, maco-1, exhibit a constellation of behavioral phenotypes, including defects in aggregation, O2 responses, and swimming. MACO-1 protein is expressed broadly and specifically in the nervous system and localizes to the rough endoplasmic reticulum; it is excluded from dendrites and axons. Apart from subtle synapse defects, nervous system development appears wild-type in maco-1 mutants. However, maco-1 animals are resistant to the cholinesterase inhibitor aldicarb and sensitive to levamisole, suggesting pre-synaptic defects. Using in vivo imaging, we show that macoilin is required to evoke Ca2+ transients, at least in some neurons: in maco-1 mutants the O2-sensing neuron PQR is unable to generate a Ca2+ response to a rise in O2. By genetically disrupting neurotransmission, we show that pre-synaptic input is not necessary for PQR to respond to O2, indicating that the response is mediated by cell-intrinsic sensory transduction and amplification. Disrupting the sodium leak channels NCA-1/NCA-2, or the N-,P/Q,R-type voltage-gated Ca2+ channels, also fails to disrupt Ca2+ responses in the PQR cell body to O2 stimuli. By contrast, mutations in egl-19, which encodes the only Caenorhabditis elegans L-type voltage-gated Ca2+ channel α1 subunit, recapitulate the Ca2+ response defect we see in maco-1 mutants, although we do not see defects in localization of EGL-19. Together, our data suggest that macoilin acts in the ER to regulate assembly or traffic of ion channels or ion channel regulators.}, author = {Arellano-Carbajal, Fausto and Briseño-Roa, Luis and Couto, Africa and Cheung, Benny H. H. and Labouesse, Michel and de Bono, Mario}, issn = {1553-7404}, journal = {PLoS Genetics}, number = {3}, publisher = {Public Library of Science}, title = {{Macoilin, a conserved nervous system–specific ER membrane protein that regulates neuronal excitability}}, doi = {10.1371/journal.pgen.1001341}, volume = {7}, year = {2011}, } @article{6137, abstract = {Variation in food quality and abundance requires animals to decide whether to stay on a poor food patch or leave in search of better food. An important question in behavioral ecology asks when is it optimal for an animal to leave a food patch it is depleting. Although optimal foraging is central to evolutionary success, the neural and molecular mechanisms underlying it are poorly understood. Here we investigate the neuronal basis for adaptive food-leaving behavior in response to resource depletion in Caenorhabditis elegans, and identify several of the signaling pathways involved. The ASE neurons, previously implicated in salt chemoattraction, promote food-leaving behavior via a cGMP pathway as food becomes limited. High ambient O2 promotes food-leaving via the O2-sensing neurons AQR, PQR, and URX. Ectopic activation of these neurons using channelrhodopsin is sufficient to induce high food-leaving behavior. In contrast, the neuropeptide receptor NPR-1, which regulates social behavior on food, acts in the ASE neurons, the nociceptive ASH neurons, and in the RMG interneuron to repress food-leaving. Finally, we show that neuroendocrine signaling by TGF-β/DAF-7 and neuronal insulin signaling are necessary for adaptive food-leaving behavior. We suggest that animals integrate information about their nutritional state with ambient oxygen and gustatory stimuli to formulate optimal foraging strategies.}, author = {Milward, K. and Busch, K. E. and Murphy, R. J. and de Bono, Mario and Olofsson, B.}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {51}, pages = {20672--20677}, publisher = {National Academy of Sciences}, title = {{Neuronal and molecular substrates for optimal foraging in Caenorhabditis elegans}}, doi = {10.1073/pnas.1106134109}, volume = {108}, year = {2011}, } @article{6138, author = {Bretscher, Andrew Jonathan and Kodama-Namba, Eiji and Busch, Karl Emanuel and Murphy, Robin Joseph and Soltesz, Zoltan and Laurent, Patrick and de Bono, Mario}, issn = {0896-6273}, journal = {Neuron}, number = {6}, pages = {1099--1113}, publisher = {Elsevier BV}, title = {{Temperature, oxygen, and salt-sensing neurons in C. elegans are carbon dioxide sensors that control avoidance behavior}}, doi = {10.1016/j.neuron.2011.02.023}, volume = {69}, year = {2011}, } @article{6298, abstract = {Tumor necrosis factor-stimulated gene-6 (TSG-6) is a hyalu-ronan (HA)-binding protein that plays important roles ininflammation and ovulation. TSG-6-mediated cross-linking ofHA has been proposed as a functional mechanism (e.g.for regu-lating leukocyte adhesion), but direct evidence for cross-linkingis lacking, and we know very little about its impact on HA ultra-structure. Here we used films of polymeric and oligomeric HAchains, end-grafted to a solid support, and a combination ofsurface-sensitive biophysical techniques to quantify the bindingof TSG-6 into HA films and to correlate binding to morpholog-ical changes. We find that full-length TSG-6 binds with pro-nounced positive cooperativity and demonstrate that it cancross-link HA at physiologically relevant concentrations. Ourdata indicate that cooperative binding of full-length TSG-6arises from HA-induced protein oligomerization and that theTSG-6 oligomers act as cross-linkers. In contrast, the HA-bind-ing domain of TSG-6 (the Link module) alone binds withoutpositive cooperativity and weaker than the full-length protein.Both the Link module and full-length TSG-6 condensed andrigidified HA films, and the degree of condensation scaled withthe affinity between the TSG-6 constructs and HA. We proposethat condensation is the result of protein-mediated HA cross-linking. Our findings firmly establish that TSG-6 is a potent HAcross-linking agent and might hence have important implica-tions for the mechanistic understanding of the biological func-tion of TSG-6 (e.g.in inflammation).}, author = {Baranova, Natalia and Nilebäck, Erik and Haller, F. Michael and Briggs, David C. and Svedhem, Sofia and Day, Anthony J. and Richter, Ralf P.}, issn = {0021-9258}, journal = {Journal of Biological Chemistry}, number = {29}, pages = {25675--25686}, publisher = {American Society for Biochemistry & Molecular Biology}, title = {{The inflammation-associated protein TSG-6 cross-links hyaluronan via hyaluronan-induced TSG-6 oligomers}}, doi = {10.1074/jbc.m111.247395}, volume = {286}, year = {2011}, } @article{6496, abstract = {We report the switching behavior of the full bacterial flagellum system that includes the filament and the motor in wild-type Escherichia coli cells. In sorting the motor behavior by the clockwise bias, we find that the distributions of the clockwise (CW) and counterclockwise (CCW) intervals are either exponential or nonexponential with long tails. At low bias, CW intervals are exponentially distributed and CCW intervals exhibit long tails. At intermediate CW bias (0.5) both CW and CCW intervals are mainly exponentially distributed. A simple model suggests that these two distinct switching behaviors are governed by the presence of signaling noise within the chemotaxis network. Low noise yields exponentially distributed intervals, whereas large noise yields nonexponential behavior with long tails. These drastically different motor statistics may play a role in optimizing bacterial behavior for a wide range of environmental conditions.}, author = {Park, Heungwon and Oikonomou, Panos and Guet, Calin C and Cluzel, Philippe}, issn = {0006-3495}, journal = {Biophysical Journal}, number = {10}, pages = {2336--2340}, publisher = {Elsevier}, title = {{Noise underlies switching behavior of the bacterial flagellum}}, doi = {10.1016/j.bpj.2011.09.040}, volume = {101}, year = {2011}, } @article{6749, abstract = {This article refers to algorithms based on finite difference schemes for computing mean and affine curvature evolutions of digital images, introduced by Alvarez and Morel [L. Alvarez, J.M. Morel, “Formalization and computational aspects of image analysis”, Acta Numerica, pp. 159, 1994]. We discuss consistency, stability and convergence. Our analysis focuses on some possible choices of the parameters, choices that generate multiple variants in the implementations. Meaningful visual examples on how the algorithms actually work are provided.}, author = {Mondelli, Marco and Ciomaga, Adina}, issn = {2105-1232}, journal = {Image Processing On Line}, pages = {127--177}, publisher = {IPOL Image Processing On Line}, title = {{Finite difference schemes for MCM and AMSS}}, doi = {10.5201/ipol.2011.cm_fds}, volume = {1}, year = {2011}, } @inproceedings{6767, abstract = {In the present paper we give a thorough analysis of two finite difference schemes for the Mean Curvature Motion and its affine variant, the Affine Morphological Scale Space, schemes introduced in the Image Processing framework. This analysis brings in a series of parameters that allow us to compute an accurate discrete evolution of curvature motions. The choice of these parameters is based on intrinsic geometric properties of the evolution equations for linear, radial and elliptical functions. In the last part we present several examples, underlining the main advantages of the algorithms (the removal of pixelization effects and JPEG artifacts) as well as their major drawbacks (absence of contrast invariance and grid dependence). A detailed explanatory report, the ANSI C implementations and an on-line demo can be found at http://www.ipol.im/.}, author = {Mondelli, Marco and Ciomaga, Adina}, booktitle = {Proceedings of the International Student Conference on Pure and Applied Mathematics}, isbn = {978-973-703-602-5}, location = {Iasi, Romania}, pages = {137--156}, publisher = {Editura Universitãtii „Alexandru Ioan Cuza” Iasi}, title = {{On finite difference schemes for curvature motions}}, doi = {10.13140/2.1.1862.4646}, year = {2011}, } @article{7076, abstract = {Iron is a ubiquitous impurity in metamict (radiation-damaged and partially amorphized) materials such as titanite (CaSiTiO5). Using 57Fe Mössbauer spectroscopy we find that iron in metamict titanite is partitioned between amorphous and crystalline regions based on valence. Trivalent iron exists in the crystalline titanite matrix whereas divalent iron exists almost exclusively in radiation-amorphized regions. We find that the relative abundances of the oxidation states correlate with the volume fraction of amorphous and crystalline regions. Our data also show that oxidation of iron proceeds along with the recrystallization of the amorphized regions. Recrystallization is confirmed to occur over the range 700 °C < T < 925 °C, and no further structural changes are observed at higher temperatures. It is surprising that our Mössbauer measurements show divalent iron to be surrounded by titanite with a high degree of short-range structural order in the amorphized regions. This observation is fundamentally different from other metamict materials such as zircon (ZrSiO4), where amorphized regions show no short-range order.}, author = {Salje, E K H and Safarik, D J and Taylor, R D and Pasternak, M P and Modic, Kimberly A and Groat, L A and Lashley, J C}, issn = {0953-8984}, journal = {Journal of Physics: Condensed Matter}, number = {10}, publisher = {IOP Publishing}, title = {{Determination of iron sites and the amount of amorphization in radiation-damaged titanite (CaSiTiO5)}}, doi = {10.1088/0953-8984/23/10/105402}, volume = {23}, year = {2011}, } @article{7077, abstract = {Pb, Te, Ag and Se, when reacted in a 1:1:x:1 (x = 1.9, 2.0, 2.01) molar ratio, form a two phase composite which consists of a phase which crystallizes in the fcc cubic PbSe structure and a phase that crystallizes in the Ag2Te structure. In this article, we demonstrate that by varying the Ag concentration, we can manipulate which variant of the Ag2Te structure stabilizes at room temperature (monoclinic α-Ag2Te or cubic β-Ag1.9Te) and can consequently manipulate the electrical and thermal transport behavior of the composite and hence the thermoelectric performance. Additionally, we show that Cu-doping results in an overall improvement in thermoelectric performance. Our results suggest that formation of composites is a viable path for achieving a phonon-glass-electron-crystal (PGEC) alloy.}, author = {Capps, J. and Ma, B. and Drye, T. and Nucklos, C. and Lindsey, S. and Rhodes, D. and Zhang, Q. and Modic, Kimberly A and Cawthorne, S. and Drymiotis, F.}, issn = {0925-8388}, journal = {Journal of Alloys and Compounds}, number = {5}, pages = {1544--1549}, publisher = {Elsevier}, title = {{The effect of Ag concentration on the structural, electrical and thermal transport behavior of Pb:Te:Ag:Se mixtures and improvement of thermoelectric performance via Cu doping}}, doi = {10.1016/j.jallcom.2010.10.187}, volume = {509}, year = {2011}, } @article{7313, abstract = {Li-ion batteries have transformed portable electronics and will play a key role in the electrification of transport. However, the highest energy storage possible for Li-ion batteries is insufficient for the long-term needs of society, for example, extended-range electric vehicles. To go beyond the horizon of Li-ion batteries is a formidable challenge; there are few options. Here we consider two: Li–air (O2) and Li–S. The energy that can be stored in Li–air (based on aqueous or non-aqueous electrolytes) and Li–S cells is compared with Li-ion; the operation of the cells is discussed, as are the significant hurdles that will have to be overcome if such batteries are to succeed. Fundamental scientific advances in understanding the reactions occurring in the cells as well as new materials are key to overcoming these obstacles. The potential benefits of Li–air and Li–S justify the continued research effort that will be needed.}, author = {Bruce, Peter G. and Freunberger, Stefan Alexander and Hardwick, Laurence J. and Tarascon, Jean-Marie}, issn = {1476-1122}, journal = {Nature Materials}, number = {1}, pages = {19--29}, publisher = {Springer Nature}, title = {{Li–O2 and Li–S batteries with high energy storage}}, doi = {10.1038/nmat3191}, volume = {11}, year = {2011}, }