Log in

Relevant bibliographies by topics / Indices de De Bruijn / Journal articles

To see the other types of publications on this topic, follow the link: Indices de De Bruijn.

Journal articles on the topic 'Indices de De Bruijn'

Author: Grafiati

Published: 4 June 2021

Last updated: 18 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Indices de De Bruijn.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Bonelli, Eduardo, Delia Kesner, and Alejandro Rios. "de Bruijn Indices for Metaterms." Journal of Logic and Computation 15, no. 6 (December 1, 2005): 855–99. http://dx.doi.org/10.1093/logcom/exi051.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Kamareddine, F. "Pure Type Systems with de Bruijn Indices." Computer Journal 45, no. 2 (February 1, 2002): 187–201. http://dx.doi.org/10.1093/comjnl/45.2.187.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

KAMAREDDINE, FAIROUZ. "THE SOUNDNESS OF EXPLICIT SUBSTITUTION WITH NAMELESS VARIABLES." International Journal of Foundations of Computer Science 09, no. 03 (September 1998): 321–49. http://dx.doi.org/10.1142/s0129054198000210.

Full text

Abstract:

We show the soundness of a λ-calculus ℬ where de Bruijn indices are used, substitution is explicit, and reduction is step-wise. This is done by interpreting ℬ in the classical calculus where the explicit substitution becomes implicit and de Bruijn indices become named variables. This is the first flat semantics of explicit substitution and step-wise reduction and the first clear account of exactly when α-reduction is needed.

APA, Harvard, Vancouver, ISO, and other styles

4

DI COSMO, ROBERTO, DELIA KESNER, and EMMANUEL POLONOVSKI. "Proof nets and explicit substitutions." Mathematical Structures in Computer Science 13, no. 3 (May 20, 2003): 409–50. http://dx.doi.org/10.1017/s0960129502003791.

Full text

Abstract:

We refine the simulation technique introduced in Di Cosmo and Kesner (1997) to show strong normalisation of $\l$-calculi with explicit substitutions via termination of cut elimination in proof nets (Girard 1987). We first propose a notion of equivalence relation for proof nets that extends the one in Di Cosmo and Guerrini (1999), and show that cut elimination modulo this equivalence relation is terminating. We then show strong normalisation of the typed version of the $\ll$-calculus with de Bruijn indices (a calculus with full composition defined in David and Guillaume (1999)) using a translation from typed $\ll$ to proof nets. Finally, we propose a version of typed $\ll$ with named variables, which helps to give a better understanding of the complex mechanism of the explicit weakening notation introduced in the $\ll$-calculus with de Bruijn indices (David and Guillaume 1999).

APA, Harvard, Vancouver, ISO, and other styles

5

POUILLARD, NICOLAS, and FRANÇOIS POTTIER. "A unified treatment of syntax with binders." Journal of Functional Programming 22, no. 4-5 (August 15, 2012): 614–704. http://dx.doi.org/10.1017/s0956796812000251.

Full text

Abstract:

AbstractAtoms and de Bruijn indices are two well-known representation techniques for data structures that involve names and binders. However, using either technique, it is all too easy to make a programming error that causes one name to be used where another was intended. We propose an abstract interface to names and binders that rules out many of these errors. This interface is implemented as a library in Agda. It allows defining and manipulating term representations in nominal style and in de Bruijn style. The programmer is not forced to choose between these styles: on the contrary, the library allows using both styles in the same program, if desired. Whereas indexing the types of names and terms with a natural number is a well-known technique to better control the use of de Bruijn indices, we index types with worlds. Worlds are at the same time more precise and more abstract than natural numbers. Via logical relations and parametricity, we are able to demonstrate in what sense our library is safe, and to obtain theorems for free about world-polymorphic functions. For instance, we prove that a world-polymorphic term transformation function must commute with any renaming of the free variables. The proof is entirely carried out in Agda.

APA, Harvard, Vancouver, ISO, and other styles

6

