Search

Your search keyword '"Zamboni, L."' showing total 7 results
Start Over Author "Zamboni, L." Topic fos: computer and information sciences
7 results on '"Zamboni, L."'

1. Subword complexity and decomposition of the set of factors

Author

Cassaigne, J., Frid, A. E., Puzynina, S., and Zamboni, L. Q.

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), F.4.3, Computer Science - Formal Languages and Automata Theory, G.2.1, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 68R15, Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

In this paper we explore a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class $L_k$ if it is a subset of the catenation of $k$ languages $S_1\cdots S_k$, where the number of words of length $n$ in each of $S_i$ is bounded by a constant. The class of infinite words whose set of factors is in $L_k$ is denoted by $W_k$. In this paper we focus on the relations between the classes $W_k$ and the subword complexity of infinite words, which is as usual defined as the number of factors of the word of length $n$. In particular, we prove that the class $W_{2}$ coincides with the class of infinite words of linear complexity. On the other hand, although the class $W_{k}$ is included in the class of words of complexity $O(n^{k-1})$, this inclusion is strict for $k> 2$., The final publication will be available in the Springer proceedings of MFCS 2014

Published
2014
Full Text
View/download PDF

2. 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

3. 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

4. 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

5. 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

6. 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

7. Rich, Sturmian, and trapezoidal words

Author

Luca Q. Zamboni, Aldo de Luca, Amy Glen, DE LUCA, Aldo, Glen, A., and Zamboni, L. Q.

Subjects
FOS: Computer and information sciences, Discrete mathematics, Property (philosophy), Discrete Mathematics (cs.DM), General Computer Science, Rich words, palindrome, Sturmian word, Palindrome, Trapezoidal words, 68R15, Sturmian words, Characterization (mathematics), palindromic complexity, Theoretical Computer Science, Rich word, trapezoidal word, FOS: Mathematics, Mathematics - Combinatorics, Palindromes, Combinatorics (math.CO), Computer Science(all), Computer Science - Discrete Mathematics, Mathematics
Abstract

In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced in arXiv:0801.1656 by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity., 7 pages

Published
2008

Catalog

Books, media, physical & digital resources
See catalog results