We follow in this paper a recent line of work, consisting characterizing the periodically rigid finitely generated groups, i.e., groups for which every subshift finite type is weakly aperiodic also strongly aperiodic. In particular, we show that group admitting presentation with one reduced relator and at least $3$ generators if only it either virtually cyclic or torsion-free $\mathbb Z^2$. This proves special case conjecture Bitar (2024). moreover prove period rigidity preserved under...

Minimizing finite automata, proving trace equivalence of labelled transition systems or representing sofic subshifts involve very similar arguments, which suggests the possibility a unified formalism. We propose states non-deterministic transducer as lingua franca for automata theory, systems, and subshifts. introduce compositional diagrammatical syntax transducers in form string diagrams interpreted relations. This comes with sound rewriting rules allowing reasoning. Our main result is...

In this paper we study colorings (or tilings) of the two-dimensional grid $\mathbb{Z}^2$. A coloring is said to be valid with respect a set $P$ $n\times m$ rectangular patterns if all sub-patterns are in $P$. $c$ low complexity rectangle there exist $m,n\in\mathbb{N}$ and such that $|P|\leq nm$. Open since it was stated 1997, Nivat's conjecture states necessarily periodic. If true, mn$ must We prove exists at least one periodic among ones. use result investigate tiling problem, also known as...

We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove for fundamental group any closed orientable surface genus at least 2.

In this paper we study colorings (or tilings) of the two-dimensional grid ${\mathbb {Z}}^{2}$ . A coloring is said to be valid with respect a set P n × m rectangular patterns if all sub-patterns are in P. c low complexity rectangle there exist $m,n\in \mathbb {N}$ and such that |P|≤ nm. Open since it was stated 1997, Nivat’s conjecture states necessarily periodic. If true, mn must We prove exists at least one periodic among ones. use result investigate tiling problem, also known as domino...

Abstract We present new results on the computational limitations of affine automata (AfAs). First, we show that using endmarker does not increase power AfAs. Second, computation bounded-error rational-valued AfAs can be simulated in logarithmic space. Third, identify some logspace unary languages are recognized by algebraic-valued Fourth, arbitrary real-valued transition matrices and state vectors unbounded-error model. When focusing only rational values, obtain same result also for bounded...

We exhibit a strong connection between the matchgate formalism introduced by Valiant and ZW-calculus of Coecke Kissinger. This provides natural compositional framework for theory as well direct combinatorial interpretation diagrams through perfect matchings their underlying graphs. identify precise fragment ZW-calculus, planar W-calculus, that we prove to be complete universal matchgates, are linear maps satisfying identities. Computing scalars W-calculus corresponds counting graphs, so can...

We study the periodicity of subshifts finite type (SFT) on Baumslag-Solitar groups. show that for residually groups there exist both strongly and weakly-but-not-strongly aperiodic SFTs. In particular, this shows unlike $\mathbb{Z}^2$, but like $\mathbb{Z}^3$, strong weak SFTs are different classes in BS More precisely, we prove a weakly SFT BS(m,n) due to Aubrun Kari is, fact, BS(1,n); not any other BS(m,n). addition, exhibit an which is exists BS(n,n).

By reformulating the Wang tiles formalism with tensors, we propose a natural generalization to probabilistic and quantum setting. In this new framework, introduce notions of tilings periodicity directly extending their classical counterparts. one dimensional case, recover decidability generalized domino problem by linking it trace characterization nilpotent matrices. two-dimensional provide extension weak strong aperiodicity respectively show equivalence those notions, well known in case. We...

We study Nivat's conjecture on algebraic subshifts and prove that in some of them every low complexity configuration is periodic. This the case Ledrappier subshift (the 3-dot system) and, more generally, all two-dimensional over $\mathbb{F}_p$ defined by a polynomial without line factors than one direction. also find an product two polynomials has this property 4-dot another does not.

We present two new results on the computational limitations of affine automata. First, we show that computation bounded-error rational-values automata is simulated in logarithmic space. Second, give an impossibility result for algebraic-valued As a result, identify some unary languages (in space) are not recognized by with cutpoints.