Ventura, D. L., F. Kamareddine, and M. Ayala-Rincon. "Explicit substitution calculi with de Bruijn indices and intersection type systems." Logic Journal of IGPL 23, no. 2 (December 30, 2014): 295–340. http://dx.doi.org/10.1093/jigpal/jzu044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kamareddine, F. "Bridging de Bruijn indices and variable names in explicit substitutions calculi." Logic Journal of IGPL 6, no. 6 (November 1, 1998): 843–74. http://dx.doi.org/10.1093/jigpal/6.6.843.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Vouillon, Jérôme. "A Solution to the PoplMark Challenge Based on de Bruijn Indices." Journal of Automated Reasoning 49, no. 3 (June 4, 2011): 327–62. http://dx.doi.org/10.1007/s10817-011-9230-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Berghofer, Stefan, and Christian Urban. "A Head-to-Head Comparison of de Bruijn Indices and Names." Electronic Notes in Theoretical Computer Science 174, no. 5 (June 2007): 53–67. http://dx.doi.org/10.1016/j.entcs.2007.01.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Berghofer, Stefan. "A Solution to the PoplMark Challenge Using de Bruijn Indices in Isabelle/HOL." Journal of Automated Reasoning 49, no. 3 (June 23, 2011): 303–26. http://dx.doi.org/10.1007/s10817-011-9231-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Khan, Jamshed, and Rob Patro. "Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections." Bioinformatics 37, Supplement_1 (July 1, 2021): i177—i186. http://dx.doi.org/10.1093/bioinformatics/btab309.

Full text

Abstract:

Abstract Motivation The construction of the compacted de Bruijn graph from collections of reference genomes is a task of increasing interest in genomic analyses. These graphs are increasingly used as sequence indices for short- and long-read alignment. Also, as we sequence and assemble a greater diversity of genomes, the colored compacted de Bruijn graph is being used more and more as the basis for efficient methods to perform comparative genomic analyses on these genomes. Therefore, time- and memory-efficient construction of the graph from reference sequences is an important problem. Results We introduce a new algorithm, implemented in the tool Cuttlefish, to construct the (colored) compacted de Bruijn graph from a collection of one or more genome references. Cuttlefish introduces a novel approach of modeling de Bruijn graph vertices as finite-state automata, and constrains these automata’s state-space to enable tracking their transitioning states with very low memory usage. Cuttlefish is also fast and highly parallelizable. Experimental results demonstrate that it scales much better than existing approaches, especially as the number and the scale of the input references grow. On a typical shared-memory machine, Cuttlefish constructed the graph for 100 human genomes in under 9 h, using ∼29 GB of memory. On 11 diverse conifer plant genomes, the compacted graph was constructed by Cuttlefish in under 9 h, using ∼84 GB of memory. The only other tool completing these tasks on the hardware took over 23 h using ∼126 GB of memory, and over 16 h using ∼289 GB of memory, respectively. Availability and implementation Cuttlefish is implemented in C++14, and is available under an open source license at https://github.com/COMBINE-lab/cuttlefish. Supplementary information Supplementary data are available at Bioinformatics online.

APA, Harvard, Vancouver, ISO, and other styles

12

DAVID, RENÉ, and BRUNO GUILLAUME. "A λ-calculus with explicit weakening and explicit substitution." Mathematical Structures in Computer Science 11, no. 1 (February 2001): 169–206. http://dx.doi.org/10.1017/s0960129500003224.

Full text

Abstract:

Since Melliès showed that λσ (a calculus of explicit substitutions) does not preserve the strong normalization of the β-reduction, it has become a challenge to find a calculus satisfying the following properties: step-by-step simulation of the β-reduction, confluence on terms with metavariables, strong normalization of the calculus of substitutions and preservation of the strong normalization of the λ-calculus. We present here such a calculus. The main novelty of this calculus (given with de Bruijn indices) is the use of labels that represent updating functions and correspond to explicit weakening. A typed version is also presented.

APA, Harvard, Vancouver, ISO, and other styles

13

