检索结果-内蒙古大学图书馆

Forbidden time travel: Characterization of time-consistent tree reconciliation maps

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Nøjgaard, Nikolai Geiß, Manuela Stadler, Peter F. Merkle, Daniel Wieseke, Nicolas Hellmuth, Marc Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Department of Mathematics and Computer Science University of Southern Denmark Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. Copyright © 2017, The Authors. All rights reserved.

关键词： Genes

Vibration isolation system with a compact damping system for power recycling mirrors of KAGRA

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Akiyama, Y. Akutsu, T. Ando, M. Arai, K. Arai, Y. Araki, S. Araya, A. Aritomi, N. Asada, H. Aso, Y. Bae, S. Baiotti, L. Barton, M.A. Cannon, K. Capocasa, E. Chen, C.-S. Chiu, T.-W. Cho, K. Chu, Y.-K. Craig, K. Dattilo, V. Doi, K. Enomoto, Y. Flaminio, R. Fujii, Y. Fujimoto, M.-K. Fukunaga, M. Fukushima, M. Furuhata, T. Haino, S. Hasegawa, K. Hashimoto, Y. Hashino, K. Hayama, K. Hirayama, T. Hirose, E. Hsieh, B.H. Huang, C.-Z. Ikenoue, B. Inoue, Y. Ioka, K. Itoh, Y. Izumi, K. Kaji, T. Kajita, T. Kakizaki, M. Kamiizumi, M. Kanbara, S. Kanda, N. Kanemura, S. Kang, G. Kasuya, J. Kawai, N. Kawasaki, T. Kim, C. Kim, W.S. Kim, J. Kim, J.C. Kimura, N. Kirii, S. Kitaoka, Y. Kitazawa, H. Kojima, Y. Kokeyama, K. Komori, K. Kong, A. Kotake, K. Kozu, R. Kumar, R. Kuo, H.-S. Kuroki, S. Kuroyanagi, S. Lee, H.K. Lee, H.M. Lee, H.W. Leonardi, M. Lin, C.-Y. Lin, F.-L. Liu, G.C. Marchio, M. Matsui, T. Michimura, Y. Mio, N. Miyakawa, O. Miyamoto, A. Miyoki, S. Morii, W. Morisaki, S. Moriwaki, Y. Musha, M. Nagano, S. Nagano, K. Nakamura, K. Nakamura, T. Nakano, H. Nakano, M. Narikawa, T. Quynh, L. Nguyen Ni, W.-T. Nishizawa, A. Obuchi, Y. Oh, J. Oh, S.H. Ohashi, M. Ohishi, N. Ohkawa, M. Okutomi, K. Ono, K. Oohara, K. Ooi, C.P. Pan, S.-S. Paoletti, F. Park, J. Passaquieti, R. Peña Arellano, F.E. Sago, N. Saito, S. Saito, Y. Sakai, K. Sakai, Y. Sasai, M. Sato, S. Sato, T. Sekiguchi, T. Sekiguchi, Y. Shibata, M. Shimoda, T. Shinkai, H. Shishido, T. Shoda, A. Someya, N. Somiya, K. Son, E.J. Suemasa, A. Suzuki, T. Suzuki, T. Tagoshi, H. Tahara, H. Takahashi, H. Takahashi, R. Takeda, H. Tanaka, H. Tanaka, K. Tanaka, T. Tanioka, S. San Martin, E.N. Tapia Tomaru, T. Tomura, T. Travasso, F. Tsubono, K. Tsuchida, S. Uchikata, N. Uchiyama, T. Uehara, T. Ueno, K. Uraguchi, F. Ushiba, T. van Putten, M.H.P.M. Vocca, H. Wakamatsu, T. Watanabe, Y. Xu, W.-R. Yamada, T. Yamamoto, K. Yamamoto, K. Yamamoto, S. Yamamoto, T. Yokogawa, K. Yokoyama, J. Yokozawa, T. Yoshioka, T. Yuzurihara, H. Zeidler, S. Zhu, Z.-H. Graduate School of Science and Engineering Hosei University TokyoKoganei184-8584 Japan National Astronomical Observatory of Japan TokyoMitaka181-8588 Japan Department of Physics University of Tokyo TokyoBunkyo113-0033 Japan University of Tokyo KashiwaChiba277-8582 Japan High Energy Accelerator Research Organization TsukubaIbaraki305-0801 Japan Earthquake Research Institute University of Tokyo TokyoBunkyo113-0032 Japan Department of Physics University of Tokyo TokyoBunkyo113-0033 Japan Department of Mathematics and Physics Hirosaki University AomoriHirosaki036-8561 Japan National Astronomical Observatory of Japan GifuHida506-1205 Japan Korea Institute of Science and Technology Information Yuseong Daejeon34141 Korea Republic of Department of Physics Osaka University ToyonakaOsaka560-0043 Japan University of Tokyo TokyoBunkyo113-0033 Japan Department of Physics National Taiwan Normal University Taipei116 Taiwan Department of Physics Sogang University Seoul121-742 Korea Republic of PisaCascinaI-56021 Italy Department of Physics University of Toyama ToyamaToyama930-8555 Japan Department of Astronomy University of Tokyo TokyoBunkyo113-0032 Japan Advanced Technology Center National Astronomical Observatory of Japan TokyoMitaka181-8588 Japan Institute of Physics Academia Sinica TaipeiNankang11529 Taiwan Department of Applied Physics Fukuoka University FukuokaJonan814-0180 Japan Yukawa Institute for Theoretical Physics Kyoto University KyotoSakyo606-8502 Japan Graduate School of Science Osaka City University OsakaSumiyosi558-8585 Japan Institute of Space and Astronautical Science Japan Aerospace Exploration Agency SagamiharaKanagawa252-5210 Japan University of Tokyo GifuHida506-1205 Japan Graduate Schoool of Science and Technology Tokyo Institute of Technology MeguroTokyo152-8551 Japan Department of Physics Ewha Womans University SeoulSeodaemun-gu03760 Korea Republic of National Institute for

