nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Partially Directed Animals with a Bounded Number of Holes

verfasst von : Valentina Dorigatti, Paolo Massazza

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We address the problem of the exhaustive generation of a particular class of polyominoes, corresponding to partially directed animals with a bounded number of holes. We apply an approach based on discrete dynamical systems to develop an algorithm that generates each polyomino in constant amortized time and space O(n). By implementing the algorithm in C++ we have obtained new sequences that do not appear in the On-Line Encyclopedia of Integer Sequences.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Language Varieties Without Boolean Operations

Nächstes Kapitel On the Computational Power of Programs over Monoid

Barcucci, E., Lungo, A.D., Pergola, E., Pinzani, R.: Directed animals, forests and permutations. Discrete Math. 204(1–3), 41–71 (1999)MathSciNetCrossRef

Barequet, G., Golomb, S.W., Klarner, D.A.: Polyominoes. In: Handbook of Discrete and Computational Geometry, 3rd edn., pp. 359–380. Chapman and Hall/CRC Press (2017)

Bousquet-Mélou, M.: A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154(1–3), 1–25 (1996)MathSciNetCrossRef

Brocchi, S., Castiglione, G., Massazza, P.: On the exhaustive generation of k-convex polyominoes. Theor. Comput. Sci. 664, 54–66 (2017)MathSciNetCrossRef

Castiglione, G., Massazza, P.: An efficient algorithm for the generation of Z-convex polyominoes. In: Barneva, R.P., Brimkov, V.E., Šlapal, J. (eds.) IWCIA 2014. LNCS, vol. 8466, pp. 51–61. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07148-0_6CrossRef

Castiglione, G., Restivo, A.: Reconstruction of L-convex polyominoes. Electron. Notes Discrete Math. 12, 290–301 (2003)MathSciNetCrossRef

Del Lungo, A., Duchi, E., Frosini, A., Rinaldi, S.: On the generation and enumeration of some classes of convex polyominoes. Electron. J. Comb. 11(1) (2004)

Delest, M.P., Viennot, G.: Algebraic languages and polyominoes enumeration. Theor. Comput. Sci. 34(1–2), 169–206 (1984)MathSciNetCrossRef

Duchi, E., Rinaldi, S., Schaeffer, G.: The number of Z-convex polyominoes. Adv. Appl. Math. 40(1), 54–72 (2008)MathSciNetCrossRef

10.

Formenti, E., Massazza, P.: From tetris to polyominoes generation. Electron. Notes Discrete Math. 59, 79–98 (2017)MathSciNetCrossRef

11.

Formenti, E., Massazza, P.: On the Generation of 2-Polyominoes. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 101–113. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94631-3_9CrossRefMATH

12.

Golomb, S.W.: Checker boards and polyominoes. Amer. Math. Monthly 61, 675–682 (1954)MathSciNetCrossRef

13.

Jensen, I.: Enumerations of lattice animals and trees. J. Stat. Phys. 102(3), 865–881 (2001)MathSciNetCrossRef

14.

Mantaci, R., Massazza, P.: From linear partitions to parallelogram polyominoes. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 350–361. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22321-1_30CrossRef

15.

Massazza, P.: A dynamical system approach to polyominoes generation (2020 submitted)

16.

Massazza, P.: On the generation of convex polyominoes. Discrete Appl. Math. 183, 78–89 (2015)MathSciNetCrossRef

17.

Massazza, P.: Hole-free partially directed animals. In: Hofman, P., Skrzypczak, M. (eds.) DLT 2019. LNCS, vol. 11647, pp. 221–233. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24886-4_16CrossRef

18.

Privman, V., Barma, M.: Radii of gyration of fully and partially directed lattice animals. Zeitschrift für Physik B Condensed Matter 57(1), 59–63 (1984)CrossRef

19.

Redner, S., Yang, Z.R.: Size and shape of directed lattice animals. J. Phys. A: Math. Gen. 15(4), L177–L187 (1982)MathSciNetCrossRef

Titel: Partially Directed Animals with a Bounded Number of Holes
verfasst von: Valentina Dorigatti
Paolo Massazza
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-68194-4

Electronic ISBN: 978-3-030-68195-1

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-68195-1_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"