Ventura, Daniel, Mauricio Ayala-Rincón, and Fairouz Kamareddine. "Principal Typings in a Restricted Intersection Type System for Beta Normal Forms with De Bruijn Indices." Electronic Proceedings in Theoretical Computer Science 15 (January 26, 2010): 69–82. http://dx.doi.org/10.4204/eptcs.15.6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

van Noord, Rik, Lasha Abzianidze, Antonio Toral, and Johan Bos. "Exploring Neural Methods for Parsing Discourse Representation Structures." Transactions of the Association for Computational Linguistics 6 (December 2018): 619–33. http://dx.doi.org/10.1162/tacl_a_00241.

Full text

Abstract:

Neural methods have had several recent successes in semantic parsing, though they have yet to face the challenge of producing meaning representations based on formal semantics. We present a sequence-to-sequence neural semantic parser that is able to produce Discourse Representation Structures (DRSs) for English sentences with high accuracy, outperforming traditional DRS parsers. To facilitate the learning of the output, we represent DRSs as a sequence of flat clauses and introduce a method to verify that produced DRSs are well-formed and interpretable. We compare models using characters and words as input and see (somewhat surprisingly) that the former performs better than the latter. We show that eliminating variable names from the output using De Bruijn indices increases parser performance. Adding silver training data boosts performance even further.

APA, Harvard, Vancouver, ISO, and other styles

15

GRYGIEL, KATARZYNA, and PIERRE LESCANNE. "Counting and generating lambda terms." Journal of Functional Programming 23, no. 5 (September 2013): 594–628. http://dx.doi.org/10.1017/s0956796813000178.

Full text

Abstract:

AbstractLambda calculus is the basis of functional programming and higher order proof assistants. However, little is known about combinatorial properties of lambda terms, in particular, about their asymptotic distribution and random generation. This paper tries to answer questions like: How many terms of a given size are there? What is a ‘typical’ structure of a simply typable term? Despite their ostensible simplicity, these questions still remain unanswered, whereas solutions to such problems are essential for testing compilers and optimizing programs whose expected efficiency depends on the size of terms. Our approach toward the aforementioned problems may be later extended to any language with bound variables, i.e., with scopes and declarations. This paper presents two complementary approaches: one, theoretical, uses complex analysis and generating functions, the other, experimental, is based on a generator of lambda terms. Thanks to de Bruijn indices (de Bruijn, N. (1972) Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagat. Math.34(5), 381–392), we provide three families of formulas for the number of closed lambda terms of a given size and we give four relations between these numbers which have interesting combinatorial interpretations. As a by-product of the counting formulas, we design an algorithm for generating λ-terms. Performed tests provide us with experimental data, like the average depth of bound variables and the average number of head lambdas. We also create random generators for various sorts of terms. Thereafter, we conduct experiments that answer questions like: What is the ratio of simply typable terms among all terms? (Very small!) How are simply typable lambda terms distributed among all lambda terms? (A typable term almost always starts with an abstraction.) In this paper, abstractions and applications have size 1 and variables have size 0.

APA, Harvard, Vancouver, ISO, and other styles

16

PERERA, ROLY, and JAMES CHENEY. "Proof-relevant π-calculus: a constructive account of concurrency and causality." Mathematical Structures in Computer Science 28, no. 9 (May 4, 2017): 1541–77. http://dx.doi.org/10.1017/s096012951700010x.

Full text

Abstract:

We present a formalisation in Agda of the theory of concurrent transitions, residuation and causal equivalence of traces for the π-calculus. Our formalisation employs de Bruijn indices and dependently typed syntax, and aligns the ‘proved transitions’ proposed by Boudol and Castellani in the context of CCS with the proof terms naturally present in Agda's representation of the labelled transition relation. Our main contributions are proofs of the ‘diamond lemma’ for the residuals of concurrent transitions and a formal definition of equivalence of traces up to permutation of transitions.In the π-calculus, transitions represent propagating binders whenever their actions involve bound names. To accommodate these cases, we require a more general diamond lemma where the target states of equivalent traces are no longer identical, but are related by abraidingthat rewires the bound and free names to reflect the particular interleaving of events involving binders. Our approach may be useful for modelling concurrency in other languages where transitions carry meta-data sensitive to particular interleavings, such as dynamically allocated memory addresses.