A vibration isolation system called Type-Bp system used for power recycling mirrors has been developed for KAGRA, the interferometric gravitational-wave observatory in Japan. A suspension of the Type-Bp system passively isolates an optic from seismic vibration using three main pendulum stages equipped with two vertical vibration isolation systems. A compact reaction mass around each of the main stages allows for achieving sufficient damping performance with a simple feedback as well as vibration isolation ratio. Three Type-Bp systems were inst.lled in KAGRA, and were proved to satisfy the requirements on the damping performance, and also on estimated residual displacement of the optics. Copyright © 2019, The Authors. All rights reserved.

关键词： Mirrors

Extracting Semantic Knowledge from Unstructured Text Using Embedded Controlled Language

学校读者我要写书评

暂无评论

Extracting Semantic Knowledge from Unstructured Text Using E...

International Conference on Semantic Computing

作者： Hazem Safwat Normunds Gruzitis Brian Davis Ramona Enache Insight Centre for Data Analytics National University of Ireland Galway Inst. of Mathematics and Computer Science University of Latvia Dept of Computer Science and Engineering University of Gothenburg

ISBN: (纸本)9781509006632

Nowadays, most of the data on the Web is still in the form of unstructured text. Knowledge extraction from unstructured text is highly desirable but extremely challenging due to the inherent ambiguity of natural language. In this article, we present an architecture of an information extraction system based on the concept of Embedded Controlled Language that allows for extracting formal semantic knowledge from an unstructured text corpus. Moreover, the presented approach has a potential to support multilingual input and output.

关键词： Grammar Syntactics Semantics Natural languages Data mining Concrete Conferences

Search for multimessenger signals in NOvA coincident with LIGO/Virgo detections

学校读者我要写书评

暂无评论

Physical Review D 2020年第11期101卷 112006-112006页

