@misc{5405, abstract = {The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running in time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Oualhadj, Youssouf}, issn = {2664-1690}, pages = {22}, publisher = {IST Austria}, title = {{Perfect-information stochastic mean-payoff parity games}}, doi = {10.15479/AT:IST-2013-128-v1-1}, year = {2013}, } @misc{5406, abstract = {We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Pavlogiannis, Andreas}, issn = {2664-1690}, pages = {11}, publisher = {IST Austria}, title = {{Distributed synthesis for LTL Fragments}}, doi = {10.15479/AT:IST-2013-130-v1-1}, year = {2013}, } @techreport{5407, abstract = {This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria.}, author = {Porsche, Jana}, publisher = {IST Austria}, title = {{Technical requirements and features}}, year = {2013}, } @misc{5408, abstract = {We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Nain, Sumit and Vardi, Moshe}, issn = {2664-1690}, pages = {17}, publisher = {IST Austria}, title = {{The complexity of partial-observation stochastic parity games with finite-memory strategies}}, doi = {10.15479/AT:IST-2013-141-v1-1}, year = {2013}, } @misc{5409, abstract = {The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Majumdar, Rupak}, issn = {2664-1690}, pages = {12}, publisher = {IST Austria}, title = {{Edit distance for timed automata}}, doi = {10.15479/AT:IST-2013-144-v1-1}, year = {2013}, } @misc{5410, abstract = {Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. Our approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. }, author = {Ahmed, Umair and Chatterjee, Krishnendu and Gulwani, Sumit}, issn = {2664-1690}, pages = {13}, publisher = {IST Austria}, title = {{Automatic generation of alternative starting positions for traditional board games}}, doi = {10.15479/AT:IST-2013-146-v1-1}, year = {2013}, } @inbook{5747, author = {Dragoi, Cezara and Gupta, Ashutosh and Henzinger, Thomas A}, booktitle = {Computer Aided Verification}, isbn = {9783642397981}, issn = {1611-3349}, location = {Saint Petersburg, Russia}, pages = {174--190}, publisher = {Springer Berlin Heidelberg}, title = {{Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates}}, doi = {10.1007/978-3-642-39799-8_11}, volume = {8044}, year = {2013}, } @inproceedings{590, abstract = {We present two methods of creating two orthogonally-polarized focal points at customizable relative locations. These schemes may be critical for enhancing entanglement sources and other applications.}, author = {Schmid, David and Huang, Ting-Yu and Dirks, Radhika and Onur Hosten and Kwiat, Paul G}, publisher = {OSA}, title = {{Polarization dependent focusing}}, doi = {10.1364/QIM.2013.W6.23}, year = {2013}, } @article{591, abstract = {We present two methods for the precise independent focusing of orthogonal linear polarizations of light at arbitrary relative locations. Our first scheme uses a displaced lens in a polarization Sagnac interferometer to provide adjustable longitudinal and lateral focal displacements via simple geometry; the second uses uniaxial crystals to achieve the same effect in a compact collinear setup. We develop the theoretical applications and limitations of our schemes, and provide experimental confirmation of our calculations.}, author = {Schmid, David and Huang, Ting-Yu and Hazrat, Shiraz and Dirks, Radhika and Onur Hosten and Quint, Stephan and Thian, Dickson and Kwiat, Paul G}, journal = {Optics Express}, number = {13}, pages = {15538 -- 15552}, publisher = {Optical Society of America}, title = {{Adjustable and robust methods for polarization-dependent focusing}}, doi = {10.1364/OE.21.015538}, volume = {21}, year = {2013}, } @article{5920, abstract = {We study chains of lattice ideals that are invariant under a symmetric group action. In our setting, the ambient rings for these ideals are polynomial rings which are increasing in (Krull) dimension. Thus, these chains will fail to stabilize in the traditional commutative algebra sense. However, we prove a theorem which says that “up to the action of the group”, these chains locally stabilize. We also give an algorithm, which we have implemented in software, for explicitly constructing these stabilization generators for a family of Laurent toric ideals involved in applications to algebraic statistics. We close with several open problems and conjectures arising from our theoretical and computational investigations.}, author = {Hillar, Christopher J. and Martin del Campo Sanchez, Abraham}, issn = {0747-7171}, journal = {Journal of Symbolic Computation}, pages = {314--334}, publisher = {Elsevier}, title = {{Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals}}, doi = {10.1016/j.jsc.2012.06.006}, volume = {50}, year = {2013}, } @article{595, author = {Bernecky, Carrie A and Cramer, Patrick}, journal = {EMBO Journal}, number = {6}, pages = {771 -- 772}, publisher = {Wiley-Blackwell}, title = {{Struggling to let go: A non-coding RNA directs its own extension and destruction}}, doi = {10.1038/emboj.2013.36}, volume = {32}, year = {2013}, } @article{6128, abstract = {Different interoceptive systems must be integrated to ensure that multiple homeostatic insults evoke appropriate behavioral and physiological responses. Little is known about how this is achieved. Using C. elegans, we dissect cross-modulation between systems that monitor temperature, O2 and CO2. CO2 is less aversive to animals acclimated to 15°C than those grown at 22°C. This difference requires the AFD neurons, which respond to both temperature and CO2 changes. CO2 evokes distinct AFD Ca2+ responses in animals acclimated at 15°C or 22°C. Mutants defective in synaptic transmission can reprogram AFD CO2 responses according to temperature experience, suggesting reprogramming occurs cell autonomously. AFD is exquisitely sensitive to CO2. Surprisingly, gradients of 0.01% CO2/second evoke very different Ca2+ responses from gradients of 0.04% CO2/second. Ambient O2 provides further contextual modulation of CO2 avoidance. At 21% O2 tonic signalling from the O2-sensing neuron URX inhibits CO2 avoidance. This inhibition can be graded according to O2 levels. In a natural wild isolate, a switch from 21% to 19% O2 is sufficient to convert CO2 from a neutral to an aversive cue. This sharp tuning is conferred partly by the neuroglobin GLB-5. The modulatory effects of O2 on CO2 avoidance involve the RIA interneurons, which are post-synaptic to URX and exhibit CO2-evoked Ca2+ responses. Ambient O2 and acclimation temperature act combinatorially to modulate CO2 responsiveness. Our work highlights the integrated architecture of homeostatic responses in C. elegans.}, author = {Kodama-Namba, Eiji and Fenk, Lorenz A. and Bretscher, Andrew J. and Gross, Einav and Busch, K. Emanuel and de Bono, Mario}, issn = {1553-7404}, journal = {PLoS Genetics}, number = {12}, publisher = {Public Library of Science (PLoS)}, title = {{Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans}}, doi = {10.1371/journal.pgen.1004011}, volume = {9}, year = {2013}, } @article{6130, abstract = {Cas9 is an RNA-guided double-stranded DNA nuclease that participates in clustered regularly interspaced short palindromic repeats (CRISPR)-mediated adaptive immunity in prokaryotes. CRISPR–Cas9 has recently been used to generate insertion and deletion mutations in Caenorhabditis elegans, but not to create tailored changes (knock-ins). We show that the CRISPR–CRISPR-associated (Cas) system can be adapted for efficient and precise editing of the C. elegans genome. The targeted double-strand breaks generated by CRISPR are substrates for transgene-instructed gene conversion. This allows customized changes in the C. elegans genome by homologous recombination: sequences contained in the repair template (the transgene) are copied by gene conversion into the genome. The possibility to edit the C. elegans genome at selected locations will facilitate the systematic study of gene function in this widely used model organism.}, author = {Chen, Changchun and Fenk, Lorenz A. and de Bono, Mario}, issn = {1362-4962}, journal = {Nucleic Acids Research}, number = {20}, publisher = {Oxford University Press}, title = {{Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination}}, doi = {10.1093/nar/gkt805}, volume = {41}, year = {2013}, } @inbook{6132, author = {de Bono, Mario and Schafer, W.R. and Gottschalk, A.}, booktitle = {Optogenetics}, editor = {Hegemann, Peter and Sigrist, Stephan}, isbn = {9783110270723; 9783110270716}, pages = {61--78}, publisher = {Walter de Gruyter}, title = {{Optogenetic actuation, inhibition, modulation and readout for neuronal networks generating behavior in the nematode Caenorhabditis elegans}}, year = {2013}, } @article{6133, abstract = {cGMP signaling is widespread in the nervous system. However, it has proved difficult to visualize and genetically probe endogenously evoked cGMP dynamics in neurons in vivo. Here, we combine cGMP and Ca2+ biosensors to image and dissect a cGMP signaling network in a Caenorhabditis elegans oxygen-sensing neuron. We show that a rise in O2 can evoke a tonic increase in cGMP that requires an atypical O2-binding soluble guanylate cyclase and that is sustained until oxygen levels fall. Increased cGMP leads to a sustained Ca2+ response in the neuron that depends on cGMP-gated ion channels. Elevated levels of cGMP and Ca2+ stimulate competing negative feedback loops that shape cGMP dynamics. Ca2+-dependent negative feedback loops, including activation of phosphodiesterase-1 (PDE-1), dampen the rise of cGMP. A different negative feedback loop, mediated by phosphodiesterase-2 (PDE-2) and stimulated by cGMP-dependent kinase (PKG), unexpectedly promotes cGMP accumulation following a rise in O2, apparently by keeping in check gating of cGMP channels and limiting activation of Ca2+-dependent negative feedback loops. Simultaneous imaging of Ca2+ and cGMP suggests that cGMP levels can rise close to cGMP channels while falling elsewhere. O2-evoked cGMP and Ca2+ responses are highly reproducible when the same neuron in an individual animal is stimulated repeatedly, suggesting that cGMP transduction has high intrinsic reliability. However, responses vary substantially across individuals, despite animals being genetically identical and similarly reared. This variability may reflect stochastic differences in expression of cGMP signaling components. Our work provides in vivo insights into the architecture of neuronal cGMP signaling.}, author = {Couto, A. and Oda, S. and Nikolaev, V. O. and Soltesz, Z. and de Bono, Mario}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {35}, pages = {E3301--E3310}, publisher = {Proceedings of the National Academy of Sciences}, title = {{In vivo genetic dissection of O2-evoked cGMP dynamics in a Caenorhabditis elegans gas sensor}}, doi = {10.1073/pnas.1217428110}, volume = {110}, year = {2013}, } @article{6135, abstract = {Many organisms have stress response pathways, components of which share homology with players in complex human disease pathways. Research on stress response in the nematode worm Caenorhabditis elegans has provided detailed insights into the genetic and molecular mechanisms underlying complex human diseases. In this review we focus on four different types of environmental stress responses – heat shock, oxidative stress, hypoxia, and osmotic stress – and on how these can be used to study the genetics of complex human diseases. All four types of responses involve the genetic machineries that underlie a number of complex human diseases such as cancer and neurodegenerative diseases, including Alzheimer's and Parkinson's. We highlight the types of stress response experiments required to detect the genes and pathways underlying human disease and suggest that studying stress biology in worms can be translated to understanding human disease and provide potential targets for drug discovery.}, author = {Rodriguez, Miriam and Snoek, L. Basten and de Bono, Mario and Kammenga, Jan E.}, issn = {0168-9525}, journal = {Trends in Genetics}, number = {6}, pages = {367--374}, publisher = {Elsevier}, title = {{Worms under stress: C. elegans stress response and its relevance to complex human disease and aging}}, doi = {10.1016/j.tig.2013.01.010}, volume = {29}, year = {2013}, } @article{6370, abstract = {The molecular and supramolecular origins of the superior nonlinear optical (NLO) properties observed in the organic phenolic triene material, OH1 (2-(3-(4-hydroxystyryl)-5,5-dimethylcyclohex-2-enylidene)malononitrile), are presented. The molecular charge-transfer distribution is topographically mapped, demonstrating that a uniformly delocalized passive electronic medium facilitates the charge-transfer between the phenolic electron donor and the cyano electron acceptors which lie at opposite ends of the molecule. Its ability to act as a “push–pull” π-conjugated molecule is quantified, relative to similar materials, by supporting empirical calculations; these include bond-length alternation and harmonic-oscillator stabilization energy (HOSE) tests. Such tests, together with frontier molecular orbital considerations, reveal that OH1 can exist readily in its aromatic (neutral) or quinoidal (charge-separated) state, thereby overcoming the “nonlinearity-thermal stability trade-off”. The HOSE calculation also reveals a correlation between the quinoidal resonance contribution to the overall structure of OH1 and the UV–vis absorption peak wavelength in the wider family of configurationally locked polyene framework materials. Solid-state tensorial coefficients of the molecular dipole, polarizability, and the first hyperpolarizability for OH1 are derived from the first-, second-, and third-order electronic moments of the experimental charge-density distribution. The overall solid-state molecular dipole moment is compared with those from gas-phase calculations, revealing that crystal field effects are very significant in OH1. The solid-state hyperpolarizability derived from this charge-density study affords good agreement with gas-phase calculations as well as optical measurements based on hyper-Rayleigh scattering (HRS) and electric-field-induced second harmonic (EFISH) generation. This lends support to the further use of charge-density studies to calculate solid-state hyperpolarizability coefficients in other organic NLO materials. Finally, this charge-density study is also employed to provide an advanced classification of hydrogen bonds in OH1, which requires more stringent criteria than those from conventional structure analysis. As a result, only the strongest OH···NC interaction is so classified as a true hydrogen bond. Indeed, it is this electrostatic interaction that influences the molecular charge transfer: the other four, weaker, nonbonded contacts nonetheless affect the crystal packing. Overall, the establishment of these structure–property relationships lays a blueprint for designing further, more NLO efficient, materials in this industrially leading organic family of compounds.}, author = {Lin, Tze-Chia and Cole, Jacqueline M. and Higginbotham, Andrew P and Edwards, Alison J. and Piltz, Ross O. and Pérez-Moreno, Javier and Seo, Ji-Youn and Lee, Seung-Chul and Clays, Koen and Kwon, O-Pil}, issn = {1932-7447}, journal = {The Journal of Physical Chemistry C}, number = {18}, pages = {9416--9430}, publisher = {American Chemical Society (ACS)}, title = {{Molecular origins of the high-performance nonlinear optical susceptibility in a phenolic polyene chromophore: Electron density distributions, hydrogen bonding, and ab initio calculations}}, doi = {10.1021/jp400648q}, volume = {117}, year = {2013}, } @misc{6440, abstract = {In order to guarantee that each method of a data structure updates the logical state exactly once, al-most all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contentionby increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leads to further degradation of performance.In this paper we formalize the notion of competitiveness of a synchronizing statement which can beused as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free.We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations.}, author = {Henzinger, Thomas A and Payer, Hannes and Sezgin, Ali}, issn = {2664-1690}, pages = {23}, publisher = {IST Austria}, title = {{Replacing competition with cooperation to achieve scalable lock-free FIFO queues }}, doi = {10.15479/AT:IST-2013-124-v1-1}, year = {2013}, } @article{1442, abstract = {We give a cohomological interpretation of both the Kac polynomial and the refined Donaldson-Thomas-invariants of quivers. This interpretation yields a proof of a conjecture of Kac from 1982 and gives a new perspective on recent work of Kontsevich-Soibelman. Thisis achieved by computing, via an arithmetic Fourier transform, the dimensions of the isotypical components of the cohomology of associated Nakajima quiver varieties under the action of a Weyl group. The generating function of the corresponding Poincare polynomials is an extension of Hua's formula for Kac polynomials of quivers involving Hall-Littlewood symmetric functions. The resulting formulae contain a wide range of information on the geometry of the quiver varieties.}, author = {Tamas Hausel and Letellier, Emmanuel and Rodríguez Villegas, Fernando}, journal = {Annals of Mathematics}, number = {3}, pages = {1147 -- 1168}, publisher = {Princeton University Press}, title = {{Positivity for Kac polynomials and DT-invariants of quivers}}, doi = {10.4007/annals.2013.177.3.8}, volume = {177}, year = {2013}, } @inbook{1443, abstract = {Here we survey several results and conjectures on the cohomology of the total space of the Hitchin system: the moduli space of semi-stable rank n and degree d Higgs bundles on a complex algebraic curve C. The picture emerging is a dynamic mixture of ideas originating in theoretical physics such as gauge theory and mirror symmetry, Weil conjectures in arithmetic algebraic geometry, representation theory of finite groups of Lie type and Langlands duality in number theory.}, author = {Tamas Hausel}, booktitle = {Handbook of Moduli: Volume II}, pages = {29 -- 70}, publisher = {International Press}, title = {{Global topology of the Hitchin system}}, volume = {25}, year = {2013}, }