APA, Harvard, Vancouver, ISO, and other styles

17

VESTERGAARD, RENÉ, and JOE WELLS. "Cut rules and explicit substitutions." Mathematical Structures in Computer Science 11, no. 1 (February 2001): 131–68. http://dx.doi.org/10.1017/s0960129500003273.

Full text

Abstract:

We introduce a method to associate calculi of proof terms and rewrite rules with cut elimination procedures for logical deduction systems (i.e., Gentzen-style sequent calculi) in the case of intuitionistic logic. We illustrate this method using two different versions of the cut rule for a variant of the intuitionistic fragment of Kleene's logical deduction system G3.Our systems are in fact calculi of explicit substitution, where the cut rule introduces an explicit substitution and the left-→ rule introduces a binding of the result of a function application. Cut propagation steps of cut elimination correspond to propagation of explicit substitutions, and propagation of weakening (to eliminate it) corresponds to propagation of index-updating operations. We prove various subject reduction, termination, and confluence properties for our calculi.Our calculi improve on some earlier calculi for logical deduction systems in a number of ways. By using de Bruijn indices, our calculi qualify as first-order term rewriting systems (TRS's), allowing us to use correctly certain results for TRS's about termination. Unlike in some other calculi, each of our calculi has only one cut rule and we do not need unusual features of sequents.We show that the substitution and index-updating mechanisms of our calculi work the same way as the substitution and index-updating mechanisms of Kamareddine and Ríos' λs and λt, two well-known systems of explicit substitution for the standard λ-calculus. By a change in the format of sequents, we obtain similar results for a known λ-calculus with variables and explicit substitutions, Rose's λbxgc.

APA, Harvard, Vancouver, ISO, and other styles

18

Goldberg, V., and Ch Bernhofer. "Quantifying the coupling degree between land surface and the atmospheric boundary layer with the coupled vegetation-atmosphere model HIRVAC." Annales Geophysicae 19, no. 5 (May 31, 2001): 581–87. http://dx.doi.org/10.5194/angeo-19-581-2001.

Full text

Abstract:

Abstract. In the present study, the ability of different indices to quantify the coupling degree between a vegetated surface and the atmospheric boundary layer is tested. For this purpose, a one-and-a-half dimensional atmospheric boundary layer model, including a high resolved vegetation canopy, was applied (HIRVAC) and indices, such as the decoupling factor Ω, as well as other measures derived from model out-put were used. The aim of the study was to show that the quite complex coupling and feedback mechanisms can be described with these relatively simple measures. Model results illustrate that the vegetation and the atmosphere are well coupled (expressed by a lower Ω) under conditions of a tall and dense canopy, as well as under strong dynamic forcing. This better aerodynamic coupling leads to an increase in evapotranspiration, as well as an increase in the evaporative fraction. This fact was also shown by the second coupling measure: the relative changes in daily model evapotranspiration. This measure was inspired by the assumption that these changes are primarily dependent on the coupling degree between the surface and the atmosphere, if the other boundary conditions in the model are fixed. A third sensitivity measure was used according to Jacobs and de Bruin (1992). It shows that the sensitivity of evaporative fraction to stomata resistance is much higher with a better aerodynamic coupling. The results of the factor Ω; are in a good agreement with the findings of Jacobs and de Bruin: they stress that it is a valuable strategy to group vegetation into two simple categories (smooth and rough) for the understanding of vegetation-atmosphere coupling.Key words. Atmospheric composition and structure (biosphere- atmosphere interactions) – Hydrology (evapotranspiration; hydroclimatology)

APA, Harvard, Vancouver, ISO, and other styles

19

ASPERTI, ANDREA, and JEREMY AVIGAD. "Zen and the art of formalisation." Mathematical Structures in Computer Science 21, no. 4 (July 1, 2011): 679–82. http://dx.doi.org/10.1017/s0960129511000065.