作者： M. A. Acero P. Adamson L. Aliaga T. Alion V. Allakhverdian N. Anfimov A. Antoshkin L. Asquith A. Aurisano A. Back C. Backhouse M. Baird N. Balashov P. Baldi B. A. Bambah S. Bashar K. Bays S. Bending R. Bernstein V. Bhatnagar B. Bhuyan J. Bian J. Blair A. C. Booth P. Bour C. Bromberg N. Buchanan A. Butkevich S. Calvez T. J. Carroll E. Catano-Mur S. Childress B. C. Choudhary T. E. Coan M. Colo L. Corwin L. Cremonesi G. S. Davies P. F. Derwent R. Dharmapalan P. Ding Z. Djurcic D. Doyle E. C. Dukes P. Dung H. Duyang S. Edayath R. Ehrlich G. J. Feldman P. Filip W. Flanagan M. J. Frank H. R. Gallagher R. Gandrajula F. Gao S. Germani A. Giri R. A. Gomes M. C. Goodman V. Grichine M. Groh R. Group B. Guo A. Habig F. Hakl J. Hartnell R. Hatcher K. Heller J. Hewes A. Himmel A. Holin J. Huang J. Hylen F. Jediny C. Johnson M. Judah I. Kakorin D. Kalra D. M. Kaplan R. Keloth O. Klimov L. W. Koerner L. Kolupaeva S. Kotelnikov Ch. Kullenberg A. Kumar C. D. Kuruppu V. Kus T. Lackey K. Lang L. Li S. Lin M. Lokajicek S. Luchuk S. Magill W. A. Mann M. L. Marshak M. Martinez-Casales V. Matveev B. Mayes D. P. Méndez M. D. Messier H. Meyer T. Miao W. H. Miller S. R. Mishra A. Mislivec R. Mohanta A. Moren L. Mualem M. Muether S. Mufson K. Mulder R. Murphy J. Musser D. Naples N. Nayak J. K. Nelson R. Nichol E. Niner A. Norman A. Norrick T. Nosek A. Olshevskiy T. Olson J. Paley R. B. Patterson G. Pawloski O. Petrova R. Petti R. K. Plunkett A. Rafique F. Psihas V. Raj B. Rebel P. Rojas V. Ryabov O. Samoylov M. C. Sanchez S. Sánchez Falero P. Shanahan A. Sheshukov P. Singh V. Singh E. Smith J. Smolik P. Snopok N. Solomey A. Sousa K. Soustruznik M. Strait L. Suter A. Sutton R. L. Talaga B. Tapia Oregui P. Tas R. B. Thayyullathil J. Thomas E. Tiras D. Torbunov J. Tripathi Y. Torun J. Urheim P. Vahle J. Vasel P. Vokac T. Vrba M. Wallbank T. K. Warburton M. Wetstein D. Whittington S. G. Wojcicki J. Wolcott A. Yallappa Dombara K. Yonehara S. Yu Y. Yu S. Zadorozhnyy J. Zalesak Y. Zhang R. Zwaska Universidad del Atlantico Carrera 30 Number 8-49 Puerto Colombia Atlantico Colombia Fermi National Accelerator Laboratory Batavia Illinois 60510 USA Department of Physics and Astronomy University of Sussex Falmer Brighton BN1 9QH United Kingdom Joint Institute for Nuclear Research Dubna Moscow region 141980 Russia Department of Physics University of Cincinnati Cincinnati Ohio 45221 USA Department of Physics and Astronomy Iowa State University Ames Iowa 50011 USA Physics and Astronomy Dept. University College London Gower Street London WC1E 6BT United Kingdom Indiana University Bloomington Indiana 47405 USA Department of Physics University of Virginia Charlottesville Virginia 22904 USA Department of Physics and Astronomy University of California at Irvine Irvine California 92697 USA School of Physics University of Hyderabad Hyderabad 500 046 India Department of Physics and Astronomy Tufts University Medford Massachusetts 02155 USA California Institute of Technology Pasadena California 91125 USA Department of Physics Illinois Institute of Technology Chicago Illinois 60616 USA Department of Physics Panjab University Chandigarh 160 014 India Department of Physics IIT Guwahati Guwahati 781 039 India School of Physics and Astronomy University of Minnesota Twin Cities Minneapolis Minnesota 55455 USA Department of Physics University of Houston Houston Texas 77204 USA Czech Technical University in Prague Brehova 7 115 19 Prague 1 Czech Republic Department of Physics and Astronomy Michigan State University East Lansing Michigan 48824 USA Department of Physics Colorado State University Fort Collins Colorado 80523-1875 USA Inst. for Nuclear Research of Russia Academy of Sciences 7a 60th October Anniversary prospect Moscow 117312 Russia Department of Physics University of Texas at Austin Austin Texas 78712 USA Department of Physics University of Wisconsin-Madison Madison Wisconsin 53706 USA Department of Physics William & Mary William

Using the NOvA neutrino detectors, a broad search has been performed for any signal coincident with 28 gravitational wave events detected by the LIGO/Virgo Collaboration between September 2015 and July 2019. For all of these events, NOvA is sensitive to possible arrival of neutrinos and cosmic rays of GeV and higher energies. For five (seven) events in the NOvA Far (Near) Detector, timely public alerts from the LIGO/Virgo Collaboration allowed recording of MeV-scale events. No signal candidates were found.

关键词： Particle astrophysics Neutrinos Neutrino detectors

Topology and Geometry of Gaussian random fields I: on Betti Numbers, Euler characteristic and Minkowski functionals

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Pranav, Pratyush van de Weygaert, Rien Vegter, Gert Jones, Bernard J.T. Adler, Robert J. Feldbrugge, Job Park, Changbom Buchert, Thomas Kerber, Michael Univ Lyon ENS de Lyon Univ Lyon1 CNRS Centre de Recherche Astrophysique de Lyon UMR5574 LyonFV69007 France Kapteyn Astronomical Institute Univ. of Groningen PO Box 800 Groningen9700 AV Netherlands Technion – Israel Institute of Technology Haifa32000 Israel Johann Bernoulli Inst. for Mathematics and Computer Science Univ. of Groningen P.O. Box 407 AK Groningen9700 Netherlands Perimeter Institute for Theoretical Physics University of Waterloo Waterloo Canada Korean Institute of Advanced Studies Hoegiro 87 Dongdaemun-gu Seoul130-722 Korea Republic of Institut für Geometrie TU Graz Kopernikusgasse 24A Graz8010 Austria

