TY - JOUR AB - 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. AU - Ibáñez, Maria AU - Zamani, Reza AU - Li, Wenhua AU - Shavel, Alexey AU - Arbiol, Jordi AU - Morante, Joan AU - Cabot, Andreu ID - 338 IS - 3 JF - Crystal Growth and Design TI - Extending the nanocrystal synthesis control to quaternary compositions VL - 12 ER - TY - JOUR AB - 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. AU - Ibáñez, Maria AU - Cadavid, Doris AU - Zamani, Reza AU - García Castelló, Nuria AU - Izquierdo Roca, Victora AU - Li, Wenhua AU - Fairbrother, Andrew AU - Prades, Joan AU - Shavel, Alexey AU - Arbiol, Jordi AU - Pérez Rodríguez, Alejandro AU - Morante, Joan AU - Cabot, Andreu ID - 339 IS - 3 JF - Chemistry of Materials TI - Composition control and thermoelectric properties of quaternary chalcogenide nanocrystals: The case of stannite Cu2CdSnSe4 VL - 24 ER - TY - JOUR AB - 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. AU - Shavel, Alexey AU - Cadavid, Doris AU - Ibáñez, Maria AU - Carrete, Alex AU - Cabot, Andreu ID - 340 IS - 3 JF - Journal of the American Chemical Society TI - Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor VL - 134 ER - TY - JOUR AB - 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. AU - Cadavid, Doris AU - Ibáñez, Maria AU - Gorsse, Stéphane AU - López, Antonio AU - Cirera, Albert AU - Morante, Joan AU - Cabot, Andreu ID - 345 IS - 12 JF - Journal of Nanoparticle Research TI - Bottom-up processing of thermoelectric nanocomposites from colloidal nanocrystal building blocks: The case of Ag2Te–PbTe VL - 14 ER - TY - JOUR AB - 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. AU - Ibáñez, Maria AU - Zamani, Reza AU - Lalonde, Aaron AU - Cadavid, Doris AU - Li, Wenhua AU - Shavel, Alexey AU - Arbiol, Jordi AU - Morante, Joan AU - Gorsse, Stéphane AU - Snyder, G Jeffrey AU - Cabot, Andreu ID - 347 IS - 9 JF - Journal of the American Chemical Society TI - Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric properties VL - 134 ER - TY - JOUR AB - 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. AU - Ghosal, Arkadeb AU - Iercan, Daniel AU - Kirsch, Christoph AU - Henzinger, Thomas A AU - Sangiovanni Vincentelli, Alberto ID - 3836 IS - 2 JF - Science of Computer Programming TI - Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code VL - 77 ER - TY - JOUR AB - 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. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 2972 JF - Theoretical Computer Science TI - Energy parity games VL - 458 ER - TY - JOUR AB - 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. AU - Alur, Rajeev AU - Cerny, Pavol AU - Weinstein, Scott ID - 2967 IS - 3 JF - ACM Transactions on Computational Logic (TOCL) TI - Algorithmic analysis of array-accessing programs VL - 13 ER - TY - JOUR AB - 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. AU - Galkovskyi, Taras AU - Mileyko, Yuriy AU - Bucksch, Alexander AU - Moore, Brad AU - Symonova, Olga AU - Price, Charles AU - Topp, Chrostopher AU - Iyer Pascuzzi, Anjali AU - Zurek, Paul AU - Fang, Suqin AU - Harer, John AU - Benfey, Philip AU - Weitz, Joshua ID - 492 JF - BMC Plant Biology TI - GiA Roots: Software for the high throughput analysis of plant root system architecture VL - 12 ER - TY - JOUR AB - 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. AU - Tangermann, Michael AU - Müller, Klaus AU - Aertsen, Ad AU - Birbaumer, Niels AU - Braun, Christoph AU - Brunner, Clemens AU - Leeb, Robert AU - Mehring, Carsten AU - Miller, Kai AU - Müller Putz, Gernot AU - Nolte, Guido AU - Pfurtscheller, Gert AU - Preissl, Hubert AU - Schalk, Gerwin AU - Schlögl, Alois AU - Vidaurre, Carmen AU - Waldert, Stephan AU - Blankertz, Benjamin ID - 493 JF - Frontiers in Neuroscience TI - Review of the BCI competition IV VL - 6 ER - TY - CONF AB - 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. AU - Kruckman, Alex AU - Rubin, Sasha AU - Sheridan, John AU - Zax, Ben ID - 495 T2 - Proceedings GandALF 2012 TI - A Myhill Nerode theorem for automata with advice VL - 96 ER - TY - JOUR AB - 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. AU - Pickup, Melinda AU - Field, David AU - Rowell, David AU - Young, Andrew ID - 498 IS - 8 JF - Evolutionary Applications TI - Predicting local adaptation in fragmented plant populations: Implications for restoration genetics VL - 5 ER - TY - CONF AB - 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. AU - Rabinovich, Alexander AU - Rubin, Sasha ID - 496 TI - Interpretations in trees with countably many branches ER - TY - JOUR AB - 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. AU - Boker, Udi AU - Kupferman, Orna ID - 494 IS - 4 JF - ACM Transactions on Computational Logic (TOCL) TI - Translating to Co-Büchi made tight, unified, and useful VL - 13 ER - TY - JOUR AU - Sixt, Michael K ID - 506 IS - 3 JF - Journal of Cell Biology TI - Cell migration: Fibroblasts find a new way to get ahead VL - 197 ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Chaubal, Siddhesh AU - Kamath, Pritish ID - 497 TI - Faster algorithms for alternating refinement relations VL - 16 ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H ID - 3165 T2 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms TI - An O(n2) time algorithm for alternating Büchi games ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 2956 T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science TI - Mean payoff pushdown games ER - TY - GEN AB - 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. AU - Chatterjee, Krishnendu AU - Velner, Yaron ID - 5377 SN - 2664-1690 TI - Mean-payoff pushdown games ER - TY - GEN AB - 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. AU - Chatterjee, Krishnendu AU - Chaubal, Siddhesh AU - Kamath, Pritish ID - 5378 SN - 2664-1690 TI - Faster algorithms for alternating refinement relations ER -