Results 1 to 10 of about 56 (56)
Complementary symmetric Rote sequences: the critical exponent and the recurrence function [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We determine the critical exponent and the recurrence function of complementary symmetric Rote sequences. The formulae are expressed in terms of the continued fraction expansions associated with the S-adic representations of the corresponding standard ...
Lubomíra Dvořáková +2 more
doaj +1 more source
A Classification of Trapezoidal Words [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word
Gabriele Fici
doaj +1 more source
Abelian returns in Sturmian words [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 In this paper we study an abelian version of the notion of return word. Our main result is a new characterization of Sturmian words via abelian returns. Namely, we prove that a word is Sturmian if and only if each of its factors has two or three abelian ...
Svetlana Puzynina, Luca Q. Zamboni
doaj +1 more source
A Ramsey characterisation of eventually periodic words
Bulletin of the London Mathematical Society, Volume 54, Issue 6, Page 2437-2455, December 2022., 2022 Abstract A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ of an infinite word x$x$ on alphabet X$X$ is called ‘monochromatic’, for a given colouring of the finite words X∗$X^*$ on alphabet X$X$, if each ui$u_i$ is the same colour. Wojcik and Zamboni proved that the word x$x$ is periodic if and only if for every finite colouring of X∗$X^*$ there is a ...
Maria‐Romina Ivan +2 more
wiley +1 more source
Novel Stream Ciphering Algorithm for Big Data Images Using Zeckendorf Representation
Wireless Communications and Mobile Computing, Volume 2021, Issue 1, 2021., 2021 Big data is a term used for very large data sets. Digital equipment produces vast amounts of images every day; the need for image encryption is increasingly pronounced, for example, to safeguard the privacy of the patients’ medical imaging data in cloud disk.
Liangshun Wu, Hengjin Cai, Rajesh Kaluri
wiley +1 more source
A geometrical approach of palindromic factors of standard billiard words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 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.
Jean-Pierre Borel
doaj +1 more source
Hopcroft's automaton minimization algorithm and Sturmian words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino.
Jean Berstel +2 more
doaj +1 more source
Permutation Complexity Related to the Letter Doubling Map [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 Given a countable set X (usually taken to be the natural numbers or integers), an infinite permutation, π, of X is a linear ordering of X. This paper investigates the combinatorial complexity of infinite permutations on the natural numbers associated ...
Steven Widmer
doaj +1 more source
Permutation complexity of images of Sturmian words by marked morphisms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We show that the permutation complexity of the image of a Sturmian word by a binary marked morphism is $n+k$ for some constant $k$ and all lengths $n$ sufficiently large.
Adam Borchert, Narad Rampersad
doaj +1 more source
Interactions between Digital Geometry and Combinatorics on Words [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 We review some recent results in digital geometry obtained by using a combinatorics on words approach to discrete geometry. Motivated on the one hand by the well-known theory of Sturmian words which model conveniently discrete lines in the plane, and on ...
Srečko Brlek
doaj +1 more source