Full text

Abstract:

N. G. de Bruijn, now professor emeritus of the Eindhoven University of Technology, was a pioneer in the field of interactive theorem proving. From 1967 to the end of the 1970's, his work on the Automath system introduced the architecture that is common to most of today's proof assistants, and much of the basic technology. But de Bruijn was a mathematician first and foremost, as evidenced by the many mathematical notions and results that bear his name, among them de Bruijn sequences, de Bruijn graphs, the de Bruijn–Newman constant, and the de Bruijn–Erdös theorem. The quotation above is thus interesting not because it is a reflection on his expertise in formal verification, but, rather, of his convictions as a working mathematician.

APA, Harvard, Vancouver, ISO, and other styles

20

KARI, LILA, and ZHI XU. "DE BRUIJN SEQUENCES REVISITED." International Journal of Foundations of Computer Science 23, no. 06 (September 2012): 1307–21. http://dx.doi.org/10.1142/s0129054112400540.

Full text

Abstract:

A (non-circular) de Bruijn sequence w of order n is a word such that every word of length n appears exactly once in w as a factor. In this paper, we generalize the concept to different settings: the multi-shift de Bruijn sequence and the pseudo de Bruijn sequence. An m-shift de Bruijn sequence of order n is a word such that every word of length n appears exactly once in w as a factor that starts at a position im + 1 for some integer i ≥ 0. A pseudo de Bruijn sequence of order n with respect to an antimorphic involution θ is a word such that for every word u of length n the total number of appearances of u and θ(u) as a factor is one. We show that the number of m-shift de Bruijn sequences of order n is an!a(m-n)(an-1) for 1 ≤ n ≤ m and is (am!)an-m for 1 ≤ m ≤ n, where a is the size of the alphabet. We provide two algorithms for generating a multi-shift de Bruijn sequence. The multi-shift de Bruijn sequence is important for solving the Frobenius problem in a free monoid. We show that the existence of pseudo de Bruijn sequences depends on the given alphabet and antimorphic involution, and obtain formulas for the number of such sequences in some particular settings.

APA, Harvard, Vancouver, ISO, and other styles

21

Moreno, Eduardo. "De Bruijn sequences and De Bruijn graphs for a general language." Information Processing Letters 96, no. 6 (December 2005): 214–19. http://dx.doi.org/10.1016/j.ipl.2005.05.028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Tesler, Glenn. "Multi de Bruijn sequences." Journal of Combinatorics 8, no. 3 (2017): 439–74. http://dx.doi.org/10.4310/joc.2017.v8.n3.a3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Du, D. Z., and F. K. Hwang. "Generalized de Bruijn digraphs." Networks 18, no. 1 (1988): 27–38. http://dx.doi.org/10.1002/net.3230180105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Malyshev, F. M., and V. E. Tarakanov. "Generalized de Bruijn graphs." Mathematical Notes 62, no. 4 (October 1997): 449–56. http://dx.doi.org/10.1007/bf02358978.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Cooper, Joshua N., and Ronald L. Graham. "Generalized de Bruijn Cycles." Annals of Combinatorics 8, no. 1 (May 2004): 13–25. http://dx.doi.org/10.1007/s00026-004-0201-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Alhakim, Abbas, and Maher Nouiehed. "Stretching de Bruijn sequences." Designs, Codes and Cryptography 85, no. 2 (December 1, 2016): 381–94. http://dx.doi.org/10.1007/s10623-016-0314-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Lin, Yu, Jeffrey Yuan, Mikhail Kolmogorov, Max W. Shen, Mark Chaisson, and Pavel A. Pevzner. "Assembly of long error-prone reads using de Bruijn graphs." Proceedings of the National Academy of Sciences 113, no. 52 (December 12, 2016): E8396—E8405. http://dx.doi.org/10.1073/pnas.1604560113.

Full text

Abstract:

