@article{11685, abstract = {We consider the problem of sampling URLs uniformly at random from the Web. A tool for sampling URLs uniformly can be used to estimate various properties of Web pages, such as the fraction of pages in various Internet domains or written in various languages. Moreover, uniform URL sampling can be used to determine the sizes of various search engines relative to the entire Web. In this paper, we consider sampling approaches based on random walks of the Web graph. In particular, we suggest ways of improving sampling based on random walks to make the samples closer to uniform. We suggest a natural test bed based on random graphs for testing the effectiveness of our procedures. We then use our sampling approach to estimate the distribution of pages over various Internet domains and to estimate the coverage of various search engine indexes.}, author = {Henzinger, Monika H and Heydon, Allan and Mitzenmacher, Michael and Najork, Marc}, issn = {1389-1286}, journal = {Computer Networks}, keywords = {URL sampling, Random walks, Internet domain distribution, Search engine size}, number = {1-6}, pages = {295--308}, publisher = {Elsevier}, title = {{On near-uniform URL sampling}}, doi = {10.1016/s1389-1286(00)00055-4}, volume = {33}, year = {2000}, } @article{11694, abstract = {We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the 1rst subexponential algorithm for this exploration problem, which achieves an upper bound of dO(logd)m. We also show a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration algorithms.}, author = {Albers, Susanne and Henzinger, Monika H}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, keywords = {directed graph, exploration algorithm}, location = {El Paso, TX, United States}, number = {4}, pages = {1164--1188}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Exploring unknown environments}}, doi = {10.1137/s009753979732428x}, volume = {29}, year = {2000}, } @article{11770, abstract = {We compare several algorithms for identifying mirrored hosts on the World Wide Web. The algorithms operate on the basis of URL strings and linkage data: the type of information about Web pages easily available from Web proxies and crawlers. Identification of mirrored hosts can improve Web-based information retrieval in several ways: first, by identifying mirrored hosts, search engines can avoid storing and returning duplicate documents. Second, several new information retrieval techniques for the Web make inferences based on the explicit links among hypertext documents—mirroring perturbs their graph model and degrades performance. Third, mirroring information can be used to redirect users to alternate mirror sites to compensate for various failures, and can thus improve the performance of Web browsers and proxies. We evaluated four classes of “top-down” algorithms for detecting mirrored host pairs (that is, algorithms that are based on page attributes such as URL, IP address, and hyperlinks between pages, and not on the page content) on a collection of 140 million URLs (on 230,000 hosts) and their associated connectivity information. Our best approach is one which combines five algorithms and achieved a precision of 0.57 for a recall of 0.86 considering 100,000 ranked host pairs.}, author = {Bharat, Krishna and Broder, Andrei and Dean, Jeffrey and Henzinger, Monika H}, issn = {0002-8231}, journal = {Journal of the American Society for Information Science}, number = {12}, pages = {1114--1122}, publisher = {Wiley}, title = {{A comparison of techniques to find mirrored hosts on the WWW}}, doi = {10.1002/1097-4571(2000)9999:9999<::aid-asi1025>3.0.co;2-0}, volume = {51}, year = {2000}, } @article{842, author = {Wolf, Yuri and Kondrashov, Fyodor and Koonin, Eugene}, issn = {0168-9479}, journal = {Trends in Genetics}, number = {8}, pages = {333 -- 334}, publisher = {Elsevier}, title = {{No footprints of primordial introns in a eukaryotic genome}}, doi = {10.1016/S0168-9525(00)02059-X}, volume = {16}, year = {2000}, } @article{8525, abstract = {Let M be a smooth compact manifold of dimension at least 2 and Diffr(M) be the space of C r smooth diffeomorphisms of M. Associate to each diffeomorphism f;isin; Diffr(M) the sequence P n (f) of the number of isolated periodic points for f of period n. In this paper we exhibit an open set N in the space of diffeomorphisms Diffr(M) such for a Baire generic diffeomorphism f∈N the number of periodic points P n f grows with a period n faster than any following sequence of numbers {a n } n ∈ Z + along a subsequence, i.e. P n (f)>a ni for some n i →∞ with i→∞. In the cases of surface diffeomorphisms, i.e. dim M≡2, an open set N with a supergrowth of the number of periodic points is a Newhouse domain. A proof of the man result is based on the Gontchenko–Shilnikov–Turaev Theorem [GST]. A complete proof of that theorem is also presented.}, author = {Kaloshin, Vadim}, issn = {0010-3616}, journal = {Communications in Mathematical Physics}, keywords = {Mathematical Physics, Statistical and Nonlinear Physics}, pages = {253--271}, publisher = {Springer Nature}, title = {{Generic diffeomorphisms with superexponential growth of number of periodic orbits}}, doi = {10.1007/s002200050811}, volume = {211}, year = {2000}, } @inproceedings{1736, abstract = {A coding scheme called diode is compared with duobinary signalling and with normal binary transmission. It is shown that the diode coding suppresses the FWM products of a three channel DWDM system and this reduction against that achieved with duobinary coding is presented. The results presented show how the average level of the FWM products relative to the average levels of the three optical carriers vary over the channel spacing range. The suppression observed is about / dB more than that achieved with duobinary modulation and is greater for narrow channel spacing.}, author = {Katsaros, Georgios and Lane, Phil and Murphy, Michelle}, booktitle = {Proceedings of the 2000 IEEE Annual Meeting Conference }, isbn = {078035947X}, location = {Rio Grande, PR, USA}, pages = {27 -- 28}, publisher = {IEEE}, title = {{Comparison of the impact of FWM on binary, duobinary and dicode modulation in DWDM systems}}, doi = {10.1109/LEOS.2000.890656}, volume = {1}, year = {2000}, } @article{1957, abstract = {NADH:ubiquinone oxidoreductase (complex I) is the first and largest enzyme of the mitochondrial respiratory chain. The low-resolution structure of the complex is known from electron microscopy studies. The general shape of the complex is in the form of an L, with one arm in the membrane and the other peripheral. We have purified complex I from beef heart mitochondria and reconstituted the enzyme into lipid bilayers. Under different conditions, several two-dimensional crystal forms were obtained. Crystals belonging to space groups p2221 and c12 (unit cell 488 Å x 79 Å) were obtained at 22°C and contained only the membrane fragment of complex I similar to hydrophobic subcomplex Iβ but lacking the ND5 subunit. A crystal form with larger unit cell (534 Å x 81 Å, space group c12) produced at 4°C contained both the peripheral and membrane arms of the enzyme, except that ND5 was missing. Projection maps from frozen hydrated samples were calculated for all crystal forms. By comparing two different c12 crystal forms, extra electron density in the projection map of large crystal form was assigned to the peripheral arm of the enzyme. One of the features of the map is a deep, channel-like, cleft next to peripheral arm. Comparison with available structures of the intact enzyme indicates that large hydrophobic subunit ND5 is situated at the distal end of the membrane domain. Possible locations of sub-unit ND4 and of other subunits in the membrane domain are proposed. Implications of our findings for the mechanism of proton pumping by complex I are discussed. (C) 2000 Academic Press.}, author = {Sazanov, Leonid A and Walker, John}, issn = {0022-2836}, journal = {Journal of Molecular Biology}, number = {2}, pages = {455 -- 464}, publisher = {Elsevier}, title = {{Cryo-electron crystallography of two sub-complexes of bovine complex I reveals the relationship between the membrane and peripheral arms}}, doi = {10.1006/jmbi.2000.4079}, volume = {302}, year = {2000}, } @article{1958, abstract = { Complex I (NADH:ubiquinone oxidoreductase) purified from bovine heart mitochondria was treated with the detergent N,N-dimethyldodecylamine N-oxide (LDAO). The enzyme dissociated into two known subcomplexes, Iα and Iβ, containing mostly hydrophilic and hydrophobic subunits, and a previously undetected fragment referred to as Iγ. Subcomplex Iγ contains the hydrophobic subunits ND1, ND2, ND3, and ND4L which are encoded in the mitochondrial genome, and the nuclear-encoded subunit KFYL. During size- exclusion chromatography in the presence of LDAO, subcomplex Iα lost several subunits and formed another characterized subcomplex known as Iλ. Similarly, subcomplex Iβ dissociated into two smaller subcomplexes, one of which contains the hydrophobic subunits ND4 and ND5; subcomplex Iγ released a fragment containing ND1 and ND2. These results suggest that in the intact complex subunits ND1 and ND2 are likely to be in a different region of the membrane domain than subunits ND4 and ND5. The compositions of the various subcomplexes and fragments of complex I provide an organization of the subunits of the enzyme in the framework of the known low resolution structure of the enzyme.}, author = {Sazanov, Leonid A and Peak Chew, Sew and Fearnley, Ian and Walker, John}, issn = {0006-2960}, journal = {Biochemistry}, number = {24}, pages = {7229 -- 7235}, publisher = {ACS}, title = {{Resolution of the membrane domain of bovine complex I into subcomplexes: implications for the structural organization of the enzyme}}, doi = {10.1021/bi000335t}, volume = {39}, year = {2000}, } @inproceedings{2325, author = {Robert Seiringer}, pages = {53 -- 72}, publisher = {American Mathematical Society}, title = {{Inequalities for Schrödinger operators and applications to the stability of matter problem }}, doi = {10.1090/conm/529}, volume = {529}, year = {2000}, } @inproceedings{2342, abstract = {In the theoretical description of recent experiments with dilute Bose gases confined in external potentials the Gross-Pitaevskii equation plays an important role. Its status as an approximation for the quantum mechanical many-body ground state problem has recently been rigorously clarified. A summary of this work is presented here.}, author = {Seiringer, Robert and Lieb, Élliott and Yngvason, Jakob}, booktitle = {Proceedings of the International Symposium on Quantum Theory and Symmetries}, isbn = {9789810242374 }, pages = {101 -- 110}, publisher = {World Scientific Publishing}, title = {{The ground state energy and density of interacting bosons in a trap}}, year = {2000}, } @article{2343, abstract = {We study the energy levels of a single particle in a homogeneous magnetic field and in an axially symmetric external potential. For potentials that are superharmonic off the central axis, we find a general 'pseudoconcave' ordering of the ground state energies of the Hamiltonian restricted to the sectors with fixed angular momentum. The physical applications include atoms and ions in strong magnetic fields. There the energies are monotone increasing and concave in angular momentum. In the case of a periodic chain of atoms, the pseudoconcavity extends to the entire lowest band of Bloch functions.}, author = {Baumgartner, Bernhard and Robert Seiringer}, journal = {Letters in Mathematical Physics}, number = {3}, pages = {213 -- 226}, publisher = {Springer}, title = {{On the ordering of energy levels in homogeneous magnetic fields}}, doi = { 10.1023/A:1010978807635}, volume = {54}, year = {2000}, } @article{2344, abstract = {The ground-state properties of interacting Bose gases in external potentials, as considered in recent experiments, are usually described by means of the Gross-Pitaevskii energy functional. We present here a rigorous proof of the asymptotic exactness of this approximation for the ground-state energy and particle density of a dilute Bose gas with a positive interaction.}, author = {Lieb, Élliott and Seiringer, Robert and Yngvason, Jakob}, issn = {0556-2791}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {4}, pages = {436021 -- 4360213}, publisher = {American Physical Society}, title = {{Bosons in a trap: A rigorous derivation of the Gross-Pitaevskii energy functional}}, doi = {10.1103/PhysRevA.61.043602}, volume = {61}, year = {2000}, } @inproceedings{2418, abstract = {For an absolutely continuous probability measure μ on Rd and a nonnegative integer k, let sk(μ, 0) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on sk(μ, 0), and we characterize the measures in Rd which attain this bound. This result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors for simplicial convex polytopes.}, author = {Wagner, Uli and Welzl, Emo}, booktitle = {Proceedings of the 16th annual symposium on Computational geometry}, isbn = {9781581132243}, location = {Clear Water Bay Kowloon, Hong Kong}, pages = {50 -- 56}, publisher = {ACM}, title = {{Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem}}, doi = {10.1145/336154.336176}, year = {2000}, } @article{4598, abstract = {A hybrid system is a dynamical system with both discrete and continuous state changes. For analysis purposes, it is often useful to abstract a system in a way that preserves the properties being analyzed while hiding the details that are of no interest. We show that interesting classes of hybrid systems can be abstracted to purely discrete systems while preserving all properties that are definable in temporal logic. The classes that permit discrete abstractions fall into two categories. Either the continuous dynamics must be restricted, as is the case for timed and rectangular hybrid systems, or the discrete dynamics must be restricted, as is the case for o-minimal hybrid systems. In this paper, we survey and unify results from both areas.}, author = {Alur, Rajeev and Henzinger, Thomas A and Lafferriere, Gerardo and Pappas, George}, issn = {0018-9219}, journal = {Proceedings of the IEEE}, number = {7}, pages = {971 -- 984}, publisher = {IEEE}, title = {{Discrete abstractions of hybrid systems}}, doi = {10.1109/5.871304 }, volume = {88}, year = {2000}, } @inproceedings{4627, abstract = {We consider two-player games, which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two moves determine a successor state. We consider omega-regular winning conditions on the resulting infinite state sequence. To model the independent choice of moves, both players are allowed to use randomization for selecting their moves. This gives rise to the following qualitative modes of winning, which can be studied without numerical considerations concerning probabilities: sure-win (player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure winning with probability 1), limit-win (player 1 can ensure winning with probability arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability bounded away from 0), positive-win (player 1 can ensure winning with positive probability), and exist-win (player 1 can ensure that at least one possible outcome of the game satisfies the winning condition).We provide algorithms for computing the sets of winning states for each of these winning modes. In particular, we solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the game structure and m is the number of pairs in the Rabin-chain condition. While this complexity is in line with traditional turn-based games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games are. This is because concurrent games violate two of the most fundamental properties of turn-based games. First, concurrent games are not determined, but rather exhibit a more general duality property, which involves multiple modes of winning. Second, winning strategies for concurrent games may require infinite memory.}, author = {De Alfaro, Luca and Henzinger, Thomas A}, booktitle = {Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science}, isbn = {0769507255}, location = {Santa Barbara, CA, USA}, pages = {141 -- 154}, publisher = {IEEE}, title = {{Concurrent omega-regular games}}, doi = {10.1109/LICS.2000.855763}, year = {2000}, } @inproceedings{4637, abstract = {In the synchronous composition of processes, one process may prevent another process from proceeding unless compositions without a well-defined product behavior are ruled out. They can be ruled out semantically, by insisting on the existence of certain fixed points, or syntactically, by equipping processes with types, which make the dependencies between input and output signals transparent. We classify various typing mechanisms and study their effects on the control problem. A static type enforces fixed, acyclic dependencies between input and output ports. For example, synchronous hardware without combinational loops can be typed statically. A dynamic type may vary the dependencies from state to state, while maintaining acyclicity, as in level-sensitive latches. Then, two dynamically typed processes can be syntactically compatible, if all pairs of possible dependencies are compatible, or semantically compatible, if in each state the combined dependencies remain acyclic. For a given plant process and control objective, there may be a controller of a static type, or only a controller of a syntactically compatible dynamic type, or only a controller of a semantically compatible dynamic type. We show this to be a strict hierarchy of possibilities, and we present algorithms and determine the complexity of the corresponding control problems. Furthermore, we consider versions of the control problem in which the type of the controller (static or dynamic) is given. We show that the solution of these fixed-type control problems requires the evaluation of partially ordered (Henkin) quantifiers on boolean formulas, and is therefore harder (nondeterministic exponential time) than more traditional control questions}, author = {De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy}, booktitle = {Proceedings of the 11th International Conference on Concurrency Theory}, isbn = {9783540678977}, location = {University Park, PA, USA}, pages = {458 -- 473}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The control of synchronous systems}}, doi = {10.1007/3-540-44618-4_33}, volume = {1877}, year = {2000}, } @inproceedings{4638, abstract = {Any formal method or tool is almost certainly more often applied in situations where the outcome is failure (a counterexample) rather than success (a correctness proof). We present a method for symbolic model checking that can lead to significant time and memory savings for model-checking runs that fail, while occurring only a small overhead for model-checking runs that succeed. Our method discovers an error as soon as it cannot be prevented, which can be long before it actually occurs; for example, the violation of an invariant may become unpreventable many transitions before the invariant is violated. The key observation is that “unpreventability” is a local property of a single module: an error is unpreventable in a module state if no environment can prevent it. Therefore, unpreventability is inexpensive to compute for each module, yet can save much work in the state exploration of the global, compound system. Based on different degrees of information available about the environment, we define and implement several notions of “unpreventability,” including the standard notion of uncontrollability from discrete-event control. We present experimental results for two examples, a distributed database protocol and a wireless communication protocol.}, author = {De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy}, booktitle = {Proceedings of the 12th International Conference on Computer Aided Verification}, isbn = {9783540677703}, location = {Chicago, IL, USA}, pages = {186 -- 201}, publisher = {Springer}, title = {{Detecting errors before reaching them}}, doi = {10.1007/10722167_17}, volume = {1855}, year = {2000}, } @article{1455, abstract = {First, a special case of Knaster's problem is proved implying that each symmetric convex body in ℝ3 admits an inscribed cube. It is deduced from a theorem in equivariant topology, which says that there is no S4 - equivariant map from SO(3) to S2, where S4 acts on SO(3) on the right as the rotation group of the cube, and on S2 on the right as the symmetry group of the regular tetrahedron. Some generalizations are also given. Second, it is shown how the above non-existence theorem yields Makeev's conjecture in ℝ3 that each set in ℝ3 of diameter 1 can be covered by a rhombic dodecahedron, which has distance 1 between its opposite faces. This reveals an unexpected connection between inscribing cubes into symmetric bodies and covering sets by rhombic dodecahedra. Finally, a possible application of our second theorem to the Borsuk problem in ℝ3 is pointed out.}, author = {Hausel, Tamas and Makai, Endre and Szücs, András}, issn = {0025-5793}, journal = {Mathematika}, number = {1-2}, pages = {371 -- 397}, publisher = {University College London}, title = {{Inscribing cubes and covering by rhombic dodecahedra via equivariant topology}}, doi = {10.1112/S0025579300015965}, volume = {47}, year = {2000}, } @article{13437, abstract = {Liquid/liquid Phase Transfer Catalysis (PTC) reaction of 4-chlorobutyronitrile with nonenolisable aldehydes leads via an addition-cyclisation reaction sequence to derivatives of tetrahydrofuran-3-carbonitrile.}, author = {Macogonkosza, Mieczysław and Przyborowski, Jacek and Klajn, Rafal and Kwast, Andrzej}, issn = {1437-2096}, journal = {Synlett}, keywords = {Organic Chemistry}, number = {12}, pages = {1773--1774}, publisher = {Georg Thieme Verlag}, title = {{Simple synthesis of 2-substituted Tetrahydrofuran-3-carbonitriles}}, doi = {10.1055/s-2000-8670}, volume = {2000}, year = {2000}, } @inproceedings{11802, abstract = {In this paper we survey algorithmic aspects of Web information retrieval. As an example, we discuss ranking of search engine results using connectivity analysis.}, author = {Henzinger, Monika H}, booktitle = {8th Annual European Symposium on Algorithms}, isbn = {9783540410041}, issn = {1611-3349}, location = {Saarbrücken, Germany}, pages = {1–8}, publisher = {Springer Nature}, title = {{Web information retrieval - an algorithmic perspective}}, doi = {10.1007/3-540-45253-2_1}, volume = {1879}, year = {2000}, }