Search

We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent to which monotonicity constrains the possible asymptotic dynamics by proving two results that do not hold in the subclass of monotone automata. First, it is undecidable whether the automaton almost surely fills the space when initialized on a Bernoulli random configuration with density $p$, for some/all $0 < p < 1$. Second, there exists an automaton whose space-filling property depends on $p$ in a non-monotone way., 18 pages, 3 figures

Background: Microbiome-targeted treatments have been investigated in atopic dermatitis (AD). We aimed to investigate the use of probiotic Lactococcus lactis lysate cream in AD. Methods: 13 patients with mild-to-moderate AD were treated with differently concentrated probiotic creams (3%, 10% and 30%) or placebo cream for 4 weeks. Disease severity (EASI, IGA), epidermal barrier function (TEWL) and patient-reported impact (DLQI, POEM, ADCT, pruritus and sleep disturbance VAS) were measured at baseline, 4 and 8 weeks. Comprehensive clinical data and laboratory values (blood eosinophil count, total serum IgE-levels and specific IgEs to aeroallergens) were obtained. Results: Comparison of the treatment groups showed no clear differences regarding AD severity (EASI, p=0.76, CI: 0.65-1.00), epidermal barrier dysfunction (TEWL, p=0.37, CI: 0.19-0.73) or patient-reported impact (DLQI, p=0.76, CI: 0.65-1.00; POEM, p=0.76, CI: 0.35-0.88; ADCT, p=0.72, CI: 0.65-1.00; pruritus VAS 0.67, CI: 0.55-1.00; sleep disturbance VAS, p=1.00, CI: 0.79-1.00) between different probiotic lysate concentrations and placebo. The probiotic lysate cream was well tolerated and there were no significant adverse effects. Limitations were a small and heterogenous patient groups and a relatively short follow-up with no evaluation of long-term effects. Conclusions: Topical probiotic L. lactis lysate cream showed no clear differences between the tratment groups in mild-to-moderate AD. Although topical probiotics have been reported effective in a limited number of studies, more placebo-controlled clinical studies are needed to explore their potential role in the treatment of AD.

Keratosis pilaris (KP) associates with epidermal barrier defects in atopic dermatitis (AD) but its role in disease severity and concomitant atopic diseases seems to vary between populations. We performed a cross-sectional observational study with 502 randomly selected AD patients of a Finnish tertiary health care center. At a single clinical examination, disease severity (Rajka Langeland severity score and EASI), clinical signs and patient history were evaluated and total IgE levels and frequent filaggrin (FLG) loss-of-function mutations were investigated. There was no link with disease severity (p = 0.649, 95% CI 0.569-0.654), asthma (p = 0.230, 95% CI 0.206-0.281) or atopic sensitization (p = 0.351, 95% CI 0.309-0.392). Keratosis pilaris was significantly associated with palmar hyperlinearity (p < 0.000, 95% CI 0.000-0.006, OR 4.664, 95% CI 2.072-10.496) and the filaggrin loss-of-function mutation 2282del4 (p < 0.000, 95% CI 0.000-0.009, OR 4.917, 95%CI 1.961-12.330). The prevalence of KP in the cohort was generally low and KP seems to be infrequent in Finnish AD patients. This may be explained by the fact that the tested FLG loss-of-function mutations are rarer in the Finnish population compared for example, with central Europe or Asia. Mutations in other locations of the FLG gene or other genes of the epidermal barrier may play a more important role.

We study two-dimensional subshifts whose horizontal trace (a.k.a. projective subdynamics) contains only points of finite support. Our main result is a classification result for such subshifts satisfying a minimality property. As corollaries, we obtain new proofs for various known results on traces of SFTs, nilpotency and decidability of cellular automata, topological full groups and the subshift of prime numbers. We also construct various (sofic) examples illustrating the concepts., 43 pages, 9 figures. Fixed some broken definitions, elaborated on some proofs (kept the informal style). Added an example on path extraction, results otherwise unchanged. Comments welcome!

