Search

Your search keyword '"Zamboni, L."' showing total 9 results
Start Over Author "Zamboni, L." Topic combinatorics
9 results on '"Zamboni, L."'

1. On different generalizations of episturmian words

Author

BUCCI, M, DE LUCA, A, ZAMBONI L. Q., DE LUCA, ALDO, Bucci, M, DE LUCA, Aldo, Luca, De, A, and Zamboni, L. Q.

Subjects
Class (set theory), General Computer Science, Combinatorics on words, Pseudopalindromes, Structure (category theory), Episturmian words, Sturmian words, Theoretical Computer Science, Combinatorics, Operator (computer programming), Closure (mathematics), Integer, Free monoid, Palindrome closure, Palindromes, Word (group theory), Mathematics, Computer Science(all), Involutory antimorphisms
Abstract

In this paper we study some classes of infinite words generalizing episturmian words, and analyse the relations occurring among such classes. In each case, the reversal operator R is replaced by an arbitrary involutory antimorphism @q of the free monoid A^*. In particular, we define the class of @q-words with seed, whose ''standard'' elements (@q-standard words with seed) are constructed by an iterative @q-palindrome closure process, starting from a finite word u"0 called the seed. When the seed is empty, one obtains @q-words; episturmian words are exactly the R-words. One of the main theorems of the paper characterizes @q-words with seed as infinite words closed under @q and having at most one left special factor of each length n>=N (where N is some nonnegative integer depending on the word). When N=0 we call such words @q-episturmian. Further results on the structure of @q-episturmian words are proved. In particular, some relationships between @q-words (with or without seed) and @q-episturmian words are shown.

Full Text
View/download PDF

2. Words 2013.

Author

Karhumäki, J. and Zamboni, L.

Subjects
*SPECIAL issues of periodicals, *PERIODICAL articles, *COMPUTER science, *COMBINATORICS, *MONOIDS
Published
2015
Full Text
View/download PDF

3. Cyclic Complexity of Words

Author

Gabriele Fici, Luca Q. Zamboni, Julien Cassaigne, Marinella Sciortino, Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Università degli studi di Palermo - University of Palermo, Combinatoire, théorie des nombres (CTN), 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), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), 'Automi e Linguaggi Forma: Aspetti Matematici e Applicativi' of the Italian Ministry of Education (MIUR), grant number:2010LYA9RH ., Faculty of Informatics, Eötvös Loránd University, Budapest, and the Department of Foundations of Computer Science, Faculty of Science and Informatics, University of Szeged, in cooperation with EATCS., Csuhaj-Varjú, Ersébet, Dietzfelbinger, Martin, Ésik, Zoltán (Eds.), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Cassaigne, J, Fici, G, Sciortino, M, Zamboni L. Q., Institut Camille Jordan (ICJ), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Cassaigne, J., Fici, G., Sciortino, M., and Zamboni, L.

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 68R15, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Conjugacy class, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, [MATH]Mathematics [math], Discrete Mathematics and Combinatoric, Mathematics, Discrete mathematics, Factor complexity, 010102 general mathematics, Sturmian word, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Sturmian words, Cyclic complexity, factor complexity, Sturmian words, minimal forbidden factor, Infimum and supremum, Toeplitz matrix, Computational Theory and Mathematics, 010201 computation theory & mathematics, Cyclic complexity, Bounded function, Complexity function, Combinatorics (math.CO), Word (group theory), Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equal to that of $x.$ Since $c_x(n)=1$ for some $n\geq 1$ implies $x$ is periodic, it is natural to consider the quantity $\liminf_{n\rightarrow \infty} c_x(n).$ We show that if $x$ is a Sturmian word, then $\liminf_{n\rightarrow \infty} c_x(n)=2.$ We prove however that this is not a characterization of Sturmian words by exhibiting a restricted class of Toeplitz words, including the period-doubling word, which also verify this same condition on the limit infimum. In contrast we show that, for the Thue-Morse word $t$, $\liminf_{n\rightarrow \infty} c_t(n)=+\infty.$, Comment: To appear in Journal of Combinatorial Theory, Series A

Published
2014
Full Text
View/download PDF

4. Anti-powers in infinite words

Author

Antonio Restivo, Luca Q. Zamboni, Manuel Silva, Gabriele Fici, Università degli studi di Palermo - University of Palermo, Dipartimento di Ingegneria Chimica, Gestionale, Informatica, Meccanica [Palermo] (DICGIM), 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), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Combinatoire, théorie des nombres (CTN), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Fici, G., Restivo, A., Silva, M., Zamboni, L., Fici, Gabriele, Restivo, Antonio, Silva, Manuel, and Zamboni, Luca Q.

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Concatenation, Computer Science - Formal Languages and Automata Theory, 68R15, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, Unavoidable regularity, Position (vector), Infinite word, Avoidability, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Order (group theory), Point (geometry), 0101 mathematics, Discrete Mathematics and Combinatoric, Mathematics, Discrete mathematics, 000 Computer science, knowledge, general works, Anti-power, 010101 applied mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Aperiodic graph, Computer Science, Exponent, Pairwise comparison, Combinatorics (math.CO), Software, Word (group theory), Computer Science - Discrete Mathematics
Abstract

In combinatorics of words, a concatenation of $k$ consecutive equal blocks is called a power of order $k$. In this paper we take a different point of view and define an anti-power of order $k$ as a concatenation of $k$ consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. As a consequence, we show that in every aperiodic uniformly recurrent word, anti-powers of every order begin at every position. We further show that every infinite word avoiding anti-powers of order $3$ is ultimately periodic, while there exist aperiodic words avoiding anti-powers of order $4$. We also show that there exist aperiodic recurrent words avoiding anti-powers of order $6$., Revision submitted to Journal of Combinatorial Theory Series A

