Search results for "DAWG"

showing 4 items of 4 documents

On Sturmian Graphs

2007

AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.

Discrete mathematicsApplied MathematicsCDAWGsContinued fractionsSturmian wordSturmian wordsCharacterization (mathematics)RepeatsDirected acyclic graphCombinatoricsIndifference graphSturmian words CDAWGs Continued fractions RepeatsChordal graphComputer Science::Discrete MathematicsDiscrete Mathematics and CombinatoricsContinued fractionWord (group theory)Computer Science::Formal Languages and Automata TheoryReal numberMathematics
researchProduct

On the longest common factor problem

2008

The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take…

Discrete mathematicsSettore INF/01 - InformaticaSuffix tree[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeDAWGsuffix tree[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Data structureLongest common substring problemlaw.inventionCombinatoricsSet (abstract data type)Range (mathematics)lawLongest Common Factor ProblemSuffixLowest common ancestorMathematics
researchProduct

Special factors and the combinatorics of suffix and factor automata

2011

AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.

Special factorGeneral Computer ScienceSpecial factorsFactor automatonBüchi automatonω-automatonTheoretical Computer ScienceCombinatoricsDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Data Structures and AlgorithmsCombinatorics on wordStandard Sturmian wordsMathematicsDiscrete mathematicsCombinatorics on wordsDAWGPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesSuffix automatonProbabilistic automatonSuffix automatonComputer Science::Formal Languages and Automata TheoryComputer Science(all)Theoretical Computer Science
researchProduct

Presentations of constrained systems with unconstrained positions

2005

International audience; We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a lineartime construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for con…

[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]finite-memory systemperiodic-finite-type (PFT) system[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyLibrary and Information Sciences01 natural sciencesModulation coding0202 electrical engineering electronic engineering information engineeringMathematicsDiscrete mathematicsChannel codefinite-state encodermodulation codeDAWG020206 networking & telecommunicationsDirected graphDirected acyclic graphforbidden blockComputer Science ApplicationsFinite sequence010201 computation theory & mathematicscodeError detection and correctionrun-length limited (RLL) codesInformation SystemsCoding (social sciences)maximum transition run (MTR)
researchProduct