@article{897, abstract = {Transcription is a slow and expensive process: in eukaryotes, approximately 20 nucleotides can be transcribed per second at the expense of at least two ATP molecules per nucleotide. Thus, at least for highly expressed genes, transcription of long introns, which are particularly common in mammals, is costly. Using data on the expression of genes that encode proteins in Caenorhabditis elegans and Homo sapiens, we show that introns in highly expressed genes are substantially shorter than those in genes that are expressed at low levels. This difference is greater in humans, such that introns are, on average, 14 times shorter in highly expressed genes than in genes with low expression, whereas in C. Elegans the difference in intron length is only twofold. In contrast, the density of introns in a gene does not strongly depend on the level of gene expression. Thus, natural selection appears to favor short introns in highly expressed genes to minimize the cost of transcription and other molecular processes, such as splicing. }, author = {Castillo Davis, Cristian and Mekhedov, Sergei and Hartl, Daniel and Koonin, Eugene and Kondrashov, Fyodor}, journal = {Nature Genetics}, number = {4}, pages = {415 -- 418}, publisher = {Nature Publishing Group}, title = {{Selection for short introns in highly expressed genes}}, doi = {10.1038/ng940}, volume = {31}, year = {2002}, } @article{1737, abstract = {A new solvent-free composite polymer electrolyte consisting of high-molecular mass polyethylene oxide (PEO) filled with titanium oxide and containing LiI and I2 was developed. The introduction of the inorganic filler (TiO2 Degussa P25) into the polymer matrix produces dramatic morphological changes to the host polymer structure. Upon addition of the inorganic oxide, the surface roughness increases, with respect to the original polymer and in parallel, the fractal dimension decreases. Both the thermograms and the atomic force microscope (AFM) pictures confirm the amorphicity of the composite electrolyte. The polymer sub-units are held together in a parallel orientation, forming straight long chains of about 500 nm in width, along which TiO2 spherical particles of about 20-25 nm in diameter are distributed. The polymer chains separated by the titania particles are arranged in a three-dimensional, mechanically stable network, that creates free space and voids into which the iodide/triodide anions can easily migrate. All solid-state dye-sensitized solar cells fabricated using this composite electrolyte present high efficiencies (typical maximum incident photon to current efficiency (IPCE) as high as 40% at 520 nm and overall conversion efficiency (η) of 0.96% (Voc = 0.67 V, Jsc = 2.050 mA/cm2, FF = 39%) under direct solar irradiation. Further improvement of the photovoltaic performance is expected by optimization of the electrolyte parameters and of the cell assembly.}, author = {Katsaros, Georgios and Stergiopoulos, Thomas and Arabatzis, Iannis and Papadokostaki, Kyriaki and Falaras, Polycarpos}, issn = {1010-6030}, journal = {Journal of Photochemistry and Photobiology A: Chemistry}, number = {1-3}, pages = {191 -- 198}, publisher = {Elsevier}, title = {{A solvent-free composite polymer/inorganic oxide electrolyte for high efficiency solid-state dye-sensitized solar cells}}, doi = {10.1016/S1010-6030(02)00027-8}, volume = {149}, year = {2002}, } @inproceedings{1738, abstract = {New dyes of the type Ru(II)(bdmpp)(bpy) [where bdmpp is 2,6-bis(3,5-dimethyl-N-pyrazoyl)pyridine and bpy is 2,2′-bipyridine-4,4′-dicarboxylic acid] are prepared and characterized by infra-red (IR), mass (MS) and electrospray mass spectroscopy (ES-MS) as well as 1H NMR (1D and 2D) spectroscopies. The compounds present broad and very high intensity MLCT absorption bands in the visible and can be chemically anchored on TiO2 films via ester-like linkage involving carboxylato groups. These complexes have been tested with success as potential molecular antennas in dye-sensitized solar cells. Both opaque and transparent nanocrystalline TiO2 thin film electrodes obtained by a doctor blade technique sensitized by these complexes were incorporated in a sandwich type regenerative photoelectrochemical solar cell containing 0.1M LiI +0.01M I2 in propylene carbonate as well as a platinized conductive glass counter electrode. The cell was characterized by Raman spectroscopy under anodic and cathodic bias. Two new vibration bands were observed in the lower frequency region. The first one at 112 cm-1 is due to tri-iodide formed on the photoactive electrode, and the second one at 167 cm-1 is a sign of the dye/iodide interaction and corresponds to a vibration in a chemically stable "DI" intermediate species. Under direct sunlight illumination (solar irradiance of 60 mW/cm2) by using a composite polymer solid state electrolyte, the cell ITO/TiO2/[Ru(II)(bdmpp)(bpy)(NCS)](PF6)/electrolyte/Pt-ITO produced a continuous photocurrent as high as 4.29mA/cm2, and gave IPCE values about half of the corresponding values obtained by the standard N3 dye under the same conditions. The photovoltage is about 600 mV and the overall energy conversion cell's efficiency is as high as 1.72%.}, author = {Falaras, Polycarpos and Chryssou, Katerina and Stergiopoulos, Thomas and Arabatzis, Ioannis M and Georgios Katsaros and Catalano, Vincent J and Kurtaran, Raif and Hugot-Le Goff, Anne and Bernard, Marie C}, pages = {125 -- 135}, publisher = {SPIE}, title = {{Dye-sensitization of titanium dioxide thin films by Ru(II)-bpp-bpy complexes}}, doi = {10.1117/12.452446}, volume = {4801}, year = {2002}, } @article{1739, abstract = {Poly(ethylene oxide)/titania polymer electrolyte based photoelectrochemical cells have been fabricated with Ru(dcbpy)2(NCS)2 complex as the sensitizer and nanoporous TiO2 films as photoanodes. The introduction of the titania filler into the poly(ethylene oxide) matrix reduces the crystallinity of the polymer and enhances the mobility of the 1-/13 - redox couple, resulting in outstanding overall conversion efficiency (4.2% under direct sunlight illumination) of the corresponding dye-sensitized nanocrystalline TiO2 solar cell, one of the best efficiencies reported to date for a solid-state device.}, author = {Stergiopoulos, Thomas and Arabatzis, Iannis M and Georgios Katsaros and Falaras, Polycarpos}, journal = {Nano Letters}, number = {11}, pages = {1259 -- 1261}, publisher = {American Chemical Society}, title = {{Binary Polyethylene Oxide/Titania Solid-State Redox Electrolyte for Highly Efficient Nanocrystalline TiO2 Photoelectrochemical Cells}}, doi = {10.1021/nl025798u}, volume = {2}, year = {2002}, } @article{204, abstract = {Let k⩾5 be an integer, and let x⩾1 be an arbitrary real number. We derive a bound[Formula presented] for the number of positive integers less than or equal to x which can be represented as a sum of two non-negative coprime kth powers, in essentially more than one way.}, author = {Browning, Timothy D}, issn = {0022-314X}, journal = {Journal of Number Theory}, number = {2}, pages = {293 -- 318}, publisher = {Academic Press}, title = {{Equal Sums of Two kth Powers}}, doi = {10.1006/jnth.2002.2800}, volume = {96}, year = {2002}, } @inbook{2338, abstract = {Now that the low temperature properties of quantum-mechanical many-body systems (bosons) at low density, ρ, can be examined experimentally it is appropriate to revisit some of the formulas deduced by many authors 4-5 decades ago. For systems with repulsive (i.e. positive) interaction potentials the experimental low temperature state and the ground state are effectively synonymous -- and this fact is used in all modeling. In such cases, the leading term in the energy/particle is 2πℏ2aρ/m where a is the scattering length of the two-body potential. Owing to the delicate and peculiar nature of bosonic correlations (such as the strange N7/5 law for charged bosons), four decades of research failed to establish this plausible formula rigorously. The only previous lower bound for the energy was found by Dyson in 1957, but it was 14 times too small. The correct asymptotic formula has recently been obtained by us and this work will be presented. The reason behind the mathematical difficulties will be emphasized. A different formula, postulated as late as 1971 by Schick, holds in two-dimensions and this, too, will be shown to be correct. With the aid of the methodology developed to prove the lower bound for the homogeneous gas, two other problems have been successfully addressed. One is the proof by us that the Gross-Pitaevskii equation correctly describes the ground state in the `traps' actually used in the experiments. For this system it is also possible to prove complete Bose condensation, as we have shown. Another topic is a proof that Foldy's 1961 theory of a high density Bose gas of charged particles correctly describes its ground state energy.}, author = {Lieb, Élliott and Solovej, Jan and Seiringer, Robert and Yngvason, Jakob}, booktitle = {Current Developments in Mathematics, 2001}, isbn = {9781571461018}, pages = {131 -- 178}, publisher = {International Press}, title = {{The ground state of the Bose gas}}, doi = {10.48550/arXiv.math-ph/0204027}, year = {2002}, } @inproceedings{2339, author = {Robert Seiringer}, editor = {Weder, Richardo and Exner, Pavel and Grébert, Benoit}, pages = {281 -- 286}, publisher = {World Scientific Publishing}, title = {{Symmetry breaking in a model of a rotating Bose gas}}, doi = {10.1090/conm/307}, volume = {307}, year = {2002}, } @article{2349, abstract = {The Bose-Einstein condensation (BEC) of the ground state of bosonic atoms in a trap was discussed. The BEC was proved for bosons with two-body repulsive interaction potentials in the dilute limit, starting from the basic Schrodinger equation. The BEC was 100% into the state which minimized the Gross-Pitaevskii energy functional. The analysis also included rigorous proof of BEC in a physically realistic, continuum model.}, author = {Lieb, Élliott H and Robert Seiringer}, journal = {Physical Review Letters}, number = {17}, pages = {1704091 -- 1704094}, publisher = {American Physical Society}, title = {{Proof of Bose-Einstein condensation for dilute trapped gases}}, doi = {10.1103/PhysRevLett.88.170409}, volume = {88}, year = {2002}, } @article{2350, abstract = {Using the Pauli-Fierz model of non-relativistic quantum electrodynamics, we calculate the binding energy of an electron in the field of a nucleus of charge Z and in presence of the quantized radiation field. We consider the case of small coupling constant α, but fixed Zα and ultraviolet cut-off Λ. We prove that after renormalizing the mass the binding energy has, to leading order in α, a finite limit as Λ goes to infinity; i.e., the cut-off can be removed. The expression for the ground state energy shift thus obtained agrees with Bethe's formula for small values of Zα, but shows a different behavior for bigger values.}, author = {Hainzl, Christian and Seiringer, Robert}, issn = {1095-0761}, journal = {Advances in Theoretical and Mathematical Physics}, number = {5}, pages = {847 -- 871}, publisher = {International Press}, title = {{Mass renormalization and energy level shift in non-relativistic QED}}, doi = {10.4310/ATMP.2002.v6.n5.a3}, volume = {6}, year = {2002}, } @article{2351, abstract = {We study the Gross-Pitaevskii functional for a rotating two-dimensional Bose gas in a trap. We prove that there is a breaking of the rotational symmetry in the ground state; more precisely, for any value of the angular velocity and for large enough values of the interaction strength, the ground state of the functional is not an eigenfunction of the angular momentum. This has interesting consequences on the Bose gas with spin; in particular, the ground state energy depends non-trivially on the number of spin components, and the different components do not have the same wave function. For the special case of a harmonic trap potential, we give explicit upper and lower bounds on the critical coupling constant for symmetry breaking.}, author = {Robert Seiringer}, journal = {Communications in Mathematical Physics}, number = {3}, pages = {491 -- 509}, publisher = {Springer}, title = {{Gross-Pitaevskii theory of the rotating Bose gas}}, doi = {10.1007/s00220-002-0695-2}, volume = {229}, year = {2002}, } @article{2352, abstract = {We present a generalization of the Fefferman-de la Llave decomposition of the Coulomb potential to quite arbitrary radial functions V on ℝn going to zero at infinity. This generalized decomposition can be used to extend previous results on N-body quantum systems with Coulomb interaction to a more general class of interactions. As an example of such an application, we derive the high density asymptotics of the ground state energy of jellium with Yukawa interaction in the thermodynamic limit, using a correlation estimate by Graf and Solovej.}, author = {Hainzl, Christian and Robert Seiringer}, journal = {Letters in Mathematical Physics}, number = {1}, pages = {75 -- 84}, publisher = {Springer}, title = {{General decomposition of radial functions on ℝn and applications to N-body quantum systems}}, doi = {10.1023/A:1020204818938}, volume = {61}, year = {2002}, } @article{2353, abstract = {A commonly used theoretical definition of superfluidity in the ground state of a Bose gas is based on the response of the system to an imposed velocity field or, equivalently, to twisted boundary conditions in a box. We are able to carry out this program in the case of a dilute interacting Bose gas in a trap, and we prove that a gas with repulsive interactions is 100% superfluid in the dilute limit in which the Gross-Pitaevskii equation is exact. This is the first example in an experimentally realistic continuum model in which superfluidity is rigorously verified.}, author = {Lieb, Élliott and Seiringer, Robert and Yngvason, Jakob}, issn = {0163-1829}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {13}, publisher = {American Physical Society}, title = {{Superfluidity in dilute trapped Bose gases}}, doi = {10.1103/PhysRevB.66.134529}, volume = {66}, year = {2002}, } @article{2420, abstract = {A corner cut in dimension d is a finite subset of N0d that can be separated from its complement in N0d by an affine hyperplane disjoint from N0d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write (Nd0k)cut for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N0d. Among other things, Onn and Sturmfels give an upper bound of O(k2d(d-1)/(d+1)) for the size of (Nd0k)cut when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #(Nd0k)cut = Θ(k log k). We will see that in general, for any fixed dimension d, the order of magnitude of #(Nd0k)cut is between kd-1 log k and (k log k)d-1. (It has been communicated to me that the same bounds have been found independently by G. Rémond.) In fact, the elements of (Nd0k)cut correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.}, author = {Wagner, Uli}, issn = {0196-8858}, journal = {Advances in Applied Mathematics}, number = {2}, pages = {152 -- 161}, publisher = {ACM}, title = {{On the number of corner cuts}}, doi = {10.1016/S0196-8858(02)00014-3}, volume = {29}, year = {2002}, } @inproceedings{2421, abstract = {Intersection graphs of disks and of line segments, respectively, have been well studied, because of both, practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses which in a sense, interpolate between disc and ellipses, and show that it is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.}, author = {Ambühl, Christoph and Wagner, Uli}, booktitle = {Proceedings of the 13th International Symposium on Algorithms and Computation}, isbn = {9783540001423}, location = {Vancouver, Canada}, pages = {489 -- 500}, publisher = {Springer}, title = {{On the Clique problem in intersection graphs of ellipses}}, doi = {10.1007/3-540-36136-7_43}, volume = {2518}, year = {2002}, } @inproceedings{4562, abstract = {We present interface models that describe both the input assumptions of a component, and its output behavior. By enabling us to check that the input assumptions of a component are met in a design, interface models provide a compatibility check for component-based design. When refining a design into an implementation, interface models require that the output behavior of a component satisfies the design specification only when the input assumptions of the specification are satisfied, yielding greater flexibility in the choice of implementations. Technically, our interface models are games between two players, Input and Output; the duality of the players accounts for the dual roles of inputs and outputs in composition and refinement. We present two interface models in detail, one for a simple synchronous form of interaction between components typical in hardware, and the other for more complex synchronous interactions on bidirectional connections. As an example, we specify the interface of a bidirectional bus, with the input assumption that at any time at most one component has write access to the bus. For these interface models, we present algorithms for compatibility and refinement checking, and we describe efficient symbolic implementations.}, author = {Chakrabarti, Arindam and De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy}, booktitle = {Proceedings of the 14th International Conference on Computer Aided Verification}, isbn = {9783540439974}, location = {Copenhagen, Denmark}, pages = {414 -- 427}, publisher = {Springer}, title = {{Synchronous and bidirectional component interfaces}}, doi = {10.1007/3-540-45657-0_34}, volume = {2404}, year = {2002}, } @inproceedings{4563, abstract = {We present a formal methodology and tool for uncovering errors in the interaction of software modules. Our methodology consists of a suite of languages for defining software interfaces, and algorithms for checking interface compatibility. We focus on interfaces that explain the method-call dependencies between software modules. Such an interface makes assumptions about the environment in the form of call and availability constraints. A call constraint restricts the accessibility of local methods to certain external methods. An availability constraint restricts the accessibility of local methods to certain states of the module. For example, the interface for a file server with local methods open and read may assert that a file cannot be read without having been opened. Checking interface compatibility requires the solution of games, and in the presence of availability constraints, of pushdown games. Based on this methodology, we have implemented a tool that has uncovered incompatibilities in TinyOS, a small operating system for sensor nodes in adhoc networks.}, author = {Chakrabarti, Arindam and De Alfaro, Luca and Henzinger, Thomas A and Jurdziński, Marcin and Mang, Freddy}, booktitle = {Proceedings of the 14th International Conference on Computer Aided Verification}, isbn = { 9783540439974}, location = {Copenhagen, Denmark}, pages = {428 -- 441}, publisher = {Springer}, title = {{Interface compatibility checking for software modules}}, doi = {10.1007/3-540-45657-0_35}, volume = {2404}, year = {2002}, } @inproceedings{4565, abstract = {In the literature, we find several formulations of the control problem for timed and hybrid systems. We argue that formulations where a controller can cause an action at any point in dense (rational or real) time are problematic, by presenting an example where the controller must act faster and faster, yet causes no Zeno effects (say, the control actions are at times 0, 1/2, 1, 1 1/4, 2, 2 1/8, 3, 3 1/16 ,...). Such a controller is, of course, not implementable in software. Such controllers are avoided by formulations where the controller can cause actions only at discrete (integer) points in time. While the resulting control problem is well- understood if the time unit, or “sampling rate” of the controller, is fixed a priori, we define a novel, stronger formulation: the discrete-time control problem with unknown sampling rate asks if a sampling controller exists for some sampling rate. We prove that this problem is undecidable even in the special case of timed automata.}, author = {Cassez, Franck and Henzinger, Thomas A and Raskin, Jean}, booktitle = {Proceedings of the 5th International Workshop on Hybrid Systems: Computation and Control}, isbn = {9783540433217}, location = {Stanford, CA, USA}, pages = {134 -- 148}, publisher = {Springer}, title = {{A comparison of control problems for timed and hybrid systems}}, doi = {10.1007/3-540-45873-5_13}, volume = {2289}, year = {2002}, } @article{4595, abstract = {Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by the execution of a system; branching-time temporal logic allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic: alternating-time temporal logic offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator "eventually" with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. The problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas. Depending on whether or not we admit arbitrary nesting of selective path quantifiers and temporal operators, we obtain the two alternating-time temporal logics ATL and ATL*.ATL and ATL* are interpreted over concurrent game structures. Every state transition of a concurrent game structure results from a choice of moves, one for each player. The players represent individual components and the environment of an open system. Concurrent game structures can capture various forms of synchronous composition for open systems, and if augmented with fairness constraints, also asynchronous composition. Over structures without fairness constraints, the model-checking complexity of ATL is linear in the size of the game structure and length of the formula, and the symbolic model-checking algorithm for CTL extends with few modifications to ATL. Over structures with weak-fairness constraints, ATL model checking requires the solution of 1-pair Rabin games, and can be done in polynomial time. Over structures with strong-fairness constraints, ATL model checking requires the solution of games with Boolean combinations of Büchi conditions, and can be done in PSPACE. In the case of ATL*, the model-checking problem is closely related to the synthesis problem for linear-time formulas, and requires doubly exponential time.}, author = {Alur, Rajeev and Henzinger, Thomas A and Kupferman, Orna}, issn = {0004-5411}, journal = {Journal of the ACM}, number = {5}, pages = {672 -- 713}, publisher = {ACM}, title = {{Alternating-time temporal logic}}, doi = {10.1145/585265.585270}, volume = {49}, year = {2002}, } @inproceedings{4631, abstract = {We present a theory of timed interfaces, which is capable of specifying both the timing of the inputs a component expects from the environment, and the timing of the outputs it can produce. Two timed interfaces are compatible if there is a way to use them together such that their timing expectations are met. Our theory provides algorithms for checking the compatibility between two interfaces and for deriving the composite interface; the theory can thus be viewed as a type system for real-time interaction. Technically, a timed interface is encoded as a timed game between two players, representing the inputs and outputs of the component. The algorithms for compatibility checking and interface composition are thus derived from algorithms for solving timed games.}, author = {De Alfaro, Luca and Henzinger, Thomas A and Stoelinga, Mariëlle}, booktitle = {Proceedings of the 2nd International Conference on Embedded Software}, isbn = {9783540443070}, location = {Grenoble, France}, pages = {108 -- 122}, publisher = {ACM}, title = {{Timed interfaces}}, doi = {10.1007/3-540-45828-X_9}, volume = {2491}, year = {2002}, } @article{6158, abstract = {Wild isolates of Caenorhabditis elegans can feed either alone or in groups1,2. This natural variation in behaviour is associated with a single residue difference in NPR-1, a predicted G-protein-coupled neuropeptide receptor related to Neuropeptide Y receptors2. Here we show that the NPR-1 isoform associated with solitary feeding acts in neurons exposed to the body fluid to inhibit social feeding. Furthermore, suppressing the activity of these neurons, called AQR, PQR and URX, using an activated K+ channel, inhibits social feeding. NPR-1 activity in AQR, PQR and URX neurons seems to suppress social feeding by antagonizing signalling through a cyclic GMP-gated ion channel encoded by tax-2 and tax-4. We show that mutations in tax-2 or tax-4 disrupt social feeding, and that tax-4 is required in several neurons for social feeding, including one or more of AQR, PQR and URX. The AQR, PQR and URX neurons are unusual in C. elegans because they are directly exposed to the pseudocoelomic body fluid3. Our data suggest a model in which these neurons integrate antagonistic signals to control the choice between social and solitary feeding behaviour.}, author = {Coates, Juliet C. and de Bono, Mario}, issn = {0028-0836}, journal = {Nature}, number = {6910}, pages = {925--929}, publisher = {Springer Nature}, title = {{Antagonistic pathways in neurons exposed to body fluid regulate social feeding in Caenorhabditis elegans}}, doi = {10.1038/nature01170}, volume = {419}, year = {2002}, }