The recent breakthroughs in assembling long error-prone reads were based on the overlap-layout-consensus (OLC) approach and did not utilize the strengths of the alternative de Bruijn graph approach to genome assembly. Moreover, these studies often assume that applications of the de Bruijn graph approach are limited to short and accurate reads and that the OLC approach is the only practical paradigm for assembling long error-prone reads. We show how to generalize de Bruijn graphs for assembling long error-prone reads and describe the ABruijn assembler, which combines the de Bruijn graph and the OLC approaches and results in accurate genome reconstructions.

APA, Harvard, Vancouver, ISO, and other styles

28

REHIDA, P., and I. KOMISAROV. "COMPARISON OF PLANNING RESULTS USING BUBBLE SCHEDULING AND ALLOCATION (BSA) ALGORITHM FOR DIFFERENT TOPOLOGIES." HERALD OF KHMELNYTSKYI NATIONAL UNIVERSITY 295, no. 2 (May 2021): 89–96. http://dx.doi.org/10.31891/2307-5732-2021-295-2-89-96.

Full text

Abstract:

In this article, the bubble scheduling and allocation algorithm is considered for different types of topologies: grid, hypercube, de Bruijn topology, extended de Bruijn topology based on ternary code. Static planning algorithms are analyzed; the results are presented in the form of a comparative table on the criteria of complexity, the need to find a critical path, the presence of a table of routing and efficiency. The study of the method of planning calculations is carried out based on the problem of finding the roots of systems of linear and nonlinear equations using Cramer’s and Newton’s methods. The corresponding graphs of tier-parallel form are synthesized for these methods. The principles of synthesis for 4 types of topologies are shown. The synthesis of the grid, hypercube, and de Bruijn graph is considered in the classical form. The synthesis of the extended de Bruijn topology is a synthesis of de Bruijn topology [1, 2] using a ternary code. That is, with the same number of processors, the number of connections increases. Experimental studies of the scheduling of the obtained graphs in the synthesized topologies using the method of bubble scheduling and allocation are conducted; the results of scheduling are presented for these topologies. The best results were shown by extended de Bruijn topology based on ternary code due to the increased degree of units, which is especially noticeable for Newton’s method where there are much more data transfers than in Cramer’s method. The topology of a hypercube and de Bruijn topology demonstrated just about same results but hypercube topology did a little better. In addition to this, having a smaller diameter and cost, the hypercube is the most optimal topology and still used today. However, when constructing fail-safe topological organizations, it is better to use topologies based on ternary code, such as the topology based on the extended de Bruijn graph.

APA, Harvard, Vancouver, ISO, and other styles

29

BARTH, D. "EMBEDDING MESHES OF d-ARY TREES INTO DE BRUIJN GRAPHS." Parallel Processing Letters 03, no. 02 (June 1993): 115–27. http://dx.doi.org/10.1142/s0129626493000150.

Full text

Abstract:

We present an embedding of the mesh of d-ary trees, a graph we introduce here, into de Bruijn graphs, which are good topologies for parallel architectures, with an optimal expansion and constant dilation and congestion. We show how to embed several disjoint meshes of d-ary trees in the same de Bruijn graph. It gives some results about emulation of the meshes of d-ary trees by the de Bruijn network.

APA, Harvard, Vancouver, ISO, and other styles

30

Wang, Zhongxiao, Xiangyu Wang, and Tian Tian. "Constructing de Bruijn Sequences Based on a New Necessary Condition." International Journal of Foundations of Computer Science 31, no. 03 (April 2020): 301–12. http://dx.doi.org/10.1142/s0129054120500094.

Full text

Abstract:

