26 results on '"Sturmian"'
Search Results
2. Some New Results on Palindromic Factors of Billiard Words
- Author
-
Borel, Jean-Pierre, Reutenauer, Christophe, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, De Felice, Clelia, editor, and Restivo, Antonio, editor
- Published
- 2005
- Full Text
- View/download PDF
3. The \(q\)-analog of the Markoff injectivity conjecture over the language of a balanced sequence
- Author
-
Labbé, Sébastien, Labbé, Sébastien, Lapointe, Mélodie, Labbé, Sébastien, Labbé, Sébastien, and Lapointe, Mélodie
- Abstract
The Markoff injectivity conjecture states that \(w\mapsto\mu(w)_{12}\) is injective on the set of Christoffel words where \(\mu:\{\mathtt{0},\mathtt{1}\}^*\to\mathrm{SL}_2(\mathbb{Z})\) is a certain homomorphism and \(M_{12}\) is the entry above the diagonal of a \(2\times2\) matrix \(M\). Recently, Leclere and Morier-Genoud (2021) proposed a \(q\)-analog \(\mu_q\) of \(\mu\) such that \(\mu_{q}(w)_{12}|_{q=1}=\mu(w)_{12}\) is the Markoff number associated to the Christoffel word \(w\) when evaluated at \(q=1\). We show that there exists an order \(<_{radix}\) on \(\{\mathtt{0},\mathtt{1}\}^*\) such that for every balanced sequence \(s \in \{\mathtt{0},\mathtt{1}\}^\mathbb{Z}\) and for all factors \(u, v\) in the language of \(s\) with \(u <_{radix} v\), the difference \(\mu_q(v)_{12} - \mu_q(u)_{12}\) is a nonzero polynomial of indeterminate \(q\) with nonnegative integer coefficients. Therefore, the map \(u\mapsto\mu_q(u)_{12}\) is injective over the language of a balanced sequence. The proof uses an equivalence between balanced sequences satisfying some Markoff property and indistinguishable asymptotic pairs.Mathematics Subject Classifications: 11J06, 68R15, 05A30
- Published
- 2022
4. Sturmian maximizing measures for the piecewise-linear cosine family.
- Author
-
Anagnostopoulou, Vasso, Díaz-Ordaz, Karla, Jenkinson, Oliver, and Richard, Catherine
- Subjects
- *
PIECEWISE linear topology , *MATHEMATICAL mappings , *MATHEMATICAL optimization , *ERGODIC theory , *MATHEMATICAL invariants , *COSINE function , *MATHEMATICAL formulas - Abstract
Let T be the angle-doubling map on the circle $$\mathbb{T}$$, and consider the 1-parameter family of piecewise-linear cosine functions $$f_\theta :\mathbb{T} \to \mathbb{R}$$, defined by $$f_\theta (x) = 1 - 4d_\mathbb{T} (x,\theta )$$. We identify the maximizing T-invariant measures for this family: for each θ the f -maximizing measure is unique and Sturmian (i.e. with support contained in some closed semi-circle). For rational p/q, we give an explicit formula for the set of functions in the family whose maximizing measure is the Sturmian measure of rotation number p/q. This allows us to analyse the variation with θ of the maximum ergodic average for f. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
5. Palindromic complexity of codings of rotations
- Author
-
Blondin Massé, A., Brlek, S., Labbé, S., and Vuillon, L.
- Subjects
- *
CODING theory , *PALINDROMES , *COMBINATORIAL dynamics , *PARAMETER estimation , *MODULES (Algebra) , *CIRCLE , *MATHEMATICAL analysis - Abstract
Abstract: We study the palindromic complexity of infinite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every coding of rotations on two intervals is full, that is, it realizes the maximal palindromic complexity. As a byproduct, a slight improvement about return words in codings of rotations is obtained: every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a finite number of factors. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both palindromes and antipalindromes occurring in it. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
6. On self-matching within integer part sequences
- Author
-
Tognetti, Keith
- Subjects
- *
GRAPH theory , *BERNOULLI numbers , *MATHEMATICAL analysis , *NUMERICAL functions , *COMPUTATIONAL mathematics - Abstract
Abstract: With irrational the graph of against integer , displays interesting patterns of self-matching. This is best seen by comparing the Bernoulli (characteristic Sturmian) or difference sequence , term by term with the Bernoulli sequence displaced by terms , where It is shown that the fraction of such self-matching is the surprisingly simple Of particular interest is the graph of against as it is seen to exhibit an unexpected Moiré pattern obtained simply by folding the lower half of the graph of over the upper half. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
7. A geometrical approach to Palindromic Factors of Standard Billiard Words.
- Author
-
Borel, Jean-Pierre
- Subjects
- *
FORMAL languages , *LANGUAGE & languages , *MACHINE theory , *PALINDROMES , *ALGORITHMS - Abstract
Many results are already known, concerning the palindromic factors and the palindomic prefixes of Standard billiard words, i.e., Sturmian words and billiard words in any dimension, starting at the origin. We give new geometrical proofs of these results, especially for the existence in any dimension of Standard billiard words with arbitrary long palindromic prefixes. [ABSTRACT FROM AUTHOR]
- Published
- 2007
8. Two-pattern strings II—frequency of occurrence and substring complexity.
- Author
-
Franek, Frantisek, Jiang, Jiandong, and Smyth, W.F.
- Subjects
STRING ,APERIODICITY ,CHAOS theory ,REPETITION (Rhetoric) - Abstract
Abstract: The previous paper in this series introduced a class of infinite binary strings, called two-pattern strings, that constitute a significant generalization of, and include, the much-studied Sturmian strings. The class of two-pattern strings is a union of a sequence of increasing (with respect to inclusion) subclasses of two-pattern strings of scope λ, . Prefixes of two-pattern strings are interesting from the algorithmic point of view (their recognition, generation, and computation of repetitions and near-repetitions) and since they include prefixes of the Fibonacci and the Sturmian strings, they merit investigation of how many finite two-pattern strings of a given size there are among all binary strings of the same length. In this paper we first consider the frequency of occurrence of two-pattern strings of length n and scope λ among all strings of length n on : we show that , but that for strings of lengths , two-pattern strings of scope λ constitute more than one-quarter of all strings. Since the class of Sturmian strings is a subset of two-pattern strings of scope 1, it was natural to focus the study of the substring complexity of two-pattern strings to those of scope 1. Though preserving the aperiodicity of the Sturmian strings, the generalization to two-pattern strings greatly relaxes the constrained substring complexity (the number of distinct substrings of the same length) of the Sturmian strings. We derive upper and lower bounds on (the number of distinct substring of length k) of two-pattern strings of scope 1, and we show that it can be considerably greater than that of a Sturmian string. In fact, we describe circumstances in which . [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
9. Palindromic factors of billiard words
- Author
-
Borel, J.-P. and Reutenauer, C.
- Subjects
- *
PALINDROMES , *WORD games , *COMPUTER science , *COMPUTER training - Abstract
Abstract: We study palindromic factors of billiard words, in any dimension. There are differences between the two-dimensional case, and higher dimension. Arbitrary long palindrome factors exist in any dimension, but arbitrary long palindromic prefixes exist in general only in dimension 2. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
10. Characterisations of balanced words via orderings
- Author
-
Jenkinson, Oliver and Zamboni, Luca Q.
- Subjects
- *
LEXICOGRAPHY , *DISTRIBUTION (Probability theory) , *MATHEMATICS - Abstract
Three new characterisations of balanced words are presented. Each of these characterisations is based on the ordering of a shift orbit, either lexicographically or with respect to the norm
|·|1 (which counts the number of occurrences of the symbol 1). [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
11. Two-pattern strings I—A recognition algorithm.
- Author
-
Franek, Frantisek, Lu, Weilin, and Smyth, W.F.
- Subjects
PATTERN recognition systems ,ALGORITHMS ,SET theory ,COMPUTATIONAL mathematics - Abstract
This paper introduces a new class of strings on
{a,b} , called two-pattern strings, that constitute a substantial generalization of Sturmian strings while at the same time sharing many of their nice properties. In particular, we show in this paper that two-pattern strings can be recognized in time proportional to their length. This result is a prelude to showing that the repetitions in these substrings can also be computed in linear time, further that two-pattern strings occur in some sense frequently in the class of all strings on{a,b} . [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF
12. Nonrelativistic Operators for Relativistic Transition Rates
- Author
-
Sami, Maha
- Subjects
Foldy-Wouthuysen ,Sturmian ,Transition ,Wave Function ,Relativistic - Abstract
The Dirac equation provides a fully relativistic covariant equation which can be used to calculate relativistic transition rates but only for one-electron systems. For the two-electron case, one can either use approximate relativistic wave functions or obtain equivalent nonrelativistic operators that can be used with Schr{\"o}dinger wave functions; an approach that is preferred for low atomic number (Z) atoms. By using equivalent nonrelativistic operators obtained from the Foldy-Wouthuysen transformation and relativistically corrected Schr{\"o}dinger wave functions, we show that we obtain the same transition amplitude as in Dirac Theory up to order $\alpha^2$, where $\alpha$ is the fine structure constant. We show this for the one-electron case and provide a theoretical framework for the two-electron case. For the one-electron case we obtain analytic first order corrected wave functions for the $2p$ states which have not been published before. For the two-electron case we obtain first order corrected wave functions using a variational method and compare two different Sturmian basis sets, which we label triangular and linear basis sets. We show that the triangular basis set provides a significant advantage over the linear basis set, increasing the precision by two orders of magnitude. We also compare the wave functions obtained using pseudostates with those obtained analytically and give some suggestions to improve the agreement near zero.
- Published
- 2019
13. Sturmian bases for two-electron systems in hyperspherical coordinates
- Author
-
Dario Marcelo Mitnik, A L Frapiccini, Francisca Mota-Furtado, Patrick F. O’Mahony, A. Abdouraman, Bernard Piraux, Aliou Hamido, and Gustavo Gasaneo
- Subjects
Física Atómica, Molecular y Química ,Angular momentum ,resonances ,Atomic Physics (physics.atom-ph) ,Ciencias Físicas ,FOS: Physical sciences ,Basis function ,01 natural sciences ,Effective nuclear charge ,010305 fluids & plasmas ,Physics - Atomic Physics ,symbols.namesake ,Quantum mechanics ,0103 physical sciences ,Bound state ,Sturmian ,010306 general physics ,Wave function ,Basis set ,Physics ,Quantum Physics ,hyperspherical ,Condensed Matter Physics ,Atomic and Molecular Physics, and Optics ,symbols ,Hamiltonian (quantum mechanics) ,Multipole expansion ,Quantum Physics (quant-ph) ,CIENCIAS NATURALES Y EXACTAS - Abstract
We give a detailed account of an $\it{ab}$ $\it{initio}$ spectral approach for the calculation of energy spectra of two active electron atoms in a system of hyperspherical coordinates. In this system of coordinates, the Hamiltonian has the same structure as the one of atomic hydrogen with the Coulomb potential expressed in terms of a hyperradius and the nuclear charge replaced by an angle dependent effective charge. The simplest spectral approach consists in expanding the hyperangular wave function in a basis of hyperspherical harmonics. This expansion however, is known to be very slowly converging. Instead, we introduce new hyperangular sturmian functions. These functions do not have an analytical expression but they treat the first term of the multipole expansion of the electron-electron interaction potential, namely the radial electron correlation, exactly. The properties of these new functions are discussed in detail. For the basis functions of the hyperradius, several choices are possible. In the present case, we use Coulomb sturmian functions of half integer angular momentum. We show that, in the case of H$^-$, the accuracy of the energy and the width of the resonance states obtained through a single diagonalization of the Hamiltonian, is comparable to the values given by state-of-the-art methods while using a much smaller basis set. In addition, we show that precise values of the electric-dipole oscillator strengths for $S\rightarrow P$ transitions in helium are obtained thereby confirming the accuracy of the bound state wave functions generated with the present method., Comment: 28 pages, 4 figures
- Published
- 2016
- Full Text
- View/download PDF
14. Two-pattern strings II—frequency of occurrence and substring complexity
- Author
-
Frantisek Franek, Jiandong Jiang, and William F. Smyth
- Subjects
Discrete mathematics ,Periodicity ,Sequence ,Class (set theory) ,Fibonacci number ,Series (mathematics) ,Generalization ,010102 general mathematics ,Complexity ,Frequency ,0102 computer and information sciences ,String ,01 natural sciences ,String (physics) ,Substring ,Theoretical Computer Science ,Prefix ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Sturmian ,Two-pattern ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Mathematics - Abstract
The previous paper in this series introduced a class of infinite binary strings, called two-pattern strings, that constitute a significant generalization of, and include, the much-studied Sturmian strings. The class of two-pattern strings is a union of a sequence of increasing (with respect to inclusion) subclasses Tλ of two-pattern strings of scope λ, λ=1,2,…. Prefixes of two-pattern strings are interesting from the algorithmic point of view (their recognition, generation, and computation of repetitions and near-repetitions) and since they include prefixes of the Fibonacci and the Sturmian strings, they merit investigation of how many finite two-pattern strings of a given size there are among all binary strings of the same length. In this paper we first consider the frequency fλ(n) of occurrence of two-pattern strings of length n and scope λ among all strings of length n on {a,b}: we show that limn→∞fλ(n)=0, but that for strings of lengths n⩽2λ, two-pattern strings of scope λ constitute more than one-quarter of all strings. Since the class of Sturmian strings is a subset of two-pattern strings of scope 1, it was natural to focus the study of the substring complexity of two-pattern strings to those of scope 1. Though preserving the aperiodicity of the Sturmian strings, the generalization to two-pattern strings greatly relaxes the constrained substring complexity (the number of distinct substrings of the same length) of the Sturmian strings. We derive upper and lower bounds on C1(k) (the number of distinct substring of length k) of two-pattern strings of scope 1, and we show that it can be considerably greater than that of a Sturmian string. In fact, we describe circumstances in which limk→∞(C1(k)−k)=∞.
- Published
- 2007
- Full Text
- View/download PDF
15. Sturmian bases for two-electron systems in hyperspherical coordinates
- Author
-
UCL - SST/IMCN/NAPS - Nanoscopic Physics, Abdouraman, A., Frapiccini, Ana Laura, Hamido, Aliou, Mota-Furtado, Francisca, O'Mahony, Patrick, Mitnik, Darío, Gasaneo, Gustavo, Piraux, Bernard, UCL - SST/IMCN/NAPS - Nanoscopic Physics, Abdouraman, A., Frapiccini, Ana Laura, Hamido, Aliou, Mota-Furtado, Francisca, O'Mahony, Patrick, Mitnik, Darío, Gasaneo, Gustavo, and Piraux, Bernard
- Abstract
We give a detailed account of an ab initio spectral approach for the calculation of energy spectra of two active electron atoms in a system of hyperspherical coordinates. In this system of coordinates, the Hamiltonian has the same structure as the one of atomic hydrogen with the Coulomb potential expressed in terms of a hyperradius and the nuclear charge replaced by an angle dependent effective charge. The simplest spectral approach consists in expanding the hyperangular wave function in a basis of hyperspherical harmonics. This expansion however, is known to be very slowly converging. Instead, we introduce new hyperangular Sturmian functions. These functions do not have an analytical expression but they treat the first term of the multipole expansion of the electron-electron interaction potential, namely the radial electron correlation, exactly. The properties of these new functions are discussed in detail. For the basis functions of the hyperradius, several choices are possible. In the present case, we use Coulomb-Sturmian functions of half integer angular momentum. We show that, in the case of H-, the accuracy of the energy and the width of the resonance states obtained through a single diagonalization of the Hamiltonian, is comparable to the values given by state-of-the-art methods while using a much smaller basis set. In addition, we show that precise values of the electric-dipole oscillator strengths for transitions in helium are obtained thereby confirming the accuracy of the bound state wave functions generated with the present method.
- Published
- 2016
16. Characterisations of balanced words via orderings
- Author
-
Luca Q. Zamboni and Oliver Jenkinson
- Subjects
Combinatorics ,Balanced ,Lexicographic order ,General Computer Science ,Sturmian ,Orbit (control theory) ,Lexicographical order ,Symbol (formal) ,Mathematics ,Theoretical Computer Science ,Computer Science(all) - Abstract
Three new characterisations of balanced words are presented. Each of these characterisations is based on the ordering of a shift orbit, either lexicographically or with respect to the norm |·|1 (which counts the number of occurrences of the symbol 1).
- Published
- 2004
- Full Text
- View/download PDF
17. A Coloring Problem for Sturmian and Episturmian Words
- Author
-
Aldo de Luca, Luca Q. Zamboni, Elena V. Pribavkina, Università degli studi di Napoli Federico II, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,COLORING PROBLEMS ,0102 computer and information sciences ,02 engineering and technology ,68R15 ,01 natural sciences ,Combinatorics ,Factorization ,Computer Science::Discrete Mathematics ,INFINITE WORD ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Combinatorics ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,STURMIAN ,STURMIAN WORD ,Ramsey theory ,Sturmian word ,RAMSEY THEORY ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,COMPUTER SCIENCE ,010201 computation theory & mathematics ,Aperiodic graph ,ARTIFICIAL INTELLIGENCE ,020201 artificial intelligence & image processing ,Monochromatic color ,Combinatorics (math.CO) ,Coloring problem ,EPISTURMIAN WORDS ,Word (computer architecture) ,Computer Science::Formal Languages and Automata Theory ,Computer Science - Discrete Mathematics - Abstract
We consider the following open question in the spirit of Ramsey theory: Given an aperiodic infinite word w, does there exist a finite coloring of its factors such that no factorization of w is monochromatic? We show that such a coloring always exists whenever w is a Sturmian word or a standard episturmian word. © 2013 Springer-Verlag.
- Published
- 2013
18. A coloring problem for Sturmian and episturmian words
- Author
-
De, Luca, A., Pribavkina, E. V., Zamboni, L. Q., De, Luca, A., Pribavkina, E. V., and Zamboni, L. Q.
- Abstract
We consider the following open question in the spirit of Ramsey theory: Given an aperiodic infinite word w, does there exist a finite coloring of its factors such that no factorization of w is monochromatic? We show that such a coloring always exists whenever w is a Sturmian word or a standard episturmian word. © 2013 Springer-Verlag.
- Published
- 2013
19. Sturmian diziler
- Author
-
Kaçmaz, Şerife, Halıcı, Serpil, Matematik Anabilim Dalı, Yardımcı Doçent Doktor Serpil Halıcı, and Sakarya Üniversitesi, Fen Bilimleri Enstitüsü, Matematik Anabilim Dalı, Matematik
- Subjects
Matematik ,Sturmian ,Kelime ,Fibonacci dizisi ,Mathematics ,Dizi - Abstract
06.03.2018 tarihli ve 30352 sayılı Resmi Gazetede yayımlanan “Yükseköğretim Kanunu İle Bazı Kanun Ve Kanun Hükmünde Kararnamelerde Değişiklik Yapılması Hakkında Kanun” ile 18.06.2018 tarihli “Lisansüstü Tezlerin Elektronik Ortamda Toplanması, Düzenlenmesi ve Erişime Açılmasına İlişkin Yönerge” gereğince tam metin erişime açılmıştır. x, elemanları özel kurulmuş ve alfabe olarak adlandırılan harflerin bir dizisidir. Bu noktada harflerin kelimeyi, kelimelerin de diziyi oluşturduğu görülmektedir.şeklinde iki uzunluğunda, ikili alfabe üzerinde durularak Sturmian diziler tanımlanır. alfabesi üzerinde tanımlı olan bir dizisinin Sturmian dizi olması için gerek ve yeter şart 'in dengeli olması ve sonunda periyodik olmamasıdır.Sonsuz Sturmian dizisinin boştan farklı sonlu bir alt dizisine sonlu Sturmian dizi denir. Fibonacci dizileri, Sturmian dizilerinin en iyi bilinen özel bir durumudur. Sturmian diziler, düzlemdeki doğrularla da ilişkilidirler.Merkezi kelimelerin kümesi PER şeklinde gösterilir ve her Sturmian kelime PER deki kelimenin alt dizisidir. Bu yüzden PER Sturmian kelimelerin çekirdeğidir. Bu noktada PER'den yararlanarak Sturmian dizilerin kombinasyonel özellikleri hakkında bilgi sahibi olunabilir.Sturmian diziyi açıklamak ve tanımlamak için farklı yollar bu tezde çalışılmıştır.Anahtar Kelimeler: Kelime, Dizi, Sturmian, Fibonacci Dizisi A string is a sequence of letters which are the elements of a specified set called alphabet. At this point we can see letters generate the word, words generate the string obviously.Sturmian Strings are defined on binary alphabet which is called and size 2. string, which is difined on alphabet, can be Sturmian String if and only if is balanced and not ultimately periodic.A finite Sturmian string is any finite non-empty substring of an infinite Sturmian string. A Fibonacci string is a special case of a sturmian string that is well-known. Sturmian strings are related to straight lines.Set of all central words denote by PER and every Sturmian word is a substring of a word in PER. Hence the set PER is a kernel of the Sturmian words. At this point it can be make knowledge about combinational properties of the Sturmian strings by using the PER.In this thesis, it is worked on different ways for defined and explaining of Sturmian string.Key Words: Word, String, Sturmian, Fibonacci Strings.
- Published
- 2008
20. Words and morphisms with Sturmian erasures
- Author
-
Adel Guerziz, Michel Koskas, Fabien Durand, Laboratoire Amiénois de Mathématique Fondamentale et Appliquée (LAMFA), and Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Words with Sturmian erasures ,Discrete Mathematics (cs.DM) ,General Mathematics ,68R15 ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Sturmian morphisms ,morphism ,01 natural sciences ,Combinatorics ,Morphism ,Computer Science::Discrete Mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Finitely-generated abelian group ,Physics::Atomic Physics ,word ,0101 mathematics ,sturmian ,Mathematics ,Computer Science::Information Theory ,010102 general mathematics ,Sturmian word ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Sturmian words ,sequence ,Combinatorics (math.CO) ,erasure ,Computer Science::Formal Languages and Automata Theory ,Computer Science - Discrete Mathematics - Abstract
International audience; We say $x \in \{ 0,1,2 \}^{\NN}$ is a word with Sturmian erasures if for any $a\in \{ 0,1,2 \}$ the word obtained erasing all $a$ in $x$ is a Sturmian word. A large family of such words is given coding trajectories of balls in the game of billiards in the cube. We prove that the monoid of morphisms mapping all words with Sturmian erasures to words with Sturmian erasures is not finitely generated.
- Published
- 2004
21. On Christoffel classes
- Author
-
Borel, Jean-Pierre, Reutenauer, Christophe, Borel, Jean-Pierre, and Reutenauer, Christophe
- Abstract
We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.
- Published
- 2006
22. Repetitions in Sturmian strings
- Author
-
William F. Smyth, F. Franěk, and Ayşe Karaman
- Subjects
Reduction (recursion theory) ,Fibonacci number ,General Computer Science ,Word ,0102 computer and information sciences ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Repetition ,High Energy Physics::Theory ,Integer ,Sturmian ,0101 mathematics ,Mathematics ,Discrete mathematics ,Sequence ,010102 general mathematics ,String (computer science) ,Sturmian word ,Superstring theory ,String ,Algorithm ,010201 computation theory & mathematics ,Exponent ,Computer Science::Formal Languages and Automata Theory ,Computer Science(all) - Abstract
In this paper we apply a simple representation of Sturmian strings, which we call a “reduction sequence”, to three algorithms. The first algorithm accepts as input a given finite string x and determines in time O(|x|) whether or not x is Sturmian. The second algorithm is a modification of the first that, in the case that x is Sturmian, outputs a reduction sequence for a superstring u of x that is a prefix of an infinite Sturmian string. The third algorithm uses the reduction sequence of u to compute all the repetitions in u in time Θ(|u|), thus extending a recent result for Fibonacci strings. The third algorithm is also based on a characterization of the repetitions in a Sturmian string that describes them compactly in terms of “runs”. Finally, for every integer r⩾4, we show how to construct an infinite Sturmian string that contains maximal repetitions of exponents 2,3,…,r−1, but none of exponent r.
- Full Text
- View/download PDF
23. Two-pattern strings I—A recognition algorithm
- Author
-
Frantisek Franek, William F. Smyth, and Weilin Lu
- Subjects
TheoryofComputation_MISCELLANEOUS ,Two-patern ,Generalization ,Class (philosophy) ,0102 computer and information sciences ,02 engineering and technology ,Linear ,01 natural sciences ,String (physics) ,Theoretical Computer Science ,Combinatorics ,String kernel ,Sturmian ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Jaro–Winkler distance ,Recognition algorithm ,Time complexity ,Mathematics ,Discrete mathematics ,020206 networking & telecommunications ,String ,Substring ,Computational Theory and Mathematics ,010201 computation theory & mathematics - Abstract
This paper introduces a new class of strings on {a,b}, called two-pattern strings, that constitute a substantial generalization of Sturmian strings while at the same time sharing many of their nice properties. In particular, we show in this paper that two-pattern strings can be recognized in time proportional to their length. This result is a prelude to showing that the repetitions in these substrings can also be computed in linear time, further that two-pattern strings occur in some sense frequently in the class of all strings on {a,b}.
- Full Text
- View/download PDF
24. Palindromic complexity of codings of rotations
- Author
-
Blondin Massé, Alexandre, Brlek, Srecko, Labbé, Sébastien, Vuillon, Laurent, Blondin Massé, Alexandre, Brlek, Srecko, Labbé, Sébastien, and Vuillon, Laurent
- Abstract
We study the palindromic complexity of infinite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every coding of rotations on two intervals is full, that is, it realizes the maximal palindromic complexity. As a byproduct, a slight improvement about return words in codings of rotations is obtained: every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a finite number of factors. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both palindromes and antipalindromes occurring in it.
25. Palindromic complexity of codings of rotations
- Author
-
Blondin Massé, Alexandre, Brlek, Srecko, Labbé, Sébastien, Vuillon, Laurent, Blondin Massé, Alexandre, Brlek, Srecko, Labbé, Sébastien, and Vuillon, Laurent
- Abstract
We study the palindromic complexity of infinite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every coding of rotations on two intervals is full, that is, it realizes the maximal palindromic complexity. As a byproduct, a slight improvement about return words in codings of rotations is obtained: every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a finite number of factors. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both palindromes and antipalindromes occurring in it.
26. On Christoffel classes
- Author
-
Borel, Jean-Pierre, Reutenauer, Christophe, Borel, Jean-Pierre, and Reutenauer, Christophe
- Abstract
We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.