1,720,979 research outputs found
On Sturmian Graphs
No full textIn this paper we define Sturrman 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 Sturtnian 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
Languages with Mismatches
No full textIn this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text S up to some errors. More precisely, we consider sets of words that occur in a text S with k mismatches in any window of size r. The study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of S with errors. The repetition index of a string S is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text S up to errors. We prove that there is a strong relation between the repetition index of S and the maximal length of the minimal forbidden words of the language of factors of S with errors. Moreover, the repetition index plays an important role in the construction of an indexing data structure. More precisely, given a text S over a fixed alphabet, we build a data structure for approximate string matching having average size O(vertical bar S vertical bar center dot log(k+1) vertical bar S vertical bar) and answering queries in time O(vertical bar x vertical bar + vertical bar occ(x)vertical bar) for any word x, where occ is the list of all occurrences of x in S up to errors
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
From Nerode's congruence to Suffix Automata with mismatches
No full textIn this paper we focus on the minimal deterministic finite automaton S(k) that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode's right-invariant congruence that is associated with S(k). This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985. 31-55]. As second result we present an algorithm that makes use of S(k) to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches
Sturmian graphs and integer representations over numeration systems
No full textIn this paper we consider a numeration system, originally due to Ostrowski, based on the continued fraction expansion of a real number alpha. We prove that this system has deep connections with the Sturmian graph associated with alpha. We provide several properties of the representations of the natural integers in this system. In particular, we prove that the set of lazy representations of the natural integers in this numeration system is regular if and only if the continued fraction expansion of alpha is eventually periodic. The main result of the paper is that for any number i the unique path weighted i in the Sturmian graph associated with alpha represents the lazy representation of i in the Ostrowski numeration system associated with alpha
- …