We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from previous joint work of the author and T\"orm\"a that von Neumann regularity is a decidable condition, and we decide it for all elementary CA, obtaining the optimal radii for weak generalized inverses. Two sufficient conditions for non-regularity are having a proper sofic image or having a point in the image with no preimage of the same period. We show that the non-regular ECA 9 and 28 cannot be proven non-regular using these methods. We also show that a random cellular automaton is non-regular with high probability., Comment: 16 pages, 3 figures; comments welcome! arXiv admin note: text overlap with arXiv:1804.03913

To each one-dimensional subshift $X$, we may associate a winning shift $W(X)$ which arises from a combinatorial game played on the language of $X$. Previously it has been studied what properties of $X$ does $W(X)$ inherit. For example, $X$ and $W(X)$ have the same factor complexity and if $X$ is a sofic subshift, then $W(X)$ is also sofic. In this paper, we develop a notion of automaticity for $W(X)$, that is, we propose what it means that a vector representation of $W(X)$ is accepted by a finite automaton. Let $S$ be an abstract numeration system such that addition with respect to $S$ is a rational relation. Let $X$ be a subshift generated by an $S$-automatic word. We prove that as long as there is a bound on the number of nonzero symbols in configurations of $W(X)$ (which follows from $X$ having sublinear factor complexity), then $W(X)$ is accepted by a finite automaton, which can be effectively constructed from the description of $X$. We provide an explicit automaton when $X$ is generated by certain automatic words such as the Thue-Morse word., 28 pages, 5 figures, 1 table

We construct a two-dimensional Turing machine that is physically universal in both the moving tape and moving head model. In particular, it is mixing of all finite orders in both models. We also provide a variant that is physically universal in the moving tape model, but not in the moving head model., 45 pages plus 6 pages of appendices, 17 figures

We define and study a class of subshifts of finite type (SFTs) defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the number of ways to fill in the corner is the same. The main results are that for such an SFT, a locally legal pattern of convex shape is globally legal, and there is a measure that samples uniformly on all convex sets. Under suitable computability assumptions, this measure can be sampled, and legal configurations counted and enumerated, effectively and efficiently. We show by example that these subshifts need not admit a group (more generally unital magma or quasigroup) structure by shift-commuting continuous operations. Our approach to convexity is axiomatic, and only requires an abstract convex geometry that is "midpointed with respect to the shape". We construct such convex geometries on several groups, in particular all strongly polycyclic groups and free groups. We also show some other methods for sampling finite patterns, one based on orderings and one based on contructing new "independent sets" from old. We also show a link to conjectures of Gottshalk and Kaplansky., 50 pages, 7 figures

We introduce a notion of "simulation" for labelled graphs, in which edges of the simulated graph are realized by regular expressions in the simulating graph, and prove that the tiling problem (aka "domino problem") for the simulating graph is at least as difficult as that for the simulated graph. We apply this to the Cayley graph of the "lamplighter group" $L=\mathbb Z/2\wr\mathbb Z$, and more generally to "Diestel-Leader graphs". We prove that these graphs simulate the plane, and thus deduce that the seeded tiling problem is unsolvable on the group $L$. We note that $L$ does not contain any plane in its Cayley graph, so our undecidability criterion by simulation covers cases not covered by Jeandel's criterion based on translation-like action of a product of finitely generated infinite groups. Our approach to tiling problems is strongly based on categorical constructions in graph theory., Comment: Julia code to experiment with the tilings

Abelian cellular automata (CAs) are CAs which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images have weak*-convergence towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e., randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA randomizes in Cesàro mean if and only if it has no soliton, i.e., a non-zero finite configuration whose time evolution remains bounded in space. This characterization generalizes previously known sufficient conditions for abelian CAs with scalar or commuting coefficients. Second, we exhibit examples of strong randomizers, i.e., abelian CAs randomizing in simple convergence; this is the first proof of this behaviour to our knowledge. We show, however, that no CA with commuting coefficients can be strongly randomizing. Finally, we show that some abelian CAs achieve partial randomization without being randomizing: the distribution of short finite words tends to the uniform distribution up to some threshold, but this convergence fails for larger words. Again this phenomenon cannot happen for abelian CAs with commuting coefficients.

