Search

Showing total 4 results
Start Over Search Limiters Peer Reviewed Topic topology
4 results

1. Algebraic and topological structures on rational tangles

Author

Seyed M.H. Mansourbeigi, Vida Milani, Hossein Finizadeh, and Poli Paper

Subjects
tangle convergent, Coalgebra, Structure (category theory), Bi-pseudo-module, 010103 numerical & computational mathematics, Interval (mathematics), lcsh:Analysis, Group Hopf algebra, Continued fraction, Topology, 01 natural sciences, Tangle, Interval coalgebra, Incidence algebra, Mathematics::Quantum Algebra, Physical Sciences and Mathematics, Order (group theory), 0101 mathematics, Algebraic number, Mathematics, group Hopf algebra, Computer Sciences, lcsh:Mathematics, lcsh:QA299.6-433, Tangle convergen, bi-pseudo-module, lcsh:QA1-939, Mathematics::Geometric Topology, continued fraction, 010101 applied mathematics, Algebra, incidence algebra, pseudo-tensor product, Pseudo-tensor product, Pseudo-module, pseudo-module, Geometry and Topology, tangle, Locally finite partial order, locally finite partial order, interval coalgebra
Abstract

In this paper we present the construction of a group Hopf algebra on the class of rational tangles. A locally finite partial order on this class is introduced and a topology is generated. An interval coalgebra structure associated with the locally finite partial order is specified. Irrational and real tangles are introduced and their relation with rational tangles are studied. The existence of the maximal real tangle is described in detail.

Published
2017

2. Minimal NMR distance information for rigidity of protein graphs

Author

Leo Liberti, Benjamin Bardiaux, Michael Nilges, Thérèse E. Malliavin, Bradley Worley, Bruce R. Donald, Carlile Lavor, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Duke University [Durham], Bioinformatique structurale, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), C.L. would like to thank the Brazilian research agencies CNPq, FAPESP and B.D. would like to thank the NIH grants R01 GM-118543 and R01 GM-078031 for their financial support., We are also thankful to Angela Gronenborn and Michael Souza, for discussions that clarify some ideas in the paper, and to anonymous referees that made very important comments to this work., Bioinformatique structurale - Structural Bioinformatics, Universidade Estadual de Campinas = University of Campinas (UNICAMP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computational complexity theory, Nuclear Magnetic Resonance, 0211 other engineering and technologies, Structure (category theory), Rigidity (psychology), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Topology, 01 natural sciences, Article, Cardinality, Protein structure, Distance Geometry, Discrete Mathematics and Combinatorics, Molecule, Combinatorial search, Mathematics, Quantitative Biology::Biomolecules, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM], Applied Mathematics, Solution set, 021107 urban & regional planning, [SDV.BBM.BP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biophysics, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM], Vertex orders, 010201 computation theory & mathematics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular structure
Abstract

International audience; Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.

Published
2019

3. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles

Author

Paola Flocchini, David Ilcinkas, Nicola Santoro, School of Electrical Engineering and Computer Science (EECS), University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Ottawa], Carleton University, See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
Theoretical computer science, General Computer Science, FIFO (computing and electronics), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Topology (electrical circuits), 0102 computer and information sciences, 02 engineering and technology, Dangerous graphs, Topology, 01 natural sciences, Graph exploration, Autonomous robots, 0202 electrical engineering, electronic engineering, information engineering, Search problem, Pebble, Mathematics, Applied Mathematics, Black hole search, Distributed computing, Computer Science Applications, 010201 computation theory & mathematics, Asynchronous communication, Theory of computation, 020201 artificial intelligence & image processing, Node (circuits), Mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles.

Published
2012

4. True-Randomness and Pseudo-Randomness in Ring Oscillator-Based True Random Number Generators

Author

Nathalie Bochard, Florent Bernard, Viktor Fischer, Boyan Valtchanov, Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), This paper was partially supported by the Rhone-Alpes Region and Saint-Etienne Metropole, France, and Systèmes sur puces reconfigurables pour la sécurisation de données, SecReSoC, ANR-09-SEGI-013 Programme ARPEGE 2009,Systèmes sur puces reconfigurables pour la sécurisation de données, SecReSoC, ANR-09-SEGI-013 Programme ARPEGE 2009

Subjects
Clock Jitter, lcsh:Computer engineering. Computer hardware, Article Subject, Random number generation, Computer science, True Random Number Generators, Randomness Tests, Pseudo randomness, 020208 electrical & electronic engineering, lcsh:TK7885-7895, 02 engineering and technology, Ring oscillator, Topology, Ring Oscillators, [SPI.TRON]Engineering Sciences [physics]/Electronics, 020202 computer hardware & architecture, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, Entropy (information theory), [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Entropy reduction, FPGA, Randomness, Statistical hypothesis testing
Abstract

12 pages; International audience; The paper deals with true random number generators employing oscillator rings, namely, with the one proposed by Sunar et al. in 2007 and enhanced by Wold and Tan in 2009. Our mathematical analysis shows that both architectures behave identically when composed of the same number of rings and ideal logic components. However, the reduction of the number of rings, as proposed by Wold and Tan, would inevitably cause the loss of entropy. Unfortunately, this entropy insufficiency is masked by the pseudo-randomness caused by XOR-ing clock signals having different frequencies. Our simulation model shows that the generator, using more than 18 ideal jitter-free rings having slightly different frequencies and producing only pseudo-randomness, will let the statistical tests pass. We conclude that a smaller number of rings reduce the security if the entropy reduction is not taken into account in post-processing.Moreover, the designer cannot avoid that some of rings will have the same frequency, which will cause another loss of entropy. In order to confirmthis, we show how the attacker can reach a state where over 25% of the rings are locked and thus completely dependent. This effect can have disastrous consequences on the system security.

Published
2010