Wyniki wyszukiwania - BazTech

1

Piecewise Affine Functions, Sturmian Sequences and Wang Tiles

Kari J.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

257--277

EN

The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960's to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known method to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions byWang tiles. Mortality of such functions is undecidable, which directly yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods.

2

The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable

Margenstern M.

Fundamenta Informaticae

|

2009

|

Vol. 94, nr 1

63-99

EN

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane, see [6, 22, 9, 12] and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994, see [4]. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.

3

On Algebraic Structure of Neighborhoods of Cellular Automata-Horse Power Problem-

Nishio H., Margenstern M., Haeseler F. von

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 3

397-416

EN

In a previous paper we formulated and analyzed the structure of neighborhoods of cellular automata in an algebraic setting such that the cellular space S is represented by the Cayley graph of a finitely generated group and the neighbors are defined as a semigroup generated by the neighborhood N as a subset of S, Nishio and Margenstern 2004 [14,15]. Particularly we discussed the horse power problem whether the motion of a horse (knight) fills the infinite chess board or Z^2- that is, an algebraic problem whether a subset of a group generates it or not. Among others we proved that a horse fills Z^2 even when its move is restricted to properly chosen 3 directions and gave a necessary and sufficient condition for a generalized 3-horse to fill Z^2. This paper gives further developments of the horse power problem, say, on the higher dimensional Euclidean grid, the hexagonal grid and the hyperbolic plane.

4

Some connections between Minkowski and hyperbolic planes

Kosiorek J., Matraś A.

Bulletin of the Polish Academy of Sciences. Mathematics

|

2004

|

Vol. 52, nr 2

133-139

EN

The model of the Minkowski plane in the projective plane with a fixed conic sheds a new light on the connection between the Minkowski and hyperbolic geometries. The construction of the Minkowski plane in a hyperbolic plane over a Euclidean field is given. It is also proved that the geometry in an orthogonal bundle of circles is hyperbolic in a natural way.