We consider the class of hole-free partially directed animals. This is the class of all polyominoes P such that every cell of P can be reached from any cell in the first column of P with a path (inside P) which makes only North, South and East steps, and such that there is not a finite region of empty unitary squares which is surrounded by cells belonging to P. We provide a generation algorithm that allows us to enumerate in constant amortized time using O(n) space.

Hole-free Partially Directed Animals

paolo massazza
2019-01-01

Abstract

We consider the class of hole-free partially directed animals. This is the class of all polyominoes P such that every cell of P can be reached from any cell in the first column of P with a path (inside P) which makes only North, South and East steps, and such that there is not a finite region of empty unitary squares which is surrounded by cells belonging to P. We provide a generation algorithm that allows us to enumerate in constant amortized time using O(n) space.
2019
Proceedings of Developments in Language Theory 2019
9783030248857
23rd International Conference on Developments in Language Theory, DLT 2019
Varsavia
5-9 agosto 2019
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2079072
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact