0000000000989264
AUTHOR
Etienne Moutot
Aperiodicity in Quantum Wang Tilings
By reformulating the Wang tiles formalism with tensors, we propose a natural generalization to the probabilistic and quantum setting. In this new framework, we introduce notions of tilings and periodicity directly extending their classical counterparts. In the one dimensional case, we recover the decidability of the generalized domino problem by linking it to the trace characterization of nilpotent matrices. In the two-dimensional case, we provide extension of weak and strong aperiodicity respectively and show the equivalence of those generalized notions, extending the well known equivalence in the classical case. We also exhibit a quantum tile set being aperiodic while its underlying class…
Computational Limitations of Affine Automata
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-values affine automata is simulated in logarithmic space. Second, we give an impossibility result for algebraic-valued affine automata. As a result, we identify some unary languages (in logarithmic space) that are not recognized by algebraic-valued affine automata with cutpoints.
On the computational power of affine automata
We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language and a method how to reduce error in bounded error case. Moreover, we address to the question of [4] by showing that any affine language can be recognized by an AfA with certain limitation on the entries of affine states and transition matrices. Lastly, we present the first languages shown to be not recognized by AfAs with bounded-error.