In this paper, we propose a new necessary condition for feedback functions of de Bruijn sequences and discuss its application in constructing de Bruijn sequences. It is shown that a large number of de Bruijn sequences could be easily constructed by precomputing an [Formula: see text]-stage nonlinear feedback shift register (NFSR) with a special cycle structure—that is, if a state [Formula: see text] is on a cycle generated by this NFSR, then all the states with the same Hamming weight as [Formula: see text] are also on this cycle. Moreover, if there are [Formula: see text] different cycles in the state graph of the precomputed NFSR, then we can construct [Formula: see text] de Bruijn sequences by the different choices of conjugate state pairs, where [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

31

Gossner, Olivier, and Penélope Hernández. "Coordination through De Bruijn sequences." Operations Research Letters 34, no. 1 (January 2006): 17–21. http://dx.doi.org/10.1016/j.orl.2005.01.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Samatham, M. R., and D. K. Pradhan. "The de Bruijn multiprocessor network." ACM SIGARCH Computer Architecture News 13, no. 3 (June 1985): 360–67. http://dx.doi.org/10.1145/327070.327369.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Blanchet-Sadri, F., and Sinziana Munteanu. "Computing generalized de Bruijn sequences." Theoretical Computer Science 704 (December 2017): 42–61. http://dx.doi.org/10.1016/j.tcs.2017.09.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Crawford, Victoria G., Alan Kuhnle, Christina Boucher, Rayan Chikhi, and Travis Gagie. "Practical dynamic de Bruijn graphs." Bioinformatics 34, no. 24 (June 22, 2018): 4189–95. http://dx.doi.org/10.1093/bioinformatics/bty500.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Bhattacharya, Prabir. "Decomposition of de bruijn graphs." International Journal of Computer Mathematics 33, no. 1-2 (January 1990): 71–75. http://dx.doi.org/10.1080/00207169008803837.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Muggli, Martin D., Alexander Bowe, Noelle R. Noyes, Paul S. Morley, Keith E. Belk, Robert Raymond, Travis Gagie, Simon J. Puglisi, and Christina Boucher. "Succinct colored de Bruijn graphs." Bioinformatics 33, no. 20 (February 14, 2017): 3181–87. http://dx.doi.org/10.1093/bioinformatics/btx067.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Yan, G., Z. Q. Fu, and G. Chen. "Consensus on de Bruijn graphs." European Physical Journal B 63, no. 4 (June 2008): 515–20. http://dx.doi.org/10.1140/epjb/e2008-00258-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Bryant, Roy D., and Harold Fredricksen. "Covering the de Bruijn graph." Discrete Mathematics 89, no. 2 (May 1991): 133–48. http://dx.doi.org/10.1016/0012-365x(91)90362-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Golomb, Solomon W. "“Periods” of de Bruijn sequences." Advances in Applied Mathematics 13, no. 2 (June 1992): 152–59. http://dx.doi.org/10.1016/0196-8858(92)90007-j.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Xie, Shenquan. "Notes on de Bruijn sequences." Discrete Applied Mathematics 16, no. 2 (February 1987): 157–77. http://dx.doi.org/10.1016/0166-218x(87)90072-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Becher, Verónica, and Pablo Ariel Heiber. "On extending de Bruijn sequences." Information Processing Letters 111, no. 18 (September 2011): 930–32. http://dx.doi.org/10.1016/j.ipl.2011.06.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Barth, Dominique, and Marie-Claude Heydemann. "A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs." Discrete Applied Mathematics 77, no. 2 (August 1997): 99–118. http://dx.doi.org/10.1016/s0166-218x(96)00130-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Barth, Dominique, and Marie-Claude Heydemann. "A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs." Discrete Applied Mathematics 80, no. 1 (December 1997): 115. http://dx.doi.org/10.1016/s0166-218x(97)80387-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

SRINIVAS, S., K. THULASIRAMAN, and M. N. S. SWAMY. "AN MIN-BASED ARCHITECTURE FOR RECONFIGURABLE DE BRUIJN STRUCTURES." International Journal of High Speed Electronics and Systems 03, no. 03n04 (September 1992): 279–96. http://dx.doi.org/10.1142/s0129156492000114.

Full text

Abstract:

This paper presents a novel parallel architecture based on a multistage interconnection network (MIN) for reconfigurable binary de Bruijn structures. The proposed architecture is able to assume distinct binary de Bruijn configurations (BDCs), where each configuration has the geometric pattern or structure as that of a binary de Bruijn graph. A system with N nodes or processing elements can generate N2/4 distinct BDCs. The novelty of the architecture is in the design of the switching network for interconnecting the nodes. The switching network adopted is an augmented shuffle-exchange MIN. The favorable features of the architecture include fast reconfiguration, simplified hardware in the MIN, absence of the need for reconfiguration hardware in the nodes, and simple routine control. The generation of BDCs is derived from an equation, called the Reconfiguration Equation, which is based on simple logical operations and defines the necessary interconnections among the nodes. It is shown that the architecture assumes interconnections according to this equation and consequently the proof of reconfiguration is given. The important properties of the reconfigurable de Bruijn structure are outlined. Finally, two features which are useful in enhancing the reconfigurability of the architecture are discussed. First, it is proved that the architecture can be augmented to generate partitioned de Bruijn configurations. Second, it is shown that the architecture can assume distinct binary tree configurations by a simple modification.

APA, Harvard, Vancouver, ISO, and other styles

45

Muggli, Martin D., Bahar Alipanahi, and Christina Boucher. "Building large updatable colored de Bruijn graphs via merging." Bioinformatics 35, no. 14 (July 2019): i51—i60. http://dx.doi.org/10.1093/bioinformatics/btz350.

Full text

Abstract:

Abstract Motivation There exist several large genomic and metagenomic data collection efforts, including GenomeTrakr and MetaSub, which are routinely updated with new data. To analyze such datasets, memory-efficient methods to construct and store the colored de Bruijn graph were developed. Yet, a problem that has not been considered is constructing the colored de Bruijn graph in a scalable manner that allows new data to be added without reconstruction. This problem is important for large public datasets as scalability is needed but also the ability to update the construction is also needed. Results We create a method for constructing the colored de Bruijn graph for large datasets that is based on partitioning the data into smaller datasets, building the colored de Bruijn graph using a FM-index based representation, and succinctly merging these representations to build a single graph. The last step, merging succinctly, is the algorithmic challenge which we solve in this article. We refer to the resulting method as VariMerge. This construction method also allows the graph to be updated with new data. We validate our approach and show it produces a three-fold reduction in working space when constructing a colored de Bruijn graph for 8000 strains. Lastly, we compare VariMerge to other competing methods—including Vari, Rainbowfish, Mantis, Bloom Filter Trie, the method of Almodaresi et al. and Multi-BRWT—and illustrate that VariMerge is the only method that is capable of building the colored de Bruijn graph for 16 000 strains in a manner that allows it to be updated. Competing methods either did not scale to this large of a dataset or do not allow for additions without reconstruction. Availability and implementation VariMerge is available at https://github.com/cosmo-team/cosmo/tree/VARI-merge under GPLv3 license. Supplementary information Supplementary data are available at Bioinformatics online.

APA, Harvard, Vancouver, ISO, and other styles

46

LI, Ming, Yupeng JIANG, Dongdai LIN, and Qiuyan WANG. "Transition Mappings between De Bruijn Sequences." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A, no. 5 (2017): 1254–56. http://dx.doi.org/10.1587/transfun.e100.a.1254.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Rolim, José, Pavel Tvrdik, Jan Trdlička, and Imrich Vrto. "Bisecting de Bruijn and Kautz graphs." Discrete Applied Mathematics 85, no. 1 (June 1998): 87–97. http://dx.doi.org/10.1016/s0166-218x(98)00031-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Kamareddine, Fairouz, and Alejandro Ríos. "Explicit Substitutions à la de Bruijn." Electronic Notes in Theoretical Computer Science 85, no. 7 (September 2003): 86–105. http://dx.doi.org/10.1016/s1571-0661(04)80759-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Mittal, R., and D. Cherian. "HDDB: Hierarchical directed de Bruijn network." Computers & Electrical Engineering 23, no. 5 (September 1997): 347–55. http://dx.doi.org/10.1016/s0045-7906(97)00012-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Mattar, M. G., L. Magis-Weinberg, and G. K. Aguirre. "De Bruijn cycles for neural decoding." Journal of Vision 11, no. 11 (September 23, 2011): 848. http://dx.doi.org/10.1167/11.11.848.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!