In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.

We show that on the four-symbol full shift, there is a finitely generated subgroup of the automorphism group whose action is (set-theoretically) transitive of all orders on the points of finite support, up to the necessary caveats due to shift-commutation. As a corollary, we obtain that there is a finite set of automorphisms whose centralizer is $\mathbb{Z}$ (the shift group), giving a finitary version of Ryan’s theorem (on the four-symbol full shift), suggesting an automorphism group invariant for mixing subshifts of finite type (SFTs). We show that any such set of automorphisms must generate an infinite group, and also show that there is also a group with this transitivity property that is a subgroup of the commutator subgroup and whose elements can be written as compositions of involutions. We ask many related questions and prove some easy transitivity results for the group of reversible Turing machines, topological full groups and Thompson’s $V$ .

We show that the CPE class $\alpha$ of Barbieri and Garc\'ia-Ramos contains a one-dimensional subshift for all countable ordinals $\alpha$, i.e.\ the process of alternating topological and transitive closure on the entropy pairs relation of a subshift can end on an arbitrary ordinal. This is the composition of three constructions: We first realize every ordinal as the length of an abstract "close-up" process on a countable compact space. Next, we realize any abstract process on a compact zero-dimensional metrizable space as the process started from a shift-invariant relation on a subshift, the crucial construction being the implementation of every compact metrizable zero-dimensional space as an open invariant quotient of a subshift. Finally we realize any shift-invariant relation $E$ on a subshift $X$ as the entropy pair relation of a supershift $Y \supset X$, and under strong technical assumptions we can make the CPE process on $Y$ end on the same ordinal as the close-up process of~$E$., Comment: 18 pages, fixed some typos, added some intro and defs

We study internal Lie algebras in the category of subshifts on a fixed group -- or Lie algebraic subshifts for short. We show that if the acting group is virtually polycyclic and the underlying vector space has dense homoclinic points, such subshifts can be recoded to have a cellwise Lie bracket. On the other hand there exist Lie algebraic subshifts (on any finitely-generated non-torsion group) with cellwise vector space operations whose bracket cannot be recoded to be cellwise. We also show that one-dimensional full vector shifts with cellwise vector space operations can support infinitely many compatible Lie brackets even up to automorphisms of the underlying vector shift, and we state the classification problem of such brackets. From attempts to generalize these results to other acting groups, the following questions arise: Does every f.g. group admit a linear cellular automaton of infinite order? Which groups admit abelian group shifts whose homoclinic group is not generated by finitely many orbits? For the first question, we show that the Grigorchuk group admits such a CA, and for the second we show that the lamplighter group admits such group shifts., Comment: 18 pages

We consider expansive group actions on a compact metric space containing a special fixed point denoted by $0$, and endomorphisms of such systems whose forward trajectories are attracted toward $0$. Such endomorphisms are called asymptotically nilpotent, and we study the conditions in which they are nilpotent, that is, map the entire space to $0$ in a finite number of iterations. We show that for a large class of discrete groups, this property of nil-rigidity holds for all expansive actions that satisfy a natural specification-like property and have dense homoclinic points. Our main result in particular shows that the class includes all residually finite solvable groups and all groups of polynomial growth. For expansive actions of the group $\mathbb{Z}$, we show that a very weak gluing property suffices for nil-rigidity. For $\mathbb{Z}^2$-subshifts of finite type, we show that the block-gluing property suffices. The study of nil-rigidity is motivated by two aspects of the theory of cellular automata and symbolic dynamics: It can be seen as a finiteness property for groups, which is representative of the theory of cellular automata on groups. Nilpotency also plays a prominent role in the theory of cellular automata as dynamical systems. As a technical tool of possible independent interest, the proof involves the construction of tiered dynamical systems where several groups act on nested subsets of the original space., 60 pages, 6 figures. Very minor changes in version 4