@article{3115, abstract = {We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.}, author = {Berberich, Eric and Halperin, Dan and Kerber, Michael and Pogalnikova, Roza}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {964 -- 989}, publisher = {Springer}, title = {{Deconstructing approximate offsets}}, doi = {10.1007/s00454-012-9441-5}, volume = {48}, year = {2012}, } @article{3331, abstract = {Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.}, author = {Kerber, Michael and Sagraloff, Michael}, journal = { Journal of Symbolic Computation}, number = {3}, pages = {239 -- 258}, publisher = {Elsevier}, title = {{A worst case bound for topology computation of algebraic curves}}, doi = {10.1016/j.jsc.2011.11.001}, volume = {47}, year = {2012}, } @article{346, abstract = {Arrays of vertically aligned ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires (NWs) were prepared by means of the combination of two solution-growth processes. First, single-crystal ZnO NWs with controlled n-type doping were grown on conducting substrates by a low-cost, high-yield and seed-free electrochemical route. These NWs were covered by a titanium oxide shell of tunable thickness mediating successive adsorption-hydrolysis-condensation steps. Using this atomic-layer growth procedure, titania shells with controlled thickness and the anatase TiO2 phase were obtained after sintering at 450 °C. Higher sintering temperatures resulted in the formation of ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs by the interdiffusion of Zn and Ti ions at the ZnO–TiO2 interface. The performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell NWs towards photoelectrochemical (PEC) water splitting was investigated as a function of the titania shell thickness. Furthermore, the performance of such core–shell NWs as photoelectrodes in dye-sensitized solar cells was also characterized. The TiO2 presence at the ZnO : Cl surface promoted a two-fold increase on the produced photocurrent densities, probing their potential for PEC and optoelectronic applications. Electrochemical impedance spectroscopy was used to corroborate the lower resistance for charge transfer between the NWs and the electrolyte in the presence of the TiO2 shell.}, author = {Fan, Jiandong and Zamani, Reza and Fábrega, Cristina and Shavel, Alexey and Flox, Cristina and Ibáñez, Maria and Andreu, Teresa and López, Amtonio and Arbiol, Jordi and Morante, Joan and Cabot, Andreu}, journal = {Journal of Physics D: Applied Physics}, number = {41}, publisher = {IOP Publishing Ltd.}, title = {{Solution-growth and optoelectronic performance of ZnO : Cl/TiO2 and ZnO : Cl/ZnxTiOy/TiO2 core–shell nanowires with tunable shell thickness}}, doi = {10.1088/0022-3727/45/41/415301}, volume = {45}, year = {2012}, } @article{3168, abstract = {The induction of a signaling pathway is characterized by transient complex formation and mutual posttranslational modification of proteins. To faithfully capture this combinatorial process in a mathematical model is an important challenge in systems biology. Exploiting the limited context on which most binding and modification events are conditioned, attempts have been made to reduce the combinatorial complexity by quotienting the reachable set of molecular species into species aggregates while preserving the deterministic semantics of the thermodynamic limit. Recently, we proposed a quotienting that also preserves the stochastic semantics and that is complete in the sense that the semantics of individual species can be recovered from the aggregate semantics. In this paper, we prove that this quotienting yields a sufficient condition for weak lumpability (that is to say that the quotient system is still Markovian for a given set of initial distributions) and that it gives rise to a backward Markov bisimulation between the original and aggregated transition system (which means that the conditional probability of being in a given state in the original system knowing that we are in its equivalence class is an invariant of the system). We illustrate the framework on a case study of the epidermal growth factor (EGF)/insulin receptor crosstalk.}, author = {Feret, Jérôme and Henzinger, Thomas A and Koeppl, Heinz and Petrov, Tatjana}, journal = {Theoretical Computer Science}, pages = {137 -- 164}, publisher = {Elsevier}, title = {{Lumpability abstractions of rule based systems}}, doi = {10.1016/j.tcs.2011.12.059}, volume = {431}, year = {2012}, } @article{377, abstract = {The potential to control the composition and crystal phase at the nanometer scale enable the production of nanocrystalline materials with enhanced functionalities and new applications. In the present work, we detail a novel colloidal synthesis route to prepare nanoparticles of the ternary semiconductor Cu2GeSe3 (CGSe) with nanometer-scale control over their crystal phases. We also demonstrate the structural effect on the thermoelectric properties of bottom-up-prepared CGSe nanomaterials. By careful adjustment of the nucleation and growth temperatures, pure orthorhombic CGSe nanoparticles with cationic order or polytypic CGSe nanoparticles with disordered cation positions can be produced. In this second type of nanoparticle, a high density of twins can be created to periodically change the atomic plane stacking, forming a hexagonal wurtzite CGSe phase. The high yield of the synthetic routes reported here allows the production of single-phase and multiphase CGSe nanoparticles in the gram scale, which permits characterization of the thermoelectric properties of these materials. Reduced thermal conductivities and a related 2.5-fold increase of the thermoelectric figure of merit for multiphase nanomaterials compared to pure-phase CGSe are systematically obtained. These results are discussed in terms of the density and efficiency of phonon scattering centers in both types of materials.}, author = {Ibáñez, Maria and Zamani, Reza and Li, Wenhua and Cadavid, Doris and Gorse, Stéphane and Katchoi, Nebll and Shavel, Alexey and López, Antonioo and Morante, Joan and Arbiol, Jordi and Cabot, Andreu}, journal = {Chemistry of Materials}, number = {23}, pages = {4615 -- 4622}, publisher = {American Chemical Society}, title = {{Crystallographic control at the nanoscale to enhance functionality: Polytypic Cu2GeSe3 nanoparticles as thermoelectric materials}}, doi = {10.1021/cm303252q}, volume = {24}, year = {2012}, } @article{3846, abstract = {We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A}, journal = {Journal of Computer and System Sciences}, number = {2}, pages = {394 -- 413}, publisher = {Elsevier}, title = {{A survey of stochastic ω regular games}}, doi = {10.1016/j.jcss.2011.05.002}, volume = {78}, year = {2012}, } @article{387, abstract = {In this Letter we present detailed study of the density of states near defects in Bi 2Se 3. In particular, we present data on the commonly found triangular defects in this system. While we do not find any measurable quasiparticle scattering interference effects, we do find localized resonances, which can be well fitted by theory once the potential is taken to be extended to properly account for the observed defects. The data together with the fits confirm that while the local density of states around the Dirac point of the electronic spectrum at the surface is significantly disrupted near the impurity by the creation of low-energy resonance state, the Dirac point is not locally destroyed. We discuss our results in terms of the expected protected surface state of topological insulators. © 2012 American Physical Society.}, author = {Alpichshev, Zhanybek and Biswas, Rudro and Balatsky, Alexander and Analytis, James and Chu, Jiunhaw and Fisher, Ian and Kapitulnik, Aharon}, journal = {Physical Review Letters}, number = {20}, publisher = {American Physical Society}, title = {{STM imaging of impurity resonances on Bi 2Se 3}}, doi = {10.1103/PhysRevLett.108.206402}, volume = {108}, year = {2012}, } @article{3110, abstract = {The directional transport of the phytohormone auxin depends on the phosphorylation status and polar localization of PIN-FORMED (PIN) auxin efflux proteins. While PINIOD (PID) kinase is directly involved in the phosphorylation of PIN proteins, the phosphatase holoenzyme complexes that dephosphorylate PIN proteins remain elusive. Here, we demonstrate that mutations simultaneously disrupting the function of Arabidopsis thaliana FyPP1 (for Phytochrome-associated serine/threonine protein phosphatase1) and FyPP3, two homologous genes encoding the catalytic subunits of protein phosphatase6 (PP6), cause elevated accumulation of phosphorylated PIN proteins, correlating with a basal-to-apical shift in subcellular PIN localization. The changes in PIN polarity result in increased root basipetal auxin transport and severe defects, including shorter roots, fewer lateral roots, defective columella cells, root meristem collapse, abnormal cotyledons (small, cup-shaped, or fused cotyledons), and altered leaf venation. Our molecular, biochemical, and genetic data support the notion that FyPP1/3, SAL (for SAPS DOMAIN-LIKE), and PP2AA proteins (RCN1 [for ROOTS CURL IN NAPHTHYLPHTHALAMIC ACID1] or PP2AA1, PP2AA2, and PP2AA3) physically interact to form a novel PP6-type heterotrimeric holoenzyme complex. We also show that FyPP1/3, SAL, and PP2AA interact with a subset of PIN proteins and that for SAL the strength of the interaction depends on the PIN phosphorylation status. Thus, an Arabidopsis PP6-type phosphatase holoenzyme acts antagonistically with PID to direct auxin transport polarity and plant development by directly regulating PIN phosphorylation. }, author = {Dai, Mingqiu and Zhang, Chen and Urszula Kania and Chen, Fang and Xue, Qin and McCray, Tyra and Li, Gang and Qin, Genji and Wakeley, Michelle and Terzaghi, William and Wan, Jianmin and Zhao, Yunde and Xu, Jian and Jirí Friml and Deng, Xing W and Wang, Haiyang}, journal = {Plant Cell}, number = {6}, pages = {2497 -- 2514}, publisher = {American Society of Plant Biologists}, title = {{A PP6 type phosphatase holoenzyme directly regulates PIN phosphorylation and auxin efflux in Arabidopsis}}, doi = {10.1105/tpc.112.098905}, volume = {24}, year = {2012}, } @article{3113, abstract = {A cell membrane can be considered a liquid-phase plane in which lipids and proteins theoretically are free to diffuse. Numerous reports,however, describe retarded diffusion ofmembrane proteins in animal cells. This anomalous diffusion results from a combination of structuring factors including protein-protein interactions, cytoskeleton corralling, and lipid organization into microdomains. In plant cells, plasma-membrane (PM) proteins have been described as relatively immobile, but the control mechanisms that structure the PM have not been studied. Here, we use fluorescence recovery after photobleaching to estimate mobility of a set of minimal PM proteins. These proteins consist only of a PM-anchoring domain fused to a fluorescent protein, but their mobilities remained limited, as is the case for many full-length proteins. Neither the cytoskeleton nor membrane microdomain structure was involved in constraining the diffusion of these proteins. The cell wall, however, was shown to have a crucial role in immobilizing PM proteins. In addition, by single-molecule fluorescence imaging we confirmed that the pattern of cellulose deposition in the cell wall affects the trajectory and speed ofPMprotein diffusion. Regulation ofPMprotein dynamics by the plant cell wall can be interpreted as a mechanism for regulating protein interactions in processes such as trafficking and signal transduction.}, author = {Martinière, Alexandre and Lavagi, Irene and Nageswaran, Gayathri and Rolfe, Daniel J and Maneta-Peyret, Lilly and Luu, Doan-Trung and Botchway, Stanley W and Webb, Stephen E and Mongrand, Sebastien and Maurel, Christophe and Martin-Fernandez, Marisa L and Kleine-Vehn, Jürgen and Jirí Friml and Moreau, Patrick and Runions, John}, journal = {PNAS}, number = {31}, pages = {12805 -- 12810}, publisher = {National Academy of Sciences}, title = {{Cell wall constrains lateral diffusion of plant plasma membrane proteins}}, doi = {10.1073/pnas.1202040109}, volume = {109}, year = {2012}, } @article{3114, abstract = {Auxin is a key coordinative signal required for many aspects of plant development and its levels are controlled by auxin metabolism and intercellular auxin transport. Here we find that a member of PIN auxin transporter family, PIN8 is expressed in male gametophyte of Arabidopsis thaliana and has a crucial role in pollen development and functionality. Ectopic expression in sporophytic tissues establishes a role of PIN8 in regulating auxin homoeostasis and metabolism. PIN8 co-localizes with PIN5 to the endoplasmic reticulum (ER) where it acts as an auxin transporter. Genetic analyses reveal an antagonistic action of PIN5 and PIN8 in the regulation of intracellular auxin homoeostasis and gametophyte as well as sporophyte development. Our results reveal a role of the auxin transport in male gametophyte development in which the distinct actions of ER-localized PIN transporters regulate cellular auxin homoeostasis and maintain the auxin levels optimal for pollen development and pollen tube growth.}, author = {Ding, Zhaojun and Wang, Bangjun and Moreno, Ignacio and Dupláková, Nikoleta and Sibu Simon and Carraro, Nicola and Reemmer, Jesica and Pěnčík, Aleš and Xu Chen and Tejos, Ricardo I and Skůpa, Petr and Pollmann, Stephan and Mravec, Jozef and Petrášek, Jan and Zažímalová, Eva and Honys, David and Rolčík, Jakub and Murphy, Angus S and Orellana, Ariel and Geisler, Markus and Jirí Friml}, journal = {Nature Communications}, number = {AN 941}, publisher = {Nature Publishing Group}, title = {{ER-localized auxin transporter PIN8 regulates auxin homeostasis and male gametophyte development in Arabidopsis}}, doi = {10.1038/ncomms1941}, volume = {3}, year = {2012}, } @article{3111, abstract = {PIN-FORMED (PIN) protein-mediated auxin polar transport is critically important for development, pattern formation, and morphogenesis in plants. Auxin has been implicated in the regulation of polar auxin transport by inhibiting PIN endocytosis [1, 2], but how auxin regulates this process is poorly understood. Our genetic screen identified the Arabidopsis SPIKE1 (SPK1) gene whose loss-of-function mutations increased lateral root density and retarded gravitropic responses, as do pin2 knockout mutations [3]. SPK1 belongs to the conserved DHR2-Dock family of Rho guanine nucleotide exchange factors [4-6]. The spk1 mutations induced PIN2 internalization that was not suppressed by auxin, as did the loss-of-function mutations for Rho-like GTPase from Plants 6 (ROP6)-GTPase or its effector RIC1. Furthermore, SPK1 was required for auxin induction of ROP6 activation. Our results have established a Rho GTPase-based auxin signaling pathway that maintains PIN2 polar distribution to the plasma membrane via inhibition of its internalization in Arabidopsis roots. Our findings provide new insights into signaling mechanisms that underlie the regulation of the dynamic trafficking of PINs required for long-distance auxin transport and that link auxin signaling to PIN-mediated pattern formation and morphogenesis.}, author = {Lin, Deshu and Nagawa, Shingo and Chen, Jisheng and Cao, Lingyan and Xu Chen and Xu, Tongda and Hongjiang Li and Dhonukshe, Pankaj and Yamamuro, Chizuko and Jirí Friml and Scheres, Ben and Fu, Ying and Yang, Zhenbiao}, journal = {Current Biology}, number = {14}, pages = {1319 -- 1325}, publisher = {Cell Press}, title = {{A ROP GTPase dependent auxin signaling pathway regulates the subcellular distribution of PIN2 in Arabidopsis roots}}, doi = {10.1016/j.cub.2012.05.019}, volume = {22}, year = {2012}, } @article{3112, abstract = {The dynamic spatial and temporal distribution of the crucial plant signaling molecule auxin is achieved by feedback coordination of auxin signaling and intercellular auxin transport pathways [1, 2]. Developmental roles of auxin have been attributed predominantly to its effect on transcription; however, an alternative pathway involving AUXIN BINDING PROTEIN1 (ABP1) has been proposed to regulate clathrin-mediated endocytosis in roots and Rho-like GTPase (ROP)-dependent pavement cell interdigitation in leaves [3, 4]. In this study, we show that ROP6 and its downstream effector RIC1 regulate clathrin association with the plasma membrane for clathrin-mediated endocytosis, as well as for its feedback regulation by auxin. Genetic analysis revealed that ROP6/RIC1 acts downstream of ABP1 to regulate endocytosis. This signaling circuit is also involved in the feedback regulation of PIN-FORMED 1 (PIN1) and PIN2 auxin transporters activity (via its constitutive endocytosis) and corresponding auxin transport-mediated processes, including root gravitropism and leave vascular tissue patterning. Our findings suggest that the signaling module auxin-ABP1-ROP6/RIC1-clathrin-PIN1/PIN2 is a shared component of the feedback regulation of auxin transport during both root and aerial development.}, author = {Xu Chen and Naramoto, Satoshi and Robert, Stéphanie and Tejos, Ricardo and Löfke, Christian and Lin, Deshu and Yang, Zhenbiao and Jirí Friml}, journal = {Current Biology}, number = {14}, pages = {1326 -- 1332}, publisher = {Cell Press}, title = {{ABP1 and ROP6 GTPase signaling regulate clathrin mediated endocytosis in Arabidopsis roots}}, doi = {10.1016/j.cub.2012.05.020}, volume = {22}, year = {2012}, } @article{3128, abstract = {We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational). }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, journal = {Formal Methods in System Design}, number = {2}, pages = {268 -- 284}, publisher = {Springer}, title = {{A survey of partial-observation stochastic parity games}}, doi = {10.1007/s10703-012-0164-2}, volume = {43}, year = {2012}, } @inproceedings{3125, abstract = {We propose a new learning method to infer a mid-level feature representation that combines the advantage of semantic attribute representations with the higher expressive power of non-semantic features. The idea lies in augmenting an existing attribute-based representation with additional dimensions for which an autoencoder model is coupled with a large-margin principle. This construction allows a smooth transition between the zero-shot regime with no training example, the unsupervised regime with training examples but without class labels, and the supervised regime with training examples and with class labels. The resulting optimization problem can be solved efficiently, because several of the necessity steps have closed-form solutions. Through extensive experiments we show that the augmented representation achieves better results in terms of object categorization accuracy than the semantic representation alone.}, author = {Sharmanska, Viktoriia and Quadrianto, Novi and Lampert, Christoph}, location = {Florence, Italy}, number = {PART 5}, pages = {242 -- 255}, publisher = {Springer}, title = {{Augmented attribute representations}}, doi = {10.1007/978-3-642-33715-4_18}, volume = {7576}, year = {2012}, } @inproceedings{3129, abstract = {Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω  + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations. }, author = {Busaryev, Oleksiy and Cabello, Sergio and Chen, Chao and Dey, Tamal and Wang, Yusu}, location = {Helsinki, Finland}, pages = {189 -- 200}, publisher = {Springer}, title = {{Annotating simplices with a homology basis and its applications}}, doi = {10.1007/978-3-642-31155-0_17}, volume = {7357}, year = {2012}, } @inproceedings{3126, abstract = {In this work we propose a new information-theoretic clustering algorithm that infers cluster memberships by direct optimization of a non-parametric mutual information estimate between data distribution and cluster assignment. Although the optimization objective has a solid theoretical foundation it is hard to optimize. We propose an approximate optimization formulation that leads to an efficient algorithm with low runtime complexity. The algorithm has a single free parameter, the number of clusters to find. We demonstrate superior performance on several synthetic and real datasets. }, author = {Müller, Andreas and Nowozin, Sebastian and Lampert, Christoph}, location = {Graz, Austria}, pages = {205 -- 215}, publisher = {Springer}, title = {{Information theoretic clustering using minimal spanning trees}}, doi = {10.1007/978-3-642-32717-9_21}, volume = {7476}, year = {2012}, } @inproceedings{3155, abstract = {We propose synchronous interfaces, a new interface theory for discrete-time systems. We use an application to time-triggered scheduling to drive the design choices for our formalism; in particular, additionally to deriving useful mathematical properties, we focus on providing a syntax which is adapted to natural high-level system modeling. As a result, we develop an interface model that relies on a guarded-command based language and is equipped with shared variables and explicit discrete-time clocks. We define all standard interface operations: compatibility checking, composition, refinement, and shared refinement. Apart from the synchronous interface model, the contribution of this paper is the establishment of a formal relation between interface theories and real-time scheduling, where we demonstrate a fully automatic framework for the incremental computation of time-triggered schedules.}, author = {Delahaye, Benoît and Fahrenberg, Uli and Henzinger, Thomas A and Legay, Axel and Nickovic, Dejan}, location = {Stockholm, Sweden}, pages = {203 -- 218}, publisher = {Springer}, title = {{Synchronous interface theories and time triggered scheduling}}, doi = {10.1007/978-3-642-30793-5_13}, volume = {7273}, year = {2012}, } @article{3159, abstract = {The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.}, author = {Mileyko, Yuriy and Edelsbrunner, Herbert and Price, Charles and Weitz, Joshua}, journal = {PLoS One}, number = {6}, publisher = {Public Library of Science}, title = {{Hierarchical ordering of reticular networks}}, doi = {10.1371/journal.pone.0036715}, volume = {7}, year = {2012}, } @article{3156, abstract = {Dispersal is crucial for gene flow and often determines the long-term stability of meta-populations, particularly in rare species with specialized life cycles. Such species are often foci of conservation efforts because they suffer disproportionally from degradation and fragmentation of their habitat. However, detailed knowledge of effective gene flow through dispersal is often missing, so that conservation strategies have to be based on mark-recapture observations that are suspected to be poor predictors of long-distance dispersal. These constraints have been especially severe in the study of butterfly populations, where microsatellite markers have been difficult to develop. We used eight microsatellite markers to analyse genetic population structure of the Large Blue butterfly Maculinea arion in Sweden. During recent decades, this species has become an icon of insect conservation after massive decline throughout Europe and extinction in Britain followed by reintroduction of a seed population from the Swedish island of Öland. We find that populations are highly structured genetically, but that gene flow occurs over distances 15 times longer than the maximum distance recorded from mark-recapture studies, which can only be explained by maximum dispersal distances at least twice as large as previously accepted. However, we also find evidence that gaps between sites with suitable habitat exceeding ∼ 20 km induce genetic erosion that can be detected from bottleneck analyses. Although further work is needed, our results suggest that M. arion can maintain fully functional metapopulations when they consist of optimal habitat patches that are no further apart than ∼10 km.}, author = {Ugelvig, Line V and Andersen, Anne and Boomsma, Jacobus and Nash, David}, journal = {Molecular Ecology}, number = {13}, pages = {3224 -- 3236}, publisher = {Wiley-Blackwell}, title = {{Dispersal and gene flow in the rare parasitic Large Blue butterfly Maculinea arion}}, doi = {10.1111/j.1365-294X.2012.05592.x}, volume = {21}, year = {2012}, } @article{3158, abstract = {We describe here the development and characterization of a conditionally inducible mouse model expressing Lifeact-GFP, a peptide that reports the dynamics of filamentous actin. We have used this model to study platelets, megakaryocytes and melanoblasts and we provide evidence that Lifeact-GFP is a useful reporter in these cell types ex vivo. In the case of platelets and megakaryocytes, these cells are not transfectable by traditional methods, so conditional activation of Lifeact allows the study of actin dynamics in these cells live. We studied melanoblasts in native skin explants from embryos, allowing the visualization of live actin dynamics during cytokinesis and migration. Our study revealed that melanoblasts lacking the small GTPase Rac1 show a delay in the formation of new pseudopodia following cytokinesis that accounts for the previously reported cytokinesis delay in these cells. Thus, through use of this mouse model, we were able to gain insights into the actin dynamics of cells that could only previously be studied using fixed specimens or following isolation from their native tissue environment.}, author = {Schachtner, Hannah and Li, Ang and Stevenson, David and Calaminus, Simon and Thomas, Steven and Watson, Steve and Sixt, Michael K and Wedlich Söldner, Roland and Strathdee, Douglas and Machesky, Laura}, journal = {European Journal of Cell Biology}, number = {11-12}, pages = {923 -- 929}, publisher = {Elsevier}, title = {{Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo}}, doi = {10.1016/j.ejcb.2012.04.002}, volume = {91}, year = {2012}, } @article{3248, abstract = {We describe RTblob, a high speed vision system that detects objects in cluttered scenes based on their color and shape at a speed of over 800 frames/s. Because the system is available as open-source software and relies only on off-the-shelf PC hardware components, it can provide the basis for multiple application scenarios. As an illustrative example, we show how RTblob can be used in a robotic table tennis scenario to estimate ball trajectories through 3D space simultaneously from four cameras images at a speed of 200 Hz.}, author = {Lampert, Christoph and Peters, Jan}, issn = {1861-8219}, journal = {Journal of Real-Time Image Processing}, number = {1}, pages = {31 -- 41}, publisher = {Springer}, title = {{Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components}}, doi = {10.1007/s11554-010-0168-3}, volume = {7}, year = {2012}, } @article{3247, abstract = {The Brazilian Merganser is a very rare and threatened species that nowadays inhabits only a few protected areas and their surroundings in the Brazilian territory. In order to estimate the remaining genetic diversity and population structure in this species, two mitochondrial genes were sequenced in 39 individuals belonging to two populations and in one individual collected in Argentina in 1950. We found a highly significant divergence between two major remaining populations of Mergus octosetaceus, which suggests a historical population structure in this species. Furthermore, two deeply divergent lineages were found in a single location, which could due to current or historical secondary contact. Based on the available genetic data, we point out future directions which would contribute to design strategies for conservation and management of this threatened species.}, author = {Vilaça, Sibelle and Fernandes Redondo, Rodrigo A and Lins, Lívia and Santos, Fabrício}, journal = {Conservation Genetics}, number = {1}, pages = {293 -- 298}, publisher = {Springer}, title = {{Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)}}, doi = {10.1007/s10592-011-0262-5}, volume = {13}, year = {2012}, } @article{3245, abstract = {How cells orchestrate their behavior during collective migration is a long-standing question. Using magnetic tweezers to apply mechanical stimuli to Xenopus mesendoderm cells, Weber etal. (2012) now reveal, in this issue of Developmental Cell, a cadherin-mediated mechanosensitive response that promotes cell polarization and movement persistence during the collective mesendoderm migration in gastrulation.}, author = {Behrndt, Martin and Heisenberg, Carl-Philipp J}, journal = {Developmental Cell}, number = {1}, pages = {3 -- 4}, publisher = {Cell Press}, title = {{Spurred by resistance mechanosensation in collective migration}}, doi = {10.1016/j.devcel.2011.12.018}, volume = {22}, year = {2012}, } @article{3262, abstract = {Living cells must control the reading out or "expression" of information encoded in their genomes, and this regulation often is mediated by transcription factors--proteins that bind to DNA and either enhance or repress the expression of nearby genes. But the expression of transcription factor proteins is itself regulated, and many transcription factors regulate their own expression in addition to responding to other input signals. Here we analyze the simplest of such self-regulatory circuits, asking how parameters can be chosen to optimize information transmission from inputs to outputs in the steady state. Some nonzero level of self-regulation is almost always optimal, with self-activation dominant when transcription factor concentrations are low and self-repression dominant when concentrations are high. In steady state the optimal self-activation is never strong enough to induce bistability, although there is a limit in which the optimal parameters are very close to the critical point.}, author = {Tkacik, Gasper and Walczak, Aleksandra and Bialek, William}, journal = { Physical Review E statistical nonlinear and soft matter physics }, number = {4}, publisher = {American Institute of Physics}, title = {{Optimizing information flow in small genetic networks. III. A self-interacting gene}}, doi = {10.1103/PhysRevE.85.041903}, volume = {85}, year = {2012}, } @article{3257, abstract = {Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.}, author = {Kolmogorov, Vladimir}, journal = {Discrete Applied Mathematics}, number = {4-5}, pages = {416 -- 426}, publisher = {Elsevier}, title = {{Generalized roof duality and bisubmodular functions}}, doi = {10.1016/j.dam.2011.10.026}, volume = {160}, year = {2012}, } @inbook{3277, abstract = {The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.}, author = {de Vladar, Harold and Chela Flores, Julian}, booktitle = {Life on Earth and other planetary bodies}, pages = {387 -- 405}, publisher = {Springer}, title = {{Can the evolution of multicellularity be anticipated in the exploration of the solar system?}}, doi = {10.1007/978-94-007-4966-5_22}, volume = {24}, year = {2012}, } @inproceedings{3279, abstract = {We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions. }, author = {Jain, Abhishek and Pietrzak, Krzysztof Z and Tentes, Aris}, location = {Taormina, Sicily, Italy}, pages = {369 -- 382}, publisher = {Springer}, title = {{Hardness preserving constructions of pseudorandom functions}}, doi = {10.1007/978-3-642-28914-9_21}, volume = {7194}, year = {2012}, } @article{3274, abstract = {A boundary element model of a tunnel running through horizontally layered soil with anisotropic material properties is presented. Since there is no analytical fundamental solution for wave propagation inside a layered orthotropic medium in 3D, the fundamental displacements and stresses have to be calculated numerically. In our model this is done in the Fourier domain with respect to space and time. The assumption of a straight tunnel with infinite extension in the x direction makes it possible to decouple the system for every wave number kx, leading to a 2.5D-problem, which is suited for parallel computation. The special form of the fundamental solution, resulting from our Fourier ansatz, and the fact, that the calculation of the boundary integral equation is performed in the Fourier domain, enhances the stability and efficiency of the numerical calculations.}, author = {Rieckh, Georg and Kreuzer, Wolfgang and Waubke, Holger and Balazs, Peter}, journal = { Engineering Analysis with Boundary Elements}, number = {6}, pages = {960 -- 967}, publisher = {Elsevier}, title = {{A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil}}, doi = {10.1016/j.enganabound.2011.12.014}, volume = {36}, year = {2012}, } @article{3289, abstract = {Viral manipulation of transduction pathways associated with key cellular functions such as survival, response to microbial infection, and cytoskeleton reorganization can provide the supportive milieu for a productive infection. Here, we demonstrate that vaccinia virus (VACV) infection leads to activation of the stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK) 4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the stimulation of this pathway requires postpenetration, prereplicative events in the viral replication cycle. Although the formation of intracellular mature virus (IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an accentuated deregulation of microtubule and actin network organization in infected JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery and enhanced enveloped particle release. Furthermore, VACV infection induced alterations in the cell contractility and morphology, and cell migration was reduced in the JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell contractility and cell migration, such as microtubule-associated protein 1B and paxillin, respectively, was not detected in the VACV-infected KO cells. In sum, our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in cytoskeleton reorganization during VACV infection. }, author = {Pereira, Anna and Leite, Flávia and Brasil, Bruno and Soares Martins, Jamaria and Torres, Alice and Pimenta, Paulo and Souto Padrón, Thais and Tranktman, Paula and Ferreira, Paulo and Kroon, Erna and Bonjardim, Cláudio}, journal = {Journal of Virology}, number = {1}, pages = {172 -- 184}, publisher = {ASM}, title = {{A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization}}, doi = {10.1128/JVI.05638-11}, volume = {86}, year = {2012}, } @article{3310, abstract = {The theory of persistent homology opens up the possibility to reason about topological features of a space or a function quantitatively and in combinatorial terms. We refer to this new angle at a classical subject within algebraic topology as a point calculus, which we present for the family of interlevel sets of a real-valued function. Our account of the subject is expository, devoid of proofs, and written for non-experts in algebraic topology.}, author = {Bendich, Paul and Cabello, Sergio and Edelsbrunner, Herbert}, journal = {Pattern Recognition Letters}, number = {11}, pages = {1436 -- 1444}, publisher = {Elsevier}, title = {{A point calculus for interlevel set homology}}, doi = {10.1016/j.patrec.2011.10.007}, volume = {33}, year = {2012}, } @article{338, abstract = {The ample chemical and structural freedom of quaternary compounds permits engineering materials that fulfill the requirements of a wide variety of applications. In this work, the mechanisms to achieve unprecedented size, shape, and composition control in quaternary nanocrystals are detailed. The described procedure allows obtaining tetrahedral and penta-tetrahedral quaternary nanocrystals with tuned size distributions and controlled compositions from a plethora of I 2-II-IV-VI 4 semiconductors.}, author = {Ibáñez, Maria and Zamani, Reza and Li, Wenhua and Shavel, Alexey and Arbiol, Jordi and Morante, Joan and Cabot, Andreu}, journal = {Crystal Growth and Design }, number = {3}, pages = {1085 -- 1090}, publisher = {American Chemical Society (ACS)}, title = {{Extending the nanocrystal synthesis control to quaternary compositions}}, doi = {10.1021/cg201709c}, volume = {12}, year = {2012}, } @article{339, abstract = {A high-yield and upscalable colloidal synthesis route for the production of quaternary I 2-II-IV-VI 4 nanocrystals, particularly stannite Cu 2+xCd 1-xSnSe 4, with narrow size distribution and precisely controlled composition is presented. It is also shown here how the diversity of valences in the constituent elements allows an effective control of their electrical conductivity through the adjustment of the cation ratios. At the same time, while the crystallographic complexity of quaternary chalcogenides is associated with intrinsically low thermal conductivities, the reduction of the lattice dimensions to the nanoscale further reduces the materials thermal conductivity. In the specific case of the stannite crystal structure, a convenient slab distribution of the valence band maximum states permits a partial decoupling of the p-type electrical conductivity from both the Seebeck coefficient and the thermal conductivity. Combining these features, we demonstrate how an initial optimization of the nanocrystals Cd/Cu ratio allowed us to obtain low-temperature solution-processed materials with ZT values up to 0.71 at 685 K.}, author = {Ibáñez, Maria and Cadavid, Doris and Zamani, Reza and García Castelló, Nuria and Izquierdo Roca, Victora and Li, Wenhua and Fairbrother, Andrew and Prades, Joan and Shavel, Alexey and Arbiol, Jordi and Pérez Rodríguez, Alejandro and Morante, Joan and Cabot, Andreu}, journal = {Chemistry of Materials}, number = {3}, pages = {562 -- 570}, publisher = {American Chemical Society}, title = {{Composition control and thermoelectric properties of quaternary chalcogenide nanocrystals: The case of stannite Cu2CdSnSe4}}, doi = {10.1021/cm2031812}, volume = {24}, year = {2012}, } @article{340, abstract = {A procedure for the continuous production of Cu 2ZnSnS 4 (CZTS) nanoparticles with controlled composition is presented. CZTS nanoparticles were prepared through the reaction of the metals' amino complexes with elemental sulfur in a continuous-flow reactor at moderate temperatures (300-330 °C). High-resolution transmission electron microscopy and X-ray diffraction analysis showed the nanocrystals to have a crystallographic structure compatible with that of the kesterite. Chemical characterization of the materials showed the presence of the four elements in each individual nanocrystal. Composition control was achieved by adjusting the solution flow rate through the reactor and the proper choice of the nominal precursor concentration within the flowing solution. Single-particle analysis revealed a composition distribution within each sample, which was optimized at the highest synthesis temperatures used. }, author = {Shavel, Alexey and Cadavid, Doris and Ibáñez, Maria and Carrete, Alex and Cabot, Andreu}, journal = {Journal of the American Chemical Society}, number = {3}, pages = {1438 -- 1441}, publisher = {ACS}, title = {{Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor}}, doi = {10.1021/ja209688a}, volume = {134}, year = {2012}, } @article{345, abstract = {Nanocomposites are highly promising materials to enhance the efficiency of current thermoelectric devices. A straightforward and at the same time highly versatile and controllable approach to produce nanocomposites is the assembly of solution-processed nanocrystal building blocks. The convenience of this bottom-up approach to produce nanocomposites with homogeneous phase distributions and adjustable composition is demonstrated here by blending Ag2Te and PbTe colloidal nanocrystals to form Ag2Te–PbTe bulk nanocomposites. The thermoelectric properties of these nanocomposites are analyzed in the temperature range from 300 to 700 K. The evolution of their electrical conductivity and Seebeck coefficient is discussed in terms of the blend composition and the characteristics of the constituent materials. }, author = {Cadavid, Doris and Ibáñez, Maria and Gorsse, Stéphane and López, Antonio and Cirera, Albert and Morante, Joan and Cabot, Andreu}, journal = {Journal of Nanoparticle Research}, number = {12}, publisher = {Kluwer}, title = {{Bottom-up processing of thermoelectric nanocomposites from colloidal nanocrystal building blocks: The case of Ag2Te–PbTe}}, doi = {10.1007/s11051-012-1328-0}, volume = {14}, year = {2012}, } @article{347, abstract = {A synthetic route for producing Cu 2ZnGeSe 4 nanocrystals with narrow size distributions and controlled composition is presented. These nanocrystals were used to produce densely packed nanomaterials by hot-pressing. From the characterization of the thermoelectric properties of these nanomaterials, Cu 2ZnGeSe 4 is demonstrated to show excellent thermoelectric properties. A very preliminary adjustment of the nanocrystal composition has already resulted in a figure of merit of up to 0.55 at 450°C. }, author = {Ibáñez, Maria and Zamani, Reza and Lalonde, Aaron and Cadavid, Doris and Li, Wenhua and Shavel, Alexey and Arbiol, Jordi and Morante, Joan and Gorsse, Stéphane and Snyder, G Jeffrey and Cabot, Andreu}, journal = {Journal of the American Chemical Society}, number = {9}, pages = {4060 -- 4063}, publisher = {ACS}, title = {{Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric properties}}, doi = {10.1021/ja211952z}, volume = {134}, year = {2012}, } @article{3836, abstract = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.}, author = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto}, journal = {Science of Computer Programming}, number = {2}, pages = {96 -- 112}, publisher = {Elsevier}, title = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}}, doi = {10.1016/j.scico.2010.06.004}, volume = {77}, year = {2012}, } @article{2972, abstract = {Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objectives. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is logspace-equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, journal = {Theoretical Computer Science}, pages = {49 -- 60}, publisher = {Elsevier}, title = {{Energy parity games}}, doi = {10.1016/j.tcs.2012.07.038}, volume = {458}, year = {2012}, } @article{2967, abstract = {For programs whose data variables range over Boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this article, we consider algorithmic verification of programs that use Boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over an unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) PSPACE-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly nested loops. The second result establishes connections to automata and logics defining languages over data words.}, author = {Alur, Rajeev and Cerny, Pavol and Weinstein, Scott}, journal = {ACM Transactions on Computational Logic (TOCL)}, number = {3}, publisher = {ACM}, title = {{Algorithmic analysis of array-accessing programs}}, doi = {10.1145/2287718.2287727}, volume = {13}, year = {2012}, } @article{492, abstract = {Background: Characterizing root system architecture (RSA) is essential to understanding the development and function of vascular plants. Identifying RSA-associated genes also represents an underexplored opportunity for crop improvement. Software tools are needed to accelerate the pace at which quantitative traits of RSA are estimated from images of root networks.Results: We have developed GiA Roots (General Image Analysis of Roots), a semi-automated software tool designed specifically for the high-throughput analysis of root system images. GiA Roots includes user-assisted algorithms to distinguish root from background and a fully automated pipeline that extracts dozens of root system phenotypes. Quantitative information on each phenotype, along with intermediate steps for full reproducibility, is returned to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line interface for interweaving the software into large-scale workflows. GiA Roots can also be extended to estimate novel phenotypes specified by the end-user.Conclusions: We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing 12 genotypes from the species Oryza sativa. We validate trait measurements against prior analyses of this image set that demonstrated that RSA traits are likely heritable and associated with genotypic differences. Moreover, we demonstrate that GiA Roots is extensible and an end-user can add functionality so that GiA Roots can estimate novel RSA traits. In summary, we show that the software can function as an efficient tool as part of a workflow to move from large numbers of root images to downstream analysis.}, author = {Galkovskyi, Taras and Mileyko, Yuriy and Bucksch, Alexander and Moore, Brad and Symonova, Olga and Price, Charles and Topp, Chrostopher and Iyer Pascuzzi, Anjali and Zurek, Paul and Fang, Suqin and Harer, John and Benfey, Philip and Weitz, Joshua}, journal = {BMC Plant Biology}, publisher = {BioMed Central}, title = {{GiA Roots: Software for the high throughput analysis of plant root system architecture}}, doi = {10.1186/1471-2229-12-116}, volume = {12}, year = {2012}, } @article{493, abstract = {The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.}, author = {Tangermann, Michael and Müller, Klaus and Aertsen, Ad and Birbaumer, Niels and Braun, Christoph and Brunner, Clemens and Leeb, Robert and Mehring, Carsten and Miller, Kai and Müller Putz, Gernot and Nolte, Guido and Pfurtscheller, Gert and Preissl, Hubert and Schalk, Gerwin and Schlögl, Alois and Vidaurre, Carmen and Waldert, Stephan and Blankertz, Benjamin}, journal = {Frontiers in Neuroscience}, publisher = {Frontiers Research Foundation}, title = {{Review of the BCI competition IV}}, doi = {10.3389/fnins.2012.00055}, volume = {6}, year = {2012}, } @inproceedings{495, abstract = {An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.}, author = {Kruckman, Alex and Rubin, Sasha and Sheridan, John and Zax, Ben}, booktitle = {Proceedings GandALF 2012}, location = {Napoli, Italy}, pages = {238 -- 246}, publisher = {Open Publishing Association}, title = {{A Myhill Nerode theorem for automata with advice}}, doi = {10.4204/EPTCS.96.18}, volume = {96}, 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}, } @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}, } @article{494, abstract = {We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.}, author = {Boker, Udi and Kupferman, Orna}, journal = {ACM Transactions on Computational Logic (TOCL)}, number = {4}, publisher = {ACM}, title = {{Translating to Co-Büchi made tight, unified, and useful}}, doi = {10.1145/2362355.2362357}, volume = {13}, 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}, } @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}, } @inproceedings{3165, abstract = {Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H}, booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Kyoto, Japan}, pages = {1386 -- 1399}, publisher = {SIAM}, title = {{An O(n2) time algorithm for alternating Büchi games}}, doi = {10.1137/1.9781611973099.109}, year = {2012}, } @inproceedings{2956, 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 parity 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 computational 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}, booktitle = {Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science}, location = {Dubrovnik, Croatia }, publisher = {IEEE}, title = {{Mean payoff pushdown games}}, doi = {10.1109/LICS.2012.30}, 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}, }