Source author record

L. Q. Zamboni

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Formal Languages and Automata Theory math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

On Generating Binary Words Palindromically

We regard a finite word $u=u_1u_2\cdots u_n$ up to word isomorphism as an equivalence relation on $\{1,2,\ldots, n\}$ where $i$ is equivalent to $j$ if and only if $x_i=x_j.$ Some finite words (in particular all binary words) are generated by "{\it palindromic}" relations of the form $k\sim j+i-k$ for some choice of $1\leq i\leq j\leq n$ and $k\in \{i,i+1,\ldots,j\}.$ That is to say, some finite words $u$ are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function $μ(u)$ defined as the least number of palindromic relations required to generate $u.$ We show that every aperiodic infinite word must contain a factor $u$ with $μ(u)\geq 3,$ and that some infinite words $x$ have the property that $μ(u)\leq 3$ for each factor $u$ of $x.$ We obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast for the Thue-Morse word, we show that the function $μ$ is unbounded.

preprint2014arXiv

Subword complexity and decomposition of the set of factors

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

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.