The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in $\mathbb{Z}/l\mathbb{Z}$, and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE.

Let $T:x\mapsto x+g$ be an ergodic translation on the compact group $C$ and $M\subseteq C$ a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence $\mathbf{a}:\mathbb{Z}\mapsto \{0,1\}$ defined by $\mathbf{a}\left(k\right)=1$ if $T^k\left(0_C\right)\in M$ and $\mathbf{a}\left(k\right)=0$ otherwise, is called a Hartman sequence. This paper studies the growth rate of $P_{\mathbf{a}}\left(n\right)$, where $P_{\mathbf{a}}\left(n\right)$ denotes the number of binary words of length $n\in \mathbb{N}$ occurring in $\mathbf{a}$. The growth rate is always subexponential and this result is optimal. If $T$ is an ergodic translation $x\mapsto x+\alpha$$...$

We study the complexity of the infinite word $u_{\beta }$ associated with the Rényi expansion of $1$ in an irrational base $\beta \>1$. When $\beta$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ\left(n\right)=n+1$. For $\beta$ such that $d_{\beta }\left(1\right)=t_1{t}_2\cdots t_m$ is finite we provide a simple description of the structure of special factors of the word $u_{\beta }$. When $t_m=1$ we show that $ℂ\left(n\right)=(m-1)n+1$. In the cases when $t_1=t_2=\cdots =t_{m-1}$ or $t_1\>max\{t_2,\cdots ,t_{m-1}\}$ we show that the first difference of the complexity function $ℂ(n+1)-ℂ\left(n\right)$ takes value in $\{m-1,m\}$ for every $n$, and consequently we determine...

We study the complexity of the infinite word uβ associated with the Rényi expansion of 1 in an irrational base β > 1. When β is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity C(n) = n + 1. For β such that dβ(1) = t1t2...tm is finite we provide a simple description of the structure of special factors of the word uβ. When tm=1 we show that C(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1or t1 > max{t2,...,tm-1} we show that the first difference of...

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in $𝒪(m·n)$, where $n$ is the length of the word and $m$ the size of the alphabet.