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

Modified Traffic Cellular Automaton for the Density Classification Task

Kari J., Le Gloannec B.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

141-156

EN

The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conserving cellular automata. We propose a modified traffic CA that washes out finite islands in the same way as the Gacs, Kurdyumov and Levin automaton, but is also guaranteed to converge to a uniform configuration on rings of odd size. We find experimentally several good classifiers that are close to state-conserving cellular automata, and we observe that the best performing known density classifier by Wolz and de Oliveira is only a simple swap away from a state-conserving automaton.

3

Limit Sets of Stable and Unstable Cellular Automata

Ballier A., Guillony P., Kari J.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

45-56

EN

We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.

4

Observations on the Smoothness Properties of Real Functions Computed by Weighted Finite Automata

Droste M., Kari J., Steinby P.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

99-106

EN

We continue investigations of weighted finite automata (WFA) as devices to compute real functions. Based on eigenvalues of the transition matrices of automata we provide a simple necessary condition for continuity and smoothness properties of the functions they compute. Using this condition we show that polynomials are the only smooth functions computed by WFA and that any WFA computing a polynomial of degree k must have at least k+1 states.

5

On the circuit depth of structurally Reversible Cellular Automata

Kari J.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

93-107

EN

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d+2 layers can be combined into d+1 layers. This proves that no more than d+1 layers are necessary. We demonstrate that in the two-dimensional case d=2 the number d+1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.