BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Aleksi Saarela appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We consider systems of word equations and their solution sets. We discuss some fascinating properties of those, namely the size of a maximal independent set of word equations, and proper chains of solution sets of those. We recall the basic results, extend some known results and formulate several fundamental problems of the topic.
We develop a new tool, namely polynomial and linear algebraic methods, for studying systems of word equations. We illustrate its usefulness by giving essentially simpler proofs of several hard problems. At the same time we prove extensions of these results. Finally, we obtain the first nontrivial upper bounds for the fundamental problem of the maximal size of independent systems. These bounds depend quadratically on the size of the shortest equation. No methods of having such bounds have been known before.
In this paper we introduce and study a family of complexity functions of infinite words indexed by $k \in \ints ^+ \cup {+\infty}.$ Let $k \in \ints ^+ \cup {+\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$ in $A^*$ are said to be $k$-Abelian equivalent if for all $x\in A^*$ of length less than or equal to $k,$ the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v.$ This defines a family of equivalence relations $\thicksim_k$ on $A^*,$ bridging the gap between the usual notion of Abelian equivalence (when $k=1$) and equality (when $k=+\infty).$ We show that the number of $k$-Abelian equivalence classes of words of length $n$ grows polynomially, although the degree is exponential in $k.$ Given an infinite word $ω\in A^\nats,$ we consider the associated complexity function $\mathcal {P}^{(k)}_ω:\nats \rightarrow \nats$ which counts the number of $k$-Abelian equivalence classes of factors of $ω$ of length $n.$ We show that the complexity function $\mathcal {P}^{(k)}$ is intimately linked with periodicity. More precisely we define an auxiliary function $q^k: \nats \rightarrow \nats$ and show that if $\mathcal {P}^{(k)}_ω(n)<q^k(n)$ for some $k \in \ints ^+ \cup {+\infty}$ and $n\geq 0,$ the $ω$ is ultimately periodic. Moreover if $ω$ is aperiodic, then $\mathcal {P}^{(k)}_ω(n)=q^k(n)$ if and only if $ω$ is Sturmian. We also study $k$-Abelian complexity in connection with repetitions in words. Using Szemerédi's theorem, we show that if $ω$ has bounded $k$-Abelian complexity, then for every $D\subset \nats$ with positive upper density and for every positive integer $N,$ there exists a $k$-Abelian $N$ power occurring in $ω$ at some position $j\in D.$
In this paper we investigate local to global phenomena for a new family of complexity functions of infinite words indexed by $k \in \Ni \cup \{+\infty\}$ where $\Ni$ denotes the set of positive integers. Two finite words $u$ and $v$ in $A^*$ are said to be $k$-Abelian equivalent if for all $x \in A^*$ of length less than or equal to $k$, the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v$. This defines a family of equivalence relations $\sim_k$ on $A^*$, bridging the gap between the usual notion of Abelian equivalence (when $k = 1$) and equality (when $k = +\infty$). Given an infinite word $w \in A^ω$, we consider the associated complexity function $\mathcal P^{(k)}_w : \Ni \rightarrow \Ni$ which counts the number of $k$-Abelian equivalence classes of factors of $w$ of length $n$. As a whole, these complexity functions have a number of common features: Each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our paper.
We develop new polynomial methods for studying systems of word equations. We use them to improve some earlier results and to analyze how sizes of systems of word equations satisfying certain independence properties depend on the lengths of the equations. These methods give the first nontrivial upper bounds for the sizes of the systems.