6 papers
On Word Representations and Embeddings in Complex Matrices
Paul C. Bell, George Kenison, Reino Niskanen +2
Embeddings of word structures into matrix semigroups provide a natural bridge between combinatorics on words and linear algebra. However, low-dimensional matrix semigroups impose s…
On the Identity and Group Problems for Complex Heisenberg Matrices
Paul C. Bell, Reino Niskanen, Igor Potapov +1
We study the Identity Problem, the problem of determining if a finitely generated semigroup of matrices contains the identity matrix; see Problem 3 (Chapter 10.3) in ``Unsolved Pro…
Monadic Decomposability of Regular Relations
Pablo Barcelo, Chih-Duo Hong, Xuan-Bach Le +2
Monadic decomposibility --- the ability to determine whether a formula in a given logical theory can be decomposed into a boolean combination of monadic formulas --- is a powerful…
On the Identity Problem for the Special Linear Group and the Heisenberg Group
Sang-Ki Ko, Reino Niskanen, Igor Potapov
We study the identity problem for matrices, i.e., whether the identity matrix is in a semigroup generated by a given set of generators. In particular we consider the identity probl…
Undecidability of Two-dimensional Robot Games
Reino Niskanen, Igor Potapov, Julien Reichert
Robot game is a two-player vector addition game played on the integer lattice . Both players have sets of vectors and in each turn the vector chosen by a player is ad…
Weighted automata on infinite words in the context of Attacker-Defender games
Vesa Halava, Tero Harju, Reino Niskanen +1
We consider infinite-state Attacker-Defender games with reachability objectives. The results of the paper are twofold. Firstly we prove a new language-theoretic result for weighted…