main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

04.11.2016 | Ausgabe 3/2017

# Shrinking one-way cellular automata

Zeitschrift:
Natural Computing > Ausgabe 3/2017
Autoren:
Martin Kutrib, Andreas Malcher, Matthias Wendlandt
Wichtige Hinweise
A preliminary version of this work was presented at the 21st International Workshop on Cellular Automata and Discrete Complex Systems Turku, Finland, June 8–10, 2015.

## Abstract

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata ($$\text{OCA}$$) with the additional property that during a computation any cell of the $$\text{OCA}$$ has the ability to dissolve itself, so-called shrinking one-way cellular automata ($$\text{SOCA}$$). It turns out that real-time $$\text{SOCA}$$ are more powerful than real-time $$\text{OCA}$$, since they can accept certain linear-time $$\text{OCA}$$ languages. On the other hand, linear-time $$\text{OCA}$$ are more powerful than real-time $$\text{SOCA}$$, which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time $$\text{SOCA}$$ to accept the reversal of real-time iterative array languages. Finally, restricted real-time $$\text{SOCA}$$ are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in $$\text{OCA}$$. Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first k time steps, where $$k\ge 0$$ is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Business IT + Informatik
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Business IT + Informatik
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Business IT + Informatik
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Zur Ausgabe