This study presents a numerical analysis of the topology of a set of cosmologically interesting three-dimensional Gaussian random fields in terms of their Betti numbers β0, β1 and β2. We show that Betti numbers entail a considerably richer characterization of the topology of the primordial density field. Of particular interest is that Betti numbers specify which topological features - islands, cavities or tunnels - define its spatial structure. A principal characteristic of Gaussian fields is that the three Betti numbers dominate the topology at different density ranges. At extreme density levels, the topology is dominated by a single class of features. At low levels this is a Swiss-cheeselike topology, dominated by isolated cavities, at high levels a predominantly Meatball-like topology of isolated objects. At moderate density levels, two Betti number define a more Sponge-like topology. At mean density, the topology even needs three Betti numbers, quantifying a field consisting of several disconnected complexes, not of one connected and percolating overdensity. A second important aspect of Betti number statistics is that they are sensitive to the power spectrum. It reveals a monotonic trend in which at a moderate density range a lower spectral index corresponds to a considerably higher (relative) population of cavities and islands. We also assess the level of complementary information that Betti numbers represent, in addition to conventional measures such as Minkowski functionals. To this end, we include an extensive description of the Gaussian Kinematic Formula (GKF), which represents a major theoretical underpinning for this discussion. Copyright © 2018, The Authors. All rights reserved.

关键词： Gaussian distribution

Reconstructing gene trees from Fitch's xenology relation

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Geiß, Manuela Anders, John Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. f. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations. Copyright © 2017, The Authors. All rights reserved.

关键词： Clustering algorithms

From event labeled gene trees to species trees

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hernandez-Rosales, Maribel Hellmuth, Marc Wieseke, Nicolas Huber, Katharina T. Moulton, Vincent Stadler, Peter F. Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany School of Computing Sciences University of East Anglia NorwichNR4 7TJ United Kingdom Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Background: Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. Results: We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. Conclusions: The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed. Copyright © 2017, The Authors. All rights reserved.

关键词： Polynomial approximation

