L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular Automata

Anaël Grandjean 1 Victor Poupet 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing such polyominoes has been recently proved to be recognizable by tiling systems by S. Brocchi, A. Frosini, R. Pinzani and S. Rinaldi. In an attempt to compare recognition power of tiling systems and cellular automata, we have proved that this language can be recognized by 2-dimensional cellular automata working on the von Neumann neighborhood in real time.Although the construction uses a characterization of L-convex polyominoes that is similar to the one used for tiling systems, the real time constraint which has no equivalent in terms of tilings requires the use of techniques that are specific to cellular automata.
Type de document :
Communication dans un congrès
Jarkko Kari. AUTOMATA, Jun 2015, Turku, Finland. 21st Workshop on Cellular Automata and Discrete Complex Systems, LNCS (9099), pp.127-140, 2015, Cellular Automata and Discrete Complex Systems. 〈http://math.utu.fi/automata2015/〉. 〈10.1007/978-3-662-47221-7_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01442468
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:07
Dernière modification le : lundi 16 juillet 2018 - 16:24:02
Document(s) archivé(s) le : vendredi 21 avril 2017 - 16:08:15

Fichier

338243_1_En_10_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Anaël Grandjean, Victor Poupet. L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular Automata. Jarkko Kari. AUTOMATA, Jun 2015, Turku, Finland. 21st Workshop on Cellular Automata and Discrete Complex Systems, LNCS (9099), pp.127-140, 2015, Cellular Automata and Discrete Complex Systems. 〈http://math.utu.fi/automata2015/〉. 〈10.1007/978-3-662-47221-7_10〉. 〈hal-01442468〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

12