Published
2018
Full Text
View/download PDF

5. The sequence of open and closed prefixes of a Sturmian word

Author

Alessandro De Luca, Luca Q. Zamboni, Gabriele Fici, DE LUCA, Alessandro, Fici, Gabriele, Zamboni, Luca Q., Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Combinatoire, théorie des nombres (CTN), 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), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), De Luca, A., Fici, G., Zamboni, L., Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Sturmian word, closed word, Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 68R15, 01 natural sciences, Pseudorandom binary sequence, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, Mathematics, Sequence, Closed word, Settore INF/01 - Informatica, Applied Mathematics, 010102 general mathematics, Sturmian word, Prefix, 010201 computation theory & mathematics, Combinatorics (math.CO), Suffix, Element (category theory), Word (computer architecture), Maximal element, Computer Science - Discrete Mathematics
Abstract

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the {\it oc-sequence} of a word, which is the binary sequence whose $n$-th element is $0$ if the prefix of length $n$ of the word is open, or $1$ if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence., Published in Advances in Applied Mathematics. Journal version of arXiv:1306.2254

Published
2017
Full Text
View/download PDF

6. On θ-episturmian words

Author

Luca Q. Zamboni, Alessandro De Luca, Michelangelo Bucci, Aldo de Luca, Bucci, Michelangelo, DE LUCA, Alessandro, DE LUCA, Aldo, and Zamboni, L. Q.

Subjects
Discrete mathematics, Class (set theory), Image (category theory), word complexity, Combinatorics, Set (abstract data type), Sturmian and episturmian word, Integer, Free monoid, Discrete Mathematics and Combinatorics, Alphabet, Computer Science::Formal Languages and Automata Theory, Word (group theory), involutory antimorphism, Mathematics
Abstract

In this paper we study a class of infinite words on a finite alphabet A whose factors are closed under the image of an involutory antimorphism @q of the free monoid A^*. We show that given a recurrent infinite word @[email protected]?A^N, if there exists a positive integer K such that for each n>=1 the word @w has (1) cardA+(n-1)K distinct factors of length n, and (2) a unique right and a unique left special factor of length n, then there exists an involutory antimorphism @q of the free monoid A^* preserving the set of factors of @w.

Published
2009
Full Text
View/download PDF

7. On the least number of palindromes contained in an infinite word

Author

Gabriele Fici, Luca Q. Zamboni, Fici, G, Zamboni, L, Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), 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, General Computer Science, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 68R15, 01 natural sciences, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Palindromes, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Combinatorics on word, Discrete mathematics, 010102 general mathematics, Palindrome, Combinatorics on words, 010201 computation theory & mathematics, Combinatorics (math.CO), Alphabet, Word (group theory), Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

We investigate the least number of palindromic factors in an infinite word. We first consider general alphabets, and give answers to this problem for periodic and non-periodic words, closed or not under reversal of factors. We then investigate the same problem when the alphabet has size two., Accepted for publication in Theoretical Computer Science

Published
2013

8. On some problems related to palindrome closure

Author

Aldo de Luca, Michelangelo Bucci, Alessandro De Luca, Luca Q. Zamboni, Bucci, M, DE LUCA, Aldo, DE LUCA, A, and Zamboni, L.

Subjects
Combinatorics, Prefix, Class (set theory), Closure (computer programming), Iterated function, General Mathematics, Palindrome, Arithmetic, Software, Word (group theory), Computer Science Applications, Mathematics
Abstract

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A* , then the right and left ϑ -palindromic closures of any factor of a ϑ -standard word are also factors of some ϑ -standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting from a nonempty word. We show that pseudostandard words with seed are morphic images of standard episturmian words. Moreover, we prove that for any given pseudostandard word s with seed, all sufficiently long left special factors of s are prefixes of it.

Published
2008

9. A new characteristic property of rich words

Author

Michelangelo Bucci, Luca Q. Zamboni, Amy Glen, Alessandro De Luca, Laboratoire de combinatoire et d'informatique mathématique [Montréal] (LaCIM), Centre de Recherches Mathématiques [Montréal] (CRM), Université de Montréal (UdeM)-Université de Montréal (UdeM)-Université du Québec à Montréal = University of Québec in Montréal (UQAM), The Mathematics Institute, Reykjavík University, 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), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Bucci, M., De Luca, A., Glen, A., and Zamboni, L. Q.

Subjects
FOS: Computer and information sciences, Property (philosophy), General Computer Science, Discrete Mathematics (cs.DM), Rich words, 0102 computer and information sciences, 68R15, Characterization (mathematics), 01 natural sciences, Theoretical Computer Science, Combinatorics, chemistry.chemical_compound, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Palindromes, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Combinatorics on words, Combinatorics on words, Palindromes, Return words, Rich words, 010102 general mathematics, Palindrome, Prefix, Return words, chemistry, 010201 computation theory & mathematics, Combinatorics (math.CO), Suffix, Characteristic property, Computer Science - Discrete Mathematics, Computer Science(all)
Abstract

Originally introduced and studied by the third and fourth authors together with J. Justin and S. Widmer in arXiv:0801.1656, rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. Several characterizations of rich words have already been established. A particularly nice characteristic property is that all 'complete returns' to palindromes are palindromes. In this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix., Comment: 6 pages

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results