Search for multi-messenger signals in NOvA coincident with LIGO/Virgo detections

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Acero, M.A. Adamson, P. Aliaga, L. Alion, T. Allakhverdian, V. Anfimov, N. Antoshkin, A. Asquith, L. Aurisano, A. Back, A. Backhouse, C. Baird, M. Balashov, N. Baldi, P. Bambah, B.A. Bashar, S. Bays, K. Bending, S. Bernstein, R. Bhatnagar, V. Bhuyan, B. Bian, J. Blair, J. Booth, A.C. Bour, P. Bromberg, C. Buchanan, N. Butkevich, A. Calvez, S. Carroll, T.J. Catano-Mur, E. Childress, S. Choudhary, B.C. Coan, T.E. Colo, M. Corwin, L. Cremonesi, L. Davies, G.S. Derwent, P.F. Dharmapalan, R. Ding, P. Djurcic, Z. Doyle, D. Dukes, E.C. Dung, P. Duyang, H. Edayath, S. Ehrlich, R. Feldman, G.J. Filip, P. Flanagan, W. Frank, M.J. Gallagher, H.R. Gandrajula, R. Gao, F. Germani, S. Giri, A. Gomes, R.A. Goodman, M.C. Grichine, V. Groh, M. Group, R. Guo, B. Habig, A. Hakl, F. Hartnell, J. Hatcher, R. Heller, K. Hewes, J. Himmel, A. Holin, A. Huang, J. Hylen, J. Jediny, F. Johnson, C. Judah, M. Kakorin, I. Kalra, D. Kaplan, D.M. Keloth, R. Klimov, O. Koerner, L.W. Kolupaeva, L. Kotelnikov, S. Kullenberg, Ch. Kumar, A. Kuruppu, C.D. Kus, V. Lackey, T. Lang, K. Li, L. Lin, S. Lokajicek, M. Luchuk, S. Magill, S. Mann, W.A. Marshak, M.L. Martinez-Casales, M. Matveev, V. Mayes, B. Méndez, D.P. Messier, M.D. Meyer, H. Miao, T. Miller, W.H. Mishra, S.R. Mislivec, A. Mohanta, R. Moren, A. Mualem, L. Muether, M. Mufson, S. Mulder, K. Murphy, R. Musser, J. Naples, D. Nayak, N. Nelson, J.K. Nichol, R. Niner, E. Norman, A. Norrick, A. Nosek, T. Olshevskiy, A. Olson, T. Paley, J. Patterson, R.B. Pawloski, G. Petrova, O. Petti, R. Plunkett, R.K. Rafique, A. Psihas, F. Raj, V. Rebel, B. Rojas, P. Ryabov, V. Samoylov, O. Sanchez, M.C. Falero, S. Sánchez Shanahan, P. Sheshukov, A. Singh, P. Singh, V. Smith, E. Smolik, J. Snopok, P. Solomey, N. Sousa, A. Soustruznik, K. Strait, Matthew Suter, L. Sutton, A. Talaga, R.L. Oregui, B. Tapia Tas, P. Thayyullathil, R.B. Thomas, J. Tiras, E. Torbunov, D. Tripathi, J. Torun, Y. Argonne National Laboratory ArgonneIL60439 United States Universidad del Atlantico Carrera 30 No. 8-49 Puerto Colombia Atlantico Colombia Department of Physics Institute of Science Banaras Hindu University Varanasi221 005 India California Institute of Technology PasadenaCA91125 United States Charles University Faculty of Mathematics and Physics Institute of Particle and Nuclear Physics Prague Czech Republic Department of Physics University of Cincinnati CincinnatiOH45221 United States Department of Physics Cochin University of Science and Technology Kochi682 022 India Department of Physics Colorado State University Fort CollinsCO80523-1875 United States Czech Technical University in Prague Brehova 7 Prague 1115 19 Czech Republic University of Dallas 1845 E Northgate Drive IrvingTX75062 United States Department of Physics and Astrophysics University of Delhi Delhi110007 India Fermi National Accelerator Laboratory BataviaIL60510 United States Instituto de Física Universidade Federal de Goiás Goiânia Goiás74690-900 Brazil Department of Physics IIT Guwahati Guwahati781 039 India Department of Physics Harvard University CambridgeMA02138 United States Department of Physics University of Houston HoustonTX77204 United States School of Physics University of Hyderabad Hyderabad500 046 India Department of Physics IIT Hyderabad Hyderabad502 205 India Department of Physics Illinois Institute of Technology ChicagoIL60616 United States Indiana University BloomingtonIN47405 United States Institute of Computer Science Czech Academy of Sciences Prague182 07 Czech Republic Inst. for Nuclear Research of Russia Academy of Sciences 7a 60th October Anniversary prospect Moscow117312 Russia Institute of Physics Czech Academy of Sciences Prague182 21 Czech Republic Department of Physics and Astronomy Iowa State University AmesIA50011 United States Department of Physics and Astronomy University of California at Irvine IrvineCA9269

关键词： Germanium alloys

Characterizing the Computational Power of Anonymous Mobile Robots

学校读者我要写书评

暂无评论

Characterizing the Computational Power of Anonymous Mobile R...

International Conference on Distributed Computing Systems

作者： Mattia D'Emidio Daniele Frigioni Alfredo Navarra Gran Sasso Sci. Inst. (GSSI) L'Aquila Italy Computer Science and Mathematics University of L'Aquila L'Aquila Italy University of Perugia Perugia Italy

The distributed setting of computational mobile entities, called robots, thathave to perform tasks without global coordination has been extensively studied in the literature. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires asnapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Computephase), and finally moves toward a desired destination, if any (Movephase). Look-Compute-Move cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for theactivation and synchronization of mobile robots are the well-known fully-synchronous, semi-synchronous, and asynchronous models. A first comprehensive evaluation of the computational power of robots operating in the LCM model and moving within the Euclidean plane, under different levels of synchronization, has been proposed in [Das et al., Int.'l Conf. on Distributed Computing Systems, 2012]. In detail, the authors provide a series of results that prove relations between classic models and variations of them, which consider the possibility that robots are endowed with a visible light, i.e. they are luminous, or with the capability to store some past snapshots, or combinations of them. In this paper, we are interested in similar settings but for robots moving on graphs. In particular, we propose a characterization of the computational power of mobile robots on graphs as follows. First, we show the relations among the three classic activation and synchronization models. Second, we compare the models where robots are endowed with lights against.the models without lights. Third, we highlight the relations among the different models concerning luminous robots. Finally, we provide a detailed comparison of the proposed results with the case of robots moving in the Euclidean plane.

关键词： Computational modeling Robot kinematics Robot sensing systems Synchronization Color Mobile robots