%0 Conference Proceedings
%T Shrinking One-Way Cellular Automata
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%A Kutrib, Martin
%A Malcher, Andreas
%A Wendlandt, Matthias
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Turku, Finland
%Y Jarkko Kari
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9099
%P 141-154
%8 2015-06-08
%D 2015
%R 10.1007/978-3-662-47221-7_11
%Z Computer Science [cs]Conference papers
%X We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (<math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>OCA</mtext></math>) with the additional property that during a computation any cell of the <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>OCA</mtext></math> has the ability to dissolve itself and we call this model shrinking one-way cellular automata (<math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>SOCA</mtext></math>). It turns out that real-time <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>SOCA</mtext></math> are more powerful than real-time <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>OCA</mtext></math>, since they can accept certain linear-time <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>OCA</mtext></math> languages. Additionally, a construction is provided that enables real-time <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>SOCA</mtext></math> to accept the reversal of real-time iterative array languages. Finally, restricted real-time <math xmlns="http://www.w3.org/1998/Math/MathML"> <mtext>SOCA</mtext></math> are investigated which are allowed to dissolve only a number of cells that is bounded by some function. In this case, an infinite strict hierarchy of language classes is obtained.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01442469/document
%2 https://inria.hal.science/hal-01442469/file/338243_1_En_11_Chapter.pdf
%L hal-01442469
%U https://inria.hal.science/hal-